An Efficient Approach for Search Engine Using KNN Search

Authors(3) :-Vignesh V, Suganth R, Ramesh Kannan C

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.

Authors and Affiliations

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

KNN, Geo, Bit Array Construction

  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.

Publication Details

Published in : Volume 2 | Issue 2 | March-April 2016
Date of Publication : 2017-12-31
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 520-523
Manuscript Number : IJSRSET1622155
Publisher : Technoscience Academy

Print ISSN : 2395-1990, Online ISSN : 2394-4099

Cite This Article :

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.
Journal URL : http://ijsrset.com/IJSRSET1622155

Article Preview

Follow Us

Contact Us