A Logarithmic-Complexity Algorithm for Nearest Neighbor Classification Using Layered Range Trees

Ibrahim Al-Bluwi, Ashraf Elnagar

Department of Computer Science, University of Sharjah, Sharjah, UAE.
Laboratory for Analysis and Architecture of Systems (LAAS-CNRS), Universitt’e de Toulouse, Toulouse, France.

DOI: 10.4236/iim.2012.42006                

Abstract

Finding Nearest Neighbors efficiently is crucial to the design of any nearest neighbor classifier. This paper shows how Layered Range Trees (LRT) could be utilized for efficient nearest neighbor classification. The presented algorithm is robust and finds the nearest neighbor in a logarithmic order. The proposed algorithm reports the nearest neighbor in , where k is a very small constant when compared with the dataset size n and d is the number of dimensions. Experimental results demonstrate the efficiency of the proposed algorithm.

Keywords

Nearest Neighbor Classifier; Range Trees; Logarithmic Order

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	T. Cover and P. Hart, “Nearest Neighbor Pattern Classifica-tion,” IEEE Transactions on Information Theory, Vol. 13, No. 1, 1967, pp. 21-27. doi:10.1109/TIT.1967.1053964
[2]	Y. Gao, B. Zheng, G. Chen, Q. Li, C. Chen and G. Chen, “Efficient Mutual Nearest Neighbor Query Processing for Moving Object Trajectorie,” Information Sciences, Vol. 180, No. 11, 2010, pp. 2176-2195. doi:10.1016/j.ins.2010.02.010
[3]	H. W. Liu, S. C. Zhang, J. M. Zhao, X. F. Zhao and Y. C. Mo, “A New Classification Algorithm Using Mutual Nearest Neighbors,” 9th International Conference on Grid and Cooperative Computing (GCC), Nan-jing, 1-5 November 2010, pp. 52-57.
[4]	M. Z. Jahromi, E. Parvinnia and R. John, “A Method of Learning Weighted Similarity Function to Improve the Performance of Nearest Neighbor,” Information Sciences, Vol. 179, No. 17, 2009, pp. 2964-2973. doi:10.1016/j.ins.2009.04.012
[5]	J. Toyama, M. Kudo and H. Imai, “Probably Correct k-Nearest Neighbor Search in High Dimensions,” Pattern Recognition, Vol. 43, No. 4, 2010, pp. 1361-1372. doi:10.1016/j.patcog.2009.09.026
[6]	H. A. Fayed and A. F. Atiya, “A Novel Template Reduction Approach for the k-Nearest Neighbor Method,” IEEE Transactions on Neural Networks, Vol. 20, No. 5, 2009, pp. 890-896. doi:10.1109/TNN.2009.2018547
[7]	F. P. Preparata and M. I. Shamos, “Computational Geometry: An Introduction,” Springer, Berlin, 1985.
[8]	J. L. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Communica-tions of ACM, Vol. 18, No. 9, 1975, pp. 509-517. doi:10.1145/361002.361007
[9]	A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” SIGMOD’84 Proceedings of the 1984 ACM SIGMOD International Confer-ence on Management of Data, Vol. 14, No. 2, 1984, pp. 47-57.
[10]	J. H. Freidman, J. L. Bentley and R. A. Finkel, “An Algorithm for Finding Best Matches in Logarithmic Ex-pected Time,” ACM Transactions on Mathematical Software (TOMS), Vol. 3, No. 3, 1977, pp. 209-226. doi:10.1145/355744.355745
[11]	G. S. Lueker, “A Data Structure for Orthogonal Range Queries,” Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science, Ann Arbor, 16-18 October 1978, pp. 28-34.
[12]	D. E. Willard, “New Data Structures for Orthogonal Range Queries,” SIAM Journal on Computing, Vol. 14, No. 1, 1985, pp. 232-253. doi:10.1137/0214019
[13]	B. Chazelle and L. J. Guibas, “Fractional Cascading: A Data Structuring Technique with Geometric Applications,” Proceedings of the 12th Colloquium on Automata, Languages and Programming, Vol. 194, 1985, pp. 9-100. doi:10.1007/BFb0015734
[14]	S. A. Nene and S. K. Nayar, “A Simple Algorithm for Nearest Neighbor Search in High Di-mensions,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 9, 1997, pp. 989-1003. doi:10.1109/34.615448
[15]	M. de Berg, M. de Kreveld and M. Overmars, “Computational Geometry: Algorithms and Applications,” Springer, Berlin, 2000.