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

Mohammad Reza Abbasifard, Hassan Naderi, Mohadese Mirjalili

Abstract


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.


Keywords


Nearest Neighbor search, Dynamic Space, Higher Order Voronoi Diagram

Full Text:

PDF

References


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.


Refbacks

  • There are currently no refbacks.


ISSN: 1694-2507 (Print)

ISSN: 1694-2108 (Online)