On kappa-D range search with patricia tries
Patricia tries are explored for indexing combined text and spatial data. A combined text and spatial data range search algorithm is presented for reporting all data from a set of size n intersecting a query hyperrectangle. We also use Patricia tries to answer epsilon-approximate orthogonal range search on a set of n random points and hyperrectangles in k-dimensional data space. epsilon-approximate orthogonal range counting queries can be answered in O(k log n/epsilon(k-1)) timeand the number of nodes visited for orthogonal range counting queries is shown to be O(log n + k(1+ 2n(1/k)Delta)(k-1)) for cubical range of side length Delta. Patricia tries are evaluated experimentally for both orthogonal range search and epsilon-approximate orthogonal range search (for 2 <= k <= 14 and n up to 1,000,000) using uniformly distributed random data. The expected range search time is determined theoretically and found to agree with experimental results.
orthogonal range search patricia trie approximate range search