An Efficient Approach for Search Engine Using KNN Search

Authors

  • Vignesh V  Department of Computer Science and Engineering, Dhanalakshmi College of Engineering, Chennai, Tamilnadu, India
  • Suganth R  Department of Computer Science and Engineering, Dhanalakshmi College of Engineering, Chennai, Tamilnadu, India
  • Ramesh Kannan C  Department of Computer Science and Engineering, Dhanalakshmi College of Engineering, Chennai, Tamilnadu, India

Keywords:

KNN, Geo, Bit Array Construction

Abstract

Data mining techniques are the result of a long process of research and product development. This evolution began when business data were first stored on computers, continued with improvements in data access, and more recently, generated technologies that allow users to navigate through their data in real time. Data mining takes this evolutionary process beyond retrospective data access and navigation to prospective and proactive information delivery. We focus on a typical query called the KNN query. Formally, given a point-of-interest dataset P and a road network G, the KNN query reports k points such that their shortest path distances distN(q, p) from q are minimized.

References

  1. L. A. Barroso, J. Dean, and U. Heolzle, "Web search for a planet: The google cluster architecture," IEEE Micro, vol. 23, no. 2, pp. 22–28, Mar.-Apr. 2003.
  2. R. A. Baeza-Yates, C. Castillo, F. Junqueira, V. Plachouras, and F. Silvestri, "Challenges on distributed web retrieval," in Proc. IEEE 23rd Int. Conf. Data Eng, 2007, pp. 6–20.
  3. R. A. Baeza-Yates, "Towards a distributed search engine," in Proc. 7th Int. Conf. Algorithms Complexity, 2010, pp. 1–5.
  4. S. Nutanong and H. Samet, "Memory-efficient algorithms for spatial network queries," in Proc. IEEE 29th Int. Conf. Data Eng., 2013, pp. 649–660.
  5. H. Hu, D. L. Lee, and J. Xu, "Fast nearest neighbor search on road networks," in Proc. 10th Int. Conf. Extending Database Technol., 2006, pp. 186–203.
  6. K. C. K. Lee, W.-C. Lee, B. Zheng, and Y. Tian, "Road: A new spatial object search framework for road networks," IEEE Trans. Knowl. Data Eng., vol. 24, no. 3, pp. 547–560, Mar. 2012.
  7. D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao, "Query processing in spatial network databases," in Proc. 29th Int. Conf. Very Large Data Bases, 2003, pp. 802–813.
  8. K. Deng, X. Zhou, H. T. Shen, S. W. Sadiq, and X. Li, "Instance optimal query processing in spatial networks," VLDB J., vol. 18, no. 3, pp. 675–693, 2009.
  9. R. Zhong, G. Li, K.-L. Tan, and L. Zhou, "G-tree: An efficient index for knn search on road networks," in Proc. 22nd ACM Int. Conf. Inform. Knowl. Manage., 2013, pp. 39–48.
  10. H. Samet, J. Sankaranarayanan, and H. Alborzi, "Scalable network distance browsing in spatial databases," in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2008, pp. 43–54.
  11. H. Hu, D. L. Lee, and V. C. S. Lee, "Distance indexing on road networks," in Proc. 32nd Int. Conf. Very Large Data, 2006, pp. 894–905.
  12. M. R. Kolahdouzan and C. Shahabi, "Voronoi-based k nearest neighbor search for spatial network databases," in Proc. 13th Int. Conf. Very Large, 2004, pp. 840–851.
  13. A. V. Goldberg and C. Harrelson, "Computing the shortest path: A search meets graph theory," in Proc. 16th Annu. ACM-SIAM Symp. Discrete Algorithms, 2005, pp. 156–165.
  14. J. M. Kleinberg, A. Slivkins, and T. Wexler, "Triangulation and embedding using small sets of beacons," J. ACM, vol. 56, no. 6, pp. 32:1–32:37, 2009.
  15. I. Abraham, A. Fiat, A. V. Goldberg, and R. F. F. Werneck, "Highway dimension, shortest paths, and provably efficient algorithms," in Proc. 21st Annu. ACM-SIAM Symp. Discrete Algorithms, 2010, pp. 782–793.
  16. R. Mertens, T. Steffens, and J. Stachowiak, "Path searching with transit nodes in fast changing telecommunications networks," in Proc. GI Jahrestagung, 2008, pp. 158–163.
  17. R. Geisberger, P. Sanders, D. Schultes, and D. Delling, "Contraction hierarchies: Faster and simpler hierarchical routing in road networks," in Proc. 7th Int. Conf. Exp. Algorithms, 2008, pp. 319–333.
  18. R. J. Gutman, "Reach-based routing: A new approach to shortest path algorithms optimized for road networks," in Proc. 6th Workshop Algorithm Eng. Exp., 2004, pp. 100–111.
  19. R. Bauer and D. Delling, "Sharc: Fast and robust unidirectional routing," in Proc. Workshop Algorithm Eng. Exp., 2008, pp. 13–26.
  20. A. D. Zhu, H. Ma, X. Xiao, S. Luo, Y. Tang, and S. Zhou, "Shortest path and distance queries on road networks: towards bridging theory and practice," in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2013, pp. 857–868.

International Journal of Scientific Research in Science, Engineering and Technology

Downloads

Published

2017-12-31

Issue

Volume 2, Issue 2, March-April-2016

Section

Research Articles

License

Copyright (c) IJSRSET

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Vignesh V, Suganth R, Ramesh Kannan C, " An Efficient Approach for Search Engine Using KNN Search, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 2, Issue 2, pp.520-523, March-April-2016.