A k-Closest-Pair Query Algorithm Based on Grid Partition of Hilbert Curve

摘要

The k-closest-pair query is one of the important operations in spatial database. When the present k-closest-pair algorithms apply to high-dimensional space, their efficiencies are very low. Utilizing the clustering quality of Hilbert curve, divide high-dimensional space into equal-size grids according to the construction of Hilbert curve, and map the points to linear space. The paper presents the definitions and the theory about the method of the dimensionality reduction, gives an algorithm to query k closest pairs based on Hilbert curve. It can delete numerous useless points from data set, so the number of points decreases dramatically. This optimizes scanning procedure, and reduces the running time. The paper proves the correctness of the algorithm. According to the experimental results, the algorithm is better than the method of the brute-force algorithm.