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

Show more

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.