Z曲线网格划分的最近邻查询  

Nearest neighbor query under grid partition of Z curve

作　　者：刘润涛[1] 陈琳琳[2] 田广悦[2] 

机构地区：[1]哈尔滨理工大学信息与科学计算技术研究所,哈尔滨150080 [2]哈尔滨理工大学应用科学学院应用数学系,哈尔滨150080

出　　处：《计算机工程与应用》2013年第22期123-126,共4页Computer Engineering and Applications

基　　金：黑龙江省教育厅2011年度科学技术研究项目资助(No.12511103;No.12511126);黑龙江省自然科学基金资助(No.F201134)

摘　　要：为了解决高维空间最近邻查询问题,在网格划分的基础上,利用Z曲线对网格排序并将二维空间中的点映射到一维空间中。考虑到点的分布和网格形状对查询的影响,提出最小查询层和方向变换的概念。只要给出查询点与任意点之间的方向变换,即可求出该点所在的网格Z值,从而求出任意查询层的所有网格Z值。证明了最近邻查询只需访问至最小查询层后再访问两层。基于此提出了最近邻查询算法,它适用于数据点任意分布的情况,该算法能够得到精确解。In order to solve Nearest Neighbor（NN） query in high-dimensional space, the grids are ordered and points on two- dimensional space are mapped into 1D space with Z curve based on grid partition. Considering the influence of the distribution of points and the shape of grids on queries, the definitions of minimum query layer and direction transformation are proposed. The Z value of any point could be computed if only the direction transformation between it and query point is given, and moreover all Z values of any query layer can be computed. It is proved that the layer, two more layers than the minimum query layer are needed to be queried to accomplish the NN query. The grid shape is tend to square would make efficient and the NN only needs visit the minimum and then two layers are proved. Based on these, the NN algorithm is presented, which is suitable to points of any distribution. And the accurate solution can be obtained.

关 键 词：Z曲线 网格划分 最近邻查询 查询层 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]