Research On The Query Of Hilbert Curve

There are a variety of space-filling curves, such as Sierpinski curve, Lebesgue curve, Schoenberg curve of space-filling curves, Jordan curve with a positive Lebesgue measure and so on. The most commonly used ones are Hilbert curve, Z curve and Gray curve, and the main difference between them lies in the different mapping methods. In recent years, space-filling curves have been used on indexing and query in spatial database because of its dimensionality reduction and data clustering characteristics. Before space-filling curve is applied to spatial database, the most commonly used index method is based on the indexing structure of R-tree and its variation trees. In the two-dimensional space, nearest neighbor query algorithm based on R-tree and sequential scanning algorithm have higher searching efficiency. With the increase of the spatial dimension, the amount of data information increases in geometric progression, at present, the query efficiency of the above two algorithms declines sharply. Therefore, dimensionality reduction and clustering characteristics of Hilbert curve are used, which is an one-to-one mapping of points in high-dimensional space into the one-dimensional space, which not only does not affect the comparison of the distance between points,but also has higher efficiency of nearest neighbor query and other queries.Firstly, Hilbert curve was introduced, and the properties and characteristics of Hilbert curve were analyzed, and then dimensionality reduction and clustering characteristics were summarized emphatically.Secondly, one kind of nearest neighbor query algorithm based on the grid partition of Hilbert curve was proposed. First, dividing the data space into no-overlap and equivalent grids; then conducting linear ordering of the points in grids; finally, when the nearest neighbor would be obtained, only the points of the grid which the query point lay and the points of its surrounding grids were needed to access.Thirdly, one kind of the optimal location query algorithm based on the Hilbert curve was proposed. First, mapping the spatial points to one-dimensional space by dimensionality reduction of Hilbert curve; then using the range query algorithm. based on R-tree respectively, and saving all data objects and target objects in two queues; finally, traversing from the queue of target object lay to all data queues according to certain rules, obtaining priority set and calculating priority.