CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Developments in KD Tree and KNN Searches

by Vijay R. Tiwari
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 185 - Number 17
Year of Publication: 2023
Authors: Vijay R. Tiwari
10.5120/ijca2023922879

Vijay R. Tiwari . Developments in KD Tree and KNN Searches. International Journal of Computer Applications. 185, 17 ( Jun 2023), 17-23. DOI=10.5120/ijca2023922879

@article{ 10.5120/ijca2023922879,
author = { Vijay R. Tiwari },
title = { Developments in KD Tree and KNN Searches },
journal = { International Journal of Computer Applications },
issue_date = { Jun 2023 },
volume = { 185 },
number = { 17 },
month = { Jun },
year = { 2023 },
issn = { 0975-8887 },
pages = { 17-23 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume185/number17/32787-2023922879/ },
doi = { 10.5120/ijca2023922879 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T01:26:19.947168+05:30
%A Vijay R. Tiwari
%T Developments in KD Tree and KNN Searches
%J International Journal of Computer Applications
%@ 0975-8887
%V 185
%N 17
%P 17-23
%D 2023
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. 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.
  3. 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
  4. Brown, R.A. 2015. Building a balanced k - d Tree in O
  5. kn
  6. log
  7. n
  8. Time. Journal of Computer Graphics Techniques (JCGT), vol. 4, no. 1. pp. 50-68.
  9. 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
  10. Cover, T.M. and Hart, P.E. 1967. Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), pp. 21-27.
  11. 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.
  12. 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.
  13. 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.
  14. Hoare, C. A. R. 1962. Quicksort. The Computer Journal 5. pp. 10-15. doi: 10.1093/comjnl/5.1.10. 51
  15. 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.
  16. 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.
  17. 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.
  18. Knuth, D.E. 1973. The art of computer programming Volume III: Sorting and Searching. Addison - Wesley, Reading, Mass.
  19. 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.
  20. 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.
  21. Mitchell, T. M. 1997. Machine Learning. McGraw-Hill Science/Engineering/Math. ISBN: 0070428077
  22. 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.
  23. Necaise, R.D. n. d. Data Structures and Algorithms using python. Wiley Student edition.
  24. 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
  25. 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.
  26. 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.
  27. Williams, J. 1964. Heapsort (algorithm 232). Communications of the ACM 7. pp. 347-348.
  28. 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.
  29. 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.
  30. Barnwal, A. 2022. K Dimensional Tree | Set 1 (Search and Insert).https://www.geeksforgeeks.org/k-dimensional-tree/
  31. Black, P. E. 2019. Big - O notation. Dictionary of Algorithms and DataStructures. https://www.nist.gov/dads/HTML/bigOnotation.html
  32. Couto, D. D, and Napoli, J. 1998.  kD Trees.http://groups.csail.mit.edu/graphics/classes/6.838/S98/meetings/m13/kd.html
  33. 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-
  34. Hachcham, A. 2023. The KNN Algorithm – Explanation, Opportunities, Limitations.https://neptune.ai/blog/knn-algorithm-explanation-opportunities-limitations
  35. 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
  36. MATWORKS from MATLAB. 2022. Classification Using Nearest Neighbors. https://in.mathworks.com/help/stats/classification-using-nearest-neighbors.html
  37. 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
  38. Padmaja, B. 2018. Lecture Notes on Data Structures.https://www.iare.ac.in/sites/default/files/lecture_notes/IARE_DS_LECTURE_NOTES_2.pdf
Index Terms

Computer Science
Information Sciences

Keywords

KNN search KD tree Supervised Machine Learning KNN-KD tree Point Cloud Data.

Powered by PhDFocusTM