On k-d Range Search With Large k
| dc.contributor.author | Shi, Qingxiu | |
| dc.contributor.author | Nickerson, Bradford, G. | |
| dc.date.accessioned | 2023-03-01T18:30:16Z | |
| dc.date.available | 2023-03-01T18:30:16Z | |
| dc.date.issued | 2006 | |
| dc.description.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. | |
| dc.description.copyright | Copyright @ Qingxiu Shi and Bradford G. Nickerson, 2006. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14982 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | On k-d Range Search With Large k | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1