k-d Range Search with Binary Patricia Tries
| dc.contributor.author | Shi, Qingxiu | |
| dc.contributor.author | Nickerson, Bradford, G. | |
| dc.date.accessioned | 2023-03-01T18:27:36Z | |
| dc.date.available | 2023-03-01T18:27:36Z | |
| dc.date.issued | 2005 | |
| dc.description.abstract | We use Patricia tries to represent textual and spatial data, and present a range search algorithm for reporting all k-d records from a set of size n intersecting a query rectangle. Data and queries include both textual and spatial data. Patricia tries are evaluated experimentally (for n up to 1,000,000) using uniform distributed random spatial data and textual data selected from the Canadian toponymy. We compared the performance of the Patricia trie for k-d points, k-d rectangles and k-d combined textual and spatial data to the k-d tree, R*-tree, Ternary Search Trie and the naive method. Overall, our experiments show that Patricia tries are the best when F Є [0, log2 n] (F is the number of data in range). The expected range search time for Patricia tries was determined theoretically, and found to agree with experimental results when 2 <= k <= 20. | |
| dc.description.copyright | Copyright @ Qingxiu Shi and Bradford G. Nickerson, 2005. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14760 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | k-d Range Search with Binary Patricia Tries | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1