On k-d Range Search With Large k
Loading...
Files
Date
2006
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We present two new k-dimensional data structures, called the PKD-tree and the PKD[superscript +]-tree, respectively. They are explored for indexing combined text and point data, and evaluated experimentally for orthogonal range search (for 2 < k < 100 and n up to 1,000,000) using synthetic data and real data. We compared the range search performance of the PKD-tree with the PKD[superscript +]-tree, the k-d tree, the Pyramid technique, the R*-tree and naive search. The experimental results show that the PKDtree and the PKD+-tree have very good performance for large k, and they always outperform the Pyramid technique, and are better than k-d tree and the R*-tree when k > log[subscript 2]n. For a PKD+-tree built from n uniform and random data points, an orthogonal range search with a query square W of side length ^ visits O(k log n + n(1 - (1 - 2^)[superscript k])) nodes for ^ < 0.5.