Browsing by Author "Shi, Qingxiu"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Approximate Orthogonal Range Search using Patricia Tries
    (2005) Shi, Qingxiu; Nickerson, Bradford, G.
    We use Patricia tries to answer E-approximate orthogonal range search on a set of n random points and rectangles in k-dimensional space. Given n k-dimensional random points or rectangles and a k-dimensional query rectangle, E-approximate orthogonal range query counts (or reports) the points in the query rectangle or the rectangles intersecting the query rectangle, allowing errors near the boundary of the query rectangle. Points within a distance of a function of E the boundary of the query rectangle might be misclassified. The approximate orthogonal range search time using Patricia tries is determined theoretically to be O(k log n/E[superscript k-1]) for cubical range queries. Patricia tries are evaluated experimentally for E-approximate orthogonal range counting and reporting queries (for 2 < k < 10 and n up to 1,000,000) using uniformly distributed random points and rectangles, and we compared the performance of the Patricia trie for k-d points with the k-d tree and the adaptive k-d tree. The experimental results show that allowing small errors can significantly improve the query execution time of the approximate range counting. For epsilon = 0.05, an average of 50% fewer nodes are visited for the Patricia trie (compared to the exact range search).
  • Thumbnail Image
    Item
    Decreasing Radius K-Nearest Neighbor Search using Mapping-based Indexing Schemes
    (2006) Shi, Qingxiu; Nickerson, Bradford, G.
    A decreasing radius k-nearest neighbor search algorithm for the mapping-based indexing schemes is presented. We implement the algorithm in the Pyramid technique and the iMinMax(θ), respectively. The Pyramid technique divides d-dimensional data space into 2d pyramids, and the iMinMax(θ) divides the data points into d partitions. Given a query point q, we initialize the radius of a range query to be the furthest distance of the k candidate nearest neighbors from q in the pyramid (partition) which q is in, then examine the rest of the pyramids (partitions) one by one. After one pyramid (partition) is checked, the radius of the range query decreases or remains the same. We compare the decreasing radius k-nearest neighbor search algorithm with the increasing radius k-nearest neighbor search algorithm using the Pyramid technique and the iMinMax(θ). Moreover, the decreasing radius k-nearest neighbor search performance of these two mapping-based indexing schemes is compared to the BBD-tree, the R*-tree and naive search. Experimental results show that our decreasing radius k-nearest neighbor search algorithm for the mapping-based indexing schemes is efficient when d <= log2 n.
  • Thumbnail Image
    Item
    k-d Range Search with Binary Patricia Tries
    (2005) Shi, Qingxiu; Nickerson, Bradford, G.
    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.
  • Thumbnail Image
    Item
    On k-d Range Search With Large k
    (2006) Shi, Qingxiu; Nickerson, Bradford, G.
    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.