Abstract

KNN (K-nearest neighbor) is an important tool in machine learning and it is used in classification and prediction problems. In recent years several modified versions of KNN search algorithm have been developed and employed to improve the efficiency of search. KNN has enormous real life applications and is widely used in data mining. Data structures like KD tree (or K dimensional tree) are used for implementing KNN effectively. A KD tree is a multidimensional binary search tree that can be balanced or unbalanced. With the increase in dimension of space the computational time of KNN-KD search goes high. Certain modifications that can help in improvising the search time has been developed in recent years.

References

• Andoni, A. 2009. Nearest Neighbor Search: the Old, the New, and the Impossible. Doctoral dissertation, Massachusetts Institute of Technology. https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=4b4e7e0419644e9130666ed6e3ba8beee77ffa4e
• Atallah, M. J., and Blanton, M.  2009. Algorithms and Theory of Computation Handbook, Second Edition, volume 1: General Concepts and Techniques. Chapman & Hall / CRC Applied Algorithms and Data Structures series Edition: 2. ISBN: 1584888229; 9781584888222.
• Bently, J. L. 1975. Multidimensional Binary Search Trees used for Associative Searching. Communications of the ACM, 18(9). pp. 509-517. 517. doi:10.1145/361002.361007
• Brown, R.A. 2015. Building a balanced k - d Tree in O
• kn
• log
• n
• Time. Journal of Computer Graphics Techniques (JCGT), vol. 4, no. 1. pp. 50-68.
• Cost, S., and Salzberg, S. 1993. A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features. Machine learning 10. pp. 57-78. doi: 10.1023/A:1022664626993
• Cover, T.M. and Hart, P.E. 1967. Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), pp. 21-27.
• Eibe, F., Hall, M., and Pfahringer, B. 2003. Locally Weighted Naïve Bayes. In Proceedings of the Conference on Uncertainty in Artificial Intelligence. pp. 249–256. Morgan Kaufmann.
• Goldstine, H., and Von Neumann, J. 1963. Coding of some combinatorial (sorting) problems. In John von Neumann Collected works Design of computers, Theory 66 of Automata and Numerical Analysis, A. Taub, Ed., vol. 5. Pergamon Press Ltd. and the Macmillan company, New York NY. pp. 196-214.
• Han, E., Karypis, G., and Kumar, V. 2001. Text Categorization Using Weight Adjusted k-Nearest Neighbor Classification. Pacific-Asia Conference on Knowledge Discovery and Data Mining.
• Hoare, C. A. R. 1962. Quicksort. The Computer Journal 5. pp. 10-15. doi: 10.1093/comjnl/5.1.10. 51
• Hou, W., Li, D., Xu, C., Zhang, H., and Li, T. 2018. An Advanced k Nearest Neighbor Classification Algorithm Based on KD-tree. IEEE International Conference of Safety Produce Informatization (IICSPI), Chongqing, China, pp. 902-905. doi: 10.1109/IICSPI.2018.8690508.
• Jiang, L., Cai, Z., Wang, D., and Jiang, S. 2007. Survey of Improving K-Nearest-Neighbor for Classification. Fourth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2007), Haikou, China, pp. 679-683. doi: 10.1109/FSKD.2007.552.
• Jiang, L., Zhang, H., and Cai, Z. 2006. Dynamic K-Nearest-Neighbor Naive Bayes with Attribute Weighted. International Conference on Fuzzy Systems and Knowledge Discovery. pp. 365–368. Springer, 2006.
• Knuth, D.E. 1973. The art of computer programming Volume III: Sorting and Searching. Addison - Wesley, Reading, Mass.
• Kohavi, R. 1996. Scaling up the accuracy of Naïve-Bayes Classifier: A decision tree hybrid. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. pp. 202–207. AAAI Press.
• Lowe, D.G. 1995. Similarity metric learning for a variable-kernel classifier. Neural computation, vol. 7, no. 1. pp. 72-85. doi: 10.1162/neco.1995.7.1.72.
• Mitchell, T. M. 1997. Machine Learning. McGraw-Hill Science/Engineering/Math. ISBN: 0070428077
• Mohammad Reza, A., Bijan, G., and Hassan, N. 2014. A Survey on Nearest Neighbor Search Methods. International Journal of Computer Applications. 95. pp. 39-52. doi: 10.5120/16754-7073.
• Necaise, R.D. n. d. Data Structures and Algorithms using python. Wiley Student edition.
• Panigrahy, R. 2008. An Improved Algorithm Finding Nearest Neighbor Using Kd-trees. In: laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008; Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg.doi: 10.1007/978-3-540-78773-0_34
• Priyanka, T., and Swamy, N. N. 2015. KNN Based Document Classifier Using Kd Tree: An Efficient Implementation. International Journal of Computer Science & Communication Networks, 5(5). pp. 270-274.
• Silverman, B. W., and Jones, M. C. 1989. E. Fix and J.L. Hodges (1951): An Important Contribution to Nonparametric Discriminant Analysis and Density Estimation: Commentary on Fix and Hodges. International Statistical Review / Revue Internationale de Statistique, vol. 57, no. 3, 1989, pp. 233–238. doi: 10.2307/1403796.
• Williams, J. 1964. Heapsort (algorithm 232). Communications of the ACM 7. pp. 347-348.
• Xie, Z., Hsu, W., Liu, Z., and Lee, M. 2002. SNNB: A Selective Neighborhood Based Naïve Bayes for Lazy Learning. In Proceedings of the Sixth Pacific-Asia Conference on KDD. pp. 104–114. Springer. doi: 10.1007/3-540-47887-6_10.
• Zhai, H. 2022. Improving KNN Algorithm Efficiency Based on PCA and KD-tree. International Conference on Machine Learning and Knowledge Engineering (MLKE), Guilin, China, pp. 83-87. doi: 10.1109/MLKE55170.2022.00021.
• Barnwal, A. 2022. K Dimensional Tree | Set 1 (Search and Insert).https://www.geeksforgeeks.org/k-dimensional-tree/
• Black, P. E. 2019. Big - O notation. Dictionary of Algorithms and DataStructures. https://www.nist.gov/dads/HTML/bigOnotation.html
• Couto, D. D, and Napoli, J. 1998.  kD Trees.http://groups.csail.mit.edu/graphics/classes/6.838/S98/meetings/m13/kd.html
• Dey, S. 2017. Implementing kd-tree for fast range-search, nearest-neighbor search and k-nearest-neighbor search algorithms in 2D (with applications in simulating the flocking boids: modeling the motion of a flock of birds and in learning a kNN classifier: a supervised ML model for binary classification) in Java and python.https://sandipanweb.wordpress.com/2017/09/10/implementing-kd-trees-along-with-the-fast-range-search-nearest-neighbor-search-and-k-nearest-neighbor-search-algorithms-in-2d-with-
• Hachcham, A. 2023. The KNN Algorithm – Explanation, Opportunities, Limitations.https://neptune.ai/blog/knn-algorithm-explanation-opportunities-limitations
• Kang, Q., Huang, G. M., and Yang, S.C. 2018. A Gross Error Elimination Method for Point Cloud data based on KD-Tree. ISPRS-International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2018, 719-722. https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLII-3/719/2018/isprs-archives-XLII-3-719-2018.pd
• MATWORKS from MATLAB. 2022. Classification Using Nearest Neighbors. https://in.mathworks.com/help/stats/classification-using-nearest-neighbors.html
• Mount, D. 2021.CMSC 420: Lecture 13 Answering Queries with kd-trees.https://www.cs.umd.edu/class/spring2021/cmsc420-0101/Lects/lect13-kd-query.pdf
• Padmaja, B. 2018. Lecture Notes on Data Structures.https://www.iare.ac.in/sites/default/files/lecture_notes/IARE_DS_LECTURE_NOTES_2.pdf