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

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Article:A Review of various k-Nearest Neighbor Query Processing Techniques

by S. Dhanabal, Dr. S. Chandramathi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 31 - Number 7
Year of Publication: 2011
Authors: S. Dhanabal, Dr. S. Chandramathi
10.5120/3836-5332

S. Dhanabal, Dr. S. Chandramathi . Article:A Review of various k-Nearest Neighbor Query Processing Techniques. International Journal of Computer Applications. 31, 7 ( October 2011), 14-22. DOI=10.5120/3836-5332

@article{ 10.5120/3836-5332,
author = { S. Dhanabal, Dr. S. Chandramathi },
title = { Article:A Review of various k-Nearest Neighbor Query Processing Techniques },
journal = { International Journal of Computer Applications },
issue_date = { October 2011 },
volume = { 31 },
number = { 7 },
month = { October },
year = { 2011 },
issn = { 0975-8887 },
pages = { 14-22 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume31/number7/3836-5332/ },
doi = { 10.5120/3836-5332 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:17:30.699793+05:30
%A S. Dhanabal
%A Dr. S. Chandramathi
%T Article:A Review of various k-Nearest Neighbor Query Processing Techniques
%J International Journal of Computer Applications
%@ 0975-8887
%V 31
%N 7
%P 14-22
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Identifying the queried object, from a large volume of given uncertain dataset, is a tedious task which involves time complexity and computational complexity. To solve these complexities, various research techniques were proposed. Among these, the simple, highly efficient and effective technique is, finding the K-Nearest Neighbor (kNN) algorithm. It is a technique which has applications in various fields such as pattern recognition, text categorization, moving object recognition etc. Different kNN techniques are proposed by various researchers under various situations. In this paper, we classified these techniques into two ways: (1) structure based (2) non-structure based kNN techniques. The aim of this paper is to analyze the key idea, merits, demerits and target data behind each kNN techniques. The structure based kNN techniques such as Ball Tree, k-d Tree, Principal Axis Tree (PAT), Orthogonal Structure Tree (OST), Nearest Feature Line (NFL), Center Line (CL) and Non-structured kNN techniques such as Weighted kNN, Condensed NN, Model based k-NN, Ranked NN (RNN), Pseudo/Generalized NN, Clustered k-NN(CkNN), Mutual kNN (MkNN), Constrained RkNN etc., are analyzed in this paper. It is observed that the structure based kNN techniques suffer due to memory limit whereas the Non-structure based kNN techniques suffer due to computation complexity. Hence, structure based kNN techniques can be applied to small volume of data whereas Non-structure kNN techniques can be applied to large volume of data.

References
  1. V.Vaidehi, S.Vasuhi, “ Person Authentication using Face Recognition”, Proceedings of the world Congress on Engineering and Computer Science, 2008.
  2. Shizen, Y. Wu, “An Algorithm for Remote Sensing Image Classification based on Artificial Immune b-cell Network”, Springer Berlin, Vol 40.
  3. G. Toker, O. Kirmemis, “Text Categorization using k Nearest Neighbor Classification”, Survey Paper, Middle East Technical University.
  4. Y. Liao, V. R. Vemuri, “Using Text Categorization Technique for Intrusion detection”, Survey Paper, University of California.
  5. E. M. Elnahrawy, “Log Based Chat Room Monitoring Using Text Categorization: A Comparative Study”, University of Maryland.
  6. X. Geng et. al, “Query Dependent Ranking Using k Nearest Neighbor”, SIGIR, 2008.
  7. F. Bajramovie et. al “A Comparison of Nearest Neighbor Search Algorithms for Generic Object Recognition”, ACIVS 2006, LNCS 4179, pp 1186-1197.
  8. Y. Yang and T. Ault, “Improving Text Categorization Methods for event tracking”, Carnegie Mellon University.
  9. T.M.Cover and P.E. Hart, “Nearest Neighbor Pattern Classification”, IEEE Trans. Inform. Theory, Vol. IT-13, pp 21-27, Jan 1967.
  10. Berchtold, S., Ertl, B., Keim, D.A., Kriegel, H.P., Seidl, T.“Fast nearest neighbor search in high-dimensional space” in Proceedings of the International Conference on Data Engineering, pp. 209–218 (1998)
  11. Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 71–79 (1995)
  12. Guttman, A.: R-trees: A dynamic index structure for spatial searching. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 47–57 (1984)
  13. Cheung, K.L., Fu, A.W.-C.: Enhanced nearest neighbor search on the R-tree. ACM SIGMOD Record 27(3), 16–21 (1998)
  14. Katayama, N., Satoh, S.: The SR-tree: An index structure for high-dimensional nearest neighbor queries. In: Proceedings of the ACM SIGMOD International Conference on Management of Data,pp.369–380(1997)
  15. Henrich, A.: A distance scan algorithm for spatial access structures. In: Proceedings of the Second ACM Workshop on Geographic Information Systems, pp. 136–143 (1994)
  16. Hjaltason, G.R., Samet, H.: Distance browsing in spatial databases. ACM Trans. Database Sys. 24(2), 265–318 (1999)
  17. Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*- tree: An efficient and robust access method for points and rectangles. In: Proceedings of the ACM SIGMOD International Conference On Management of Data, pp. 322–331 (1990)
  18. Seidl, T., Kriegel, H.P.: Optimal multi-step k-nearest neighbor search. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 154–165 (1998)
  19. T. Liu, A. W. Moore, A. Gray, “New Algorithms for Efficient High Dimensional Non-Parametric Classification”, Journal of Machine Learning Research, 2006, pp 1135-1158.
  20. S. N. Omohundro, “Five Ball Tree Construction Algorithms”, 1989, Technical Report.
  21. R. F Sproull, “Refinements to Nearest Neighbor Searching”, Technical Report, International Computer Science, ACM (18) 9, pp 507-517. International Journal of Computer Science and Information Security,Vol. 8, No. 2, 2010
  22. S. Z Li, K. L. Chan, “Performance Evaluation of The NFL Method in Image Classification and Retrieval”, IEEE Trans On Pattern Analysis and Machine Intelligence, Vol 22, 2000.
  23. W. Zheng, L. Zhao, C. Zou, “Locally Nearest Neighbor Classifier for Pattern Classification”, Pattern Recognition, 2004, pp 1307-1309.
  24. Y. Zhou, C. Zhang, “Tunable Nearest Neighbor Classifier”, DAGM 2004, LNCS 3175, pp 204-211.
  25. Q. B. Gao, Z. Z. Wang, “Center Based Nearest Neighbor Class”, Pattern Recognition, 2007, pp 346-349.
  26. Y. C. Liaw, M. L. Leou, “Fast Exact k Nearest Neighbor Search using Orthogonal Search Tree”, Pattern Recognition 43 No. 6, pp 2351-2358.
  27. J.Mcname, “Fast Nearest Neighbor Algorithm based on Principal Axis Search Tree”, IEEE Trans on Pattern Analysis and Machine Intelligence, Vol 23, pp 964-976.
  28. Kollios, G., Gunopulos, D., Tsotras, V.J.: Nearest neighbor queries in a mobile environment. In: Proceedings of the International Workshop on Spatio-Temporal Database Management, pp. 119–134 (1999)
  29. Albers, G., Guibas, L.J., Mitchell J.S.B, Roos, T.: Voronoi Diagrams of moving points. Int. J. Comput. Geom. Appl. 8(3), 365– 380 (1998)
  30. Song, Z., Roussopoulos, N.: K-nearest neighbor search for moving query point. In: Proceedings of the International Symposium on Spatial and Temporal Databases, pp. 79–96 (2001)
  31. Raptopoulou, K., Papadopoulos, A., Manolopoulos, Y.: Fast nearest-neighbor query processing in moving-object databases. GeoInformatica 7(2), 113–137(2003)
  32. Tao, Y., Papadias, D.: Spatial queries in dynamic environments. ACM TODS 28(2), 101–139 (2003)
  33. T. Bailey and A. K. Jain, “A note on Distance weighted k-nearest neighbor rules”, IEEE Trans. Systems, Man Cybernatics, Vol.8, pp 311-313, 1978.
  34. E Alpaydin, “Voting Over Multiple Condensed Nearest Neighbors”, Artificial Intelligent Review 11:115-132, 1997.
  35. Geoffrey W. Gates, “Reduced Nearest Neighbor Rule”, IEEE Trans Information Theory, Vol. 18 No. 3, pp 431-433.
  36. G. Guo, H. Wang, D. Bell, “KNN Model based Approach in Classification”, Springer Berlin Vol 2888.
  37. S. C. Bagui, S. Bagui, K. Pal, “Breast Cancer Detection using Nearest Neighbor Classification Rules”, Pattern Recognition 36, pp 25-34, 2003.
  38. H. Parvin, H. Alizadeh and B. Minaei, “Modified k Nearest Neighbor”, Proceedings of the world congress on Engg. and computer science 2008.
  39. Y. Zeng, Y. Yang, L. Zhou, “Pseudo Nearest Neighbor Rule for Pattern Recognition”, Expert Systems with Applications (36) pp 3587-3595, 2009.
  40. Z. Yong, “An Improved kNN Text Classification Algorithm based on Clustering”, Journal of Computers, Vol. 4, No. 3, March 2009.
  41. Stanoi, I., Agrawal, D., El Abbadi, A.: Reverse nearest neighbor queries for dynamic databases. In: Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pp. 44–53 (2000)
  42. Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 201–212 (2000)
  43. Yang, C., Lin, K.-Ip.: An index structure for efficient reverse nearest neighbor queries. In: Proceedings of the International Conference on Data Engineering, pp. 485–492 (2001)
  44. Maheshwari, A., Vahrenhold, J., Zeh, N.: On reverse nearest neighbor queries. In: Proceedings of the Canadian Conference on Computational Geometry, pp. 128–132 (2002)
  45. Singh, A., Ferhatosmanoglu, H., Tosun, A.: High dimensional reverse nearest neighbor queries. In: Proceedings of ACM CIKM International Conference on Information and Knowledge Management, pp. 91–98 (2003)
  46. Tao, Y., Papadias, D., Lian, X.: Reverse kNN search in arbitrary dimensionality In: Proceedings of the VLDB Conference, pp. 744–755 (2004)
  47. T. Xia and D. Zhang. Continuous reverse nearest neighbor monitoring. In :Processings of the IEEE International Conference on Data Engineering. 2006.
  48. Tobias Emrich, Hans-Peter Kriegel, Peer Kröger, Matthias Renz, and Andreas Züfle,” Constrained Reverse Nearest Neighbor Search on Mobile Objects “,ACM GIS ’09 , November 4-6, 2009
  49. Dimitris Papadias,Yufei Tao, Kyriakos Mouratidis and Chun Kit Hui ,“ Aggregate Nearest Neighbor Queries in Spatial Databases”, In: Proceedings of ACM Transactions on Database Systems, Vol. 30, No. 2, June 2005, Pages 529–576.
  50. Yunjun Gao, Baihua Zheng, Gencai Chen, Qing Li, Chun Chen and Gang Chen “On efficient mutual nearest neighbor query processing in spatial databases” ,Elsievier Data & Knowledge Engineering, Vol. 68, May 2009, Pages 70.
Index Terms

Computer Science
Information Sciences

Keywords

Query processing Nearest Neighbor kNN

Powered by PhDFocusTM