k-d Range Search with Binary Patricia Tries

Loading...
Thumbnail Image

Date

2005

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.

Description

Keywords

Citation

Collections