HOV-kNN: A New Algorithm to Nearest Neighbor Search in Dynamic Space

Mohammad Reza Abbasifard, Hassan Naderi, Mohadese Mirjalili


Nearest neighbor search is one of the most important problem in computer science due to its numerous applications. Recently, researchers have difficulty to find nearest neighbors in a dynamic space. Unfortunately, in contrast to static space, there are not many works in this new area.  In this paper we introduce a new nearest neighbor search algorithm (called HOV-kNN) suitable for dynamic space due to eliminating widespread preprocessing step in static approaches. The basic idea of our algorithm is eliminating unnecessary computations in Higher Order Voronoi Diagram (HOVD) to efficiently find nearest neighbors. The proposed algorithm can report k-nearest neighbor with time complexity  in contrast to previous work which was . In order to show its accuracy, we have implemented this algorithm and evaluated is using an automatic and randomly generated data point set.


Nearest Neighbor search, Dynamic Space, Higher Order Voronoi Diagram

Full Text:



Lifshits, Y., “Nearest neighbor search: algorithmic perspective”, SIGSPATIAL Special. Vol. 2, No 2, pp. 12-15, 2010.

Shakhnarovich, G., Darrell, T., Indyk, P., “Nearest Neighbor Methods in Learning and Vision: Theory and Practice”, The MIT Press, United States, 2005.

Andoni, A., “Nearest Neighbor Search - the Old, the New, and the Impossible”, Doctor of Philosophy, Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2009.

Bhatia, N., Ashev, V. “Survey of Nearest Neighbor Techniques”, International Journal of Computer Science and Information Security, Vol. 8, No 2, pp.1- 4, 2010.

Dhanabal, S., Chandramathi, S. “A Review of various k-Nearest Neighbor Query Processing Techniques”, Computer Applications, Vol. 31, No 7, pp.14-22, 2011.

Hajebi, K., Abbasi-Yadkori, Y., Shahbazi, H., Zhang, H., “Fast approximate nearest-neighbor search with k-nearest neighbor graph”, In Proceedings of 22 international joint conference on Artificial Intelligence, Vol. 2 (IJCAI'11), Toby Walsh (Ed.),pp.1312-1317, 2011.

Fukunaga, K. Narendra, P. M., “A Branch and Bound Algorithm for Computing k-Nearest Neighbors”, IEEE Transactions on Computer, Vol. 24, No 7, pp.750-753, 1975.

Song, Z., Roussopoulos, N., “K-Nearest Neighbor Search for Moving Query Point”, In Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases (Redondo Beach, California, USA), Springer-Verlag, pp.79-96, 2001.

Güting, R., Behr, T., Xu, J., “Efficient k-Nearest Neighbor Search on moving object trajectories”, The VLDB Journal 19, 5, pp.687-714, 2010.

Frentzos, E., Gratsias, K., Pelekis, N., Theodoridis, Y., “Algorithms for Nearest Neighbor Search on Moving Object Trajectories”, Geoinformatica 11, 2, pp.159-193, 2007.

Berg, M. , Cheong, O. , Kreveld, M., Overmars, M., “Computational Geometry: Algorithms and Applications”, Third Edition, Springer-Verlag., 2008.

Lee, D. T., “On k-Nearest Neighbor Voronoi Diagrams in the Plane”, Computers, IEEE Transactions on Volume:C-31, Issue:6, pp.478–487, 1982.

Fortune, S., “A sweep line algorithm for Voronoi diagrams”, Proceedings of the second annual symposium on Computational geometry, Yorktown Heights, New York, United States, pp.313–322, 1986.

Meyerhenke, H., “Constructing Higher-Order Voronoi Diagrams in Parallel”, Proceedings of the 21st European Workshop on Computational Geometry, Eindhoven, The Netherlands, pp. 123-126, 2005.

Gao, Y., Zheng, B., Chen, G., Li, Q., “Algorithms for constrained k-nearest neighbor queries over moving object trajectories”, Geoinformatica 14, 2, pp. 241-276, April 2010.


  • There are currently no refbacks.

ISSN: 1694-2507 (Print)

ISSN: 1694-2108 (Online)