k-d Range Search with Binary Patricia Tries
Loading...
Files
Date
2005
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.