A Forward Moving Method for Continuous Nearest Neighbor Queries

Abstract:

A continuous nearest neighbor (CNN) query retrieves the nearest neighbor of every point on a line segment and indicates its valid segments. Zheng et al. have proposed a Hilbert-curve index for the CNN query. This method contains two phases, searching candidates in the approximate search range, and filtering the candidates to get the final answer. However, it may determine a wide search range in the first phase based on this method, resulting in the decrease of the accuracy and the increase of the processing time. Therefore, in this paper, to avoid this disadvantage, we propose a forward moving method to efficiently support the CNN queries. The proposed method locally expands the search range along the query line segment to find the neighbors. Experimental results show that our method outperforms Zheng et al.’s method in terms of the accuracy and the processing time.

• Periodical: Applied Mechanics and Materials (Volumes 284-287)
• Pages: 2965-2969
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.284-287.2965
• Online since: January 2013
• Authors: Jun Hong Shen, Ye In Chang, Chen Chang Wu, Ta Wei Liu
• Keywords: Continuous Nearest Neighbor, Space Filling Curves, Spatial Databases

References

[1] H.L. Chen and Y.I. Chang: Neighbor-finding based on space-filling curves, Information Systems 30(3) (2005) 205-226.

DOI: 10.1016/j.is.2003.12.002

[2] H. L. Chen and Y. I. Chang: All-nearest-neighbors finding based on the Hilbert curve, Expert Systems with Applications 38(6) (2011) 7462-7475.

DOI: 10.1016/j.eswa.2010.12.077

[3] Y. Gao, B. Zheng, G. Chen, Q. Li and X. Guo: Continuous visible nearest neighbor query processing in spatial databases, The VLDB Journal 20(3) (2011) 371-396.

DOI: 10.1007/s00778-010-0200-z

[4] R.H. Guting: An introduction to spatial database systems, The VLDB Journal 3(4) (1994) pp.1-32.

[5] T. Imielinski, S. Viswanathan, and B. R. Badrinath: Data on air: organization and access, IEEE Trans. on Knowledge and Data Eng., 9(3) (1997) 353-372.

DOI: 10.1109/69.599926

[6] Y. Tao, D. Papadias and Q. Shen: Continuous nearest neighbor search, Proc. of the 28th Conf. on Very Large Data Base (2002) 287-298.

DOI: 10.1016/b978-155860869-6/50033-0

[7] B. Zheng, Lee, W.C. Lee, and D.L. Lee: Search continuous nearest neighbor on the air, Proc. of the 1st Annual Int. Conf. on Mobile and Ubiquitous Systems: Networking and Services (2004) 236-245.

DOI: 10.1109/mobiq.2004.1331730