Nearest neighbor query under grid partition of Z curve

Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (22): 123-126.

Previous Articles Next Articles

Nearest neighbor query under grid partition of Z curve

LIU Runtao1, CHEN Linlin2, TIAN Guangyue2

1.Institute of Information and Scientific Computing Technology, Harbin University of Science and Technology, Harbin 150080, China
2.Department of Applied Mathematics, College of Applied Sciences, Harbin University of Science and Technology, Harbin 150080, China

Online:2013-11-15 Published:2013-11-15

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

刘润涛1，陈琳琳2，田广悦2

1.哈尔滨理工大学信息与科学计算技术研究所，哈尔滨 150080
2.哈尔滨理工大学应用科学学院应用数学系，哈尔滨 150080

Abstract

Abstract: 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.

Key words: Z curve, grid partition, nearest neighbor, query layer

摘要： 为了解决高维空间最近邻查询问题，在网格划分的基础上，利用Z曲线对网格排序并将二维空间中的点映射到一维空间中。考虑到点的分布和网格形状对查询的影响，提出最小查询层和方向变换的概念。只要给出查询点与任意点之间的方向变换，即可求出该点所在的网格Z值，从而求出任意查询层的所有网格Z值。证明了最近邻查询只需访问至最小查询层后再访问两层。基于此提出了最近邻查询算法，它适用于数据点任意分布的情况，该算法能够得到精确解。

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

LIU Runtao1, CHEN Linlin2, TIAN Guangyue2. Nearest neighbor query under grid partition of Z curve[J]. Computer Engineering and Applications, 2013, 49(22): 123-126.

刘润涛1，陈琳琳2，田广悦2. Z曲线网格划分的最近邻查询[J]. 计算机工程与应用, 2013, 49(22): 123-126.

[1]	LAN Hong, HUANG Min. Fusion of KNN Optimized Density Peaks and FCM Clustering Algorithm [J]. Computer Engineering and Applications, 2021, 57(9): 81-88.
[2]	LEI Henglin, Gulanbaier Tuerhong, Mairidan Wushouer, ZHANG Dongmei. Review of Novelty Detection [J]. Computer Engineering and Applications, 2021, 57(5): 47-55.
[3]	WANG Le, HAN Meng, LI Xiaojuan, ZHANG Ni, CHENG Haodong. Review of Classification Methods for Unbalanced Data Sets [J]. Computer Engineering and Applications, 2021, 57(22): 42-52.
[4]	CHEN Qianru, LI Yali, XU Kequan, LIU Yilong, WANG Shuqin. WKNN Feature Selection Method Based on Self-Tuning Adaptive Genetic Algorithm [J]. Computer Engineering and Applications, 2021, 57(20): 164-171.
[5]	MENG Dongxia，LI Yujian. Oversampling Method for Unbalanced Data by Natural Nearest Neighbor [J]. Computer Engineering and Applications, 2021, 57(2): 91-96.
[6]	CAI Ruiguang, ZHANG Desheng, ZHANG Xiao. Bidirectional Selection-Based Pseudo Nearest Neighbor Algorithm [J]. Computer Engineering and Applications, 2021, 57(13): 102-107.
[7]	WANG Caiwen, YANG Youlong. Improved Nearest Neighbor Classification Algorithm for Imbalanced Data [J]. Computer Engineering and Applications, 2020, 56(7): 30-38.
[8]	ZHENG Yi, MA Yingcang, YANG Xiaofei, XU Qiuxia. Sparse Subspace Clustering Based on [k]-Nearest Neighbors and Local Similarity [J]. Computer Engineering and Applications, 2020, 56(4): 99-108.
[9]	WANG Zhen, SUN Fuzhen, ZHANG Longbo, WANG Lei. Ambiguous Ranking Perceptual Hashing [J]. Computer Engineering and Applications, 2020, 56(21): 123-130.
[10]	HUANG Xin, MO Haimiao, ZHAO Zhigang, ZENG Min. Research on Discrete Enhanced Fireworks Algorithm and [kNN] in Feature Selection [J]. Computer Engineering and Applications, 2020, 56(16): 112-117.
[11]	TAN Qing, HUANG Zhangcan. Krill Herd with Nearest Neighbor Lasso Operator [J]. Computer Engineering and Applications, 2019, 55(9): 124-129.
[12]	LI Wenjie, YAN Shiqiang, JIANG Ying, ZHANG Songzhi, WANG Chengliang. Research on Method of Self-Adaptive Determination of DBSCAN Algorithm Parameters [J]. Computer Engineering and Applications, 2019, 55(5): 1-7.
[13]	LIU Yuxin, HE Guanghui. Sparse Subspace Clustering with [k] Nearest Neighbor Constraint [J]. Computer Engineering and Applications, 2019, 55(3): 39-45.
[14]	GONG Yanlu, LV Jia. Co-Training Method Combined with Semi-Supervised Clustering and Weighted [K]-Nearest Neighbor [J]. Computer Engineering and Applications, 2019, 55(22): 114-118.
[15]	GAO Yue, YANG Xiaofei, MA Yingcang, WANG Yirui. Density Peak Clustering Based on Shared [k]-Nearest Neighbors and Shared Reverse Nearest Neighbors [J]. Computer Engineering and Applications, 2019, 55(20): 43-51.

Nearest neighbor query under grid partition of Z curve

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics