Computation of shortest distance using query Dependent evolutionary algorithm

Authors(2) :-R Lisanya, K. Prakash

Shortest distance question between two nodes are generally a elementary operation in large-scale networks. Most existing that in among that throughout which at intervals the literature take a landmark embedding approach, that selects a bunch of graph nodes as landmarks and computes the shortest distances from each landmark to any or all or any nodes as an embedding. To handle a shortest distance question between two nodes, the precomputed distances from the landmarks to the question nodes are accustomed cypher an approximate shortest distance supported constellation distinction. throughout this paper, we have a tendency to tend to investigate the factors that have an impact on the accuracy of the house estimation at intervals the landmark embedding approach. significantly we've a bent to tend to hunt out that a globally chosen, query-independent landmark set and in addition the triangulation based distance estimation introduces an oversize relative error, notably for creating able to question nodes. to handle this issue, we've a bent to tend to propose a query-dependent native landmark theme, that identifies a section landmark with regards to the precise question nodes and provides an honest deal of correct distance estimation than the standard international landmark approach. Specifically, an area landmark is written as a results of the tiniest quantity common relative of the two question nodes at intervals the shortest path tree frozen at a worldwide landmark. we've a bent to tend to propose economical native landmark categorization and retrieval techniques, that are crucial to grasp low offline classification quality and on-line question quality. two improvement techniques on graph compression and graph on-line search are planned, with the goal to any deflate index size and improve question accuracy. Our experimental results on large-scale social networks and road networks demonstrate that the native landmark theme reduces the shortest distance estimation error significantly once place next with world landmark embedding

Authors and Affiliations

R Lisanya
M.Tech Student, Department of CSE, Kuppam Engineering College, Kuppam, Andhra Pradesh, India
K. Prakash
Assistant. Prof, Department of CSE, Kuppam Engineering College, Kuppam, Andhra Pradesh, India

Large scale networks, shortest distance query, landmark embedding, indexing and retrieval techniques.

  1. E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959.
  2. P. E. Hart, N. J. Nilsson, and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics SSC4, vol. 4, no. 2, pp. 100-107, 1968.
  3. A. V. Goldberg and C. Harrelson, Computing the shortest path: A* search meets graph theory, in SODA, 2005, pp. 156-165.
  4. A. V. Goldberg, H. Kaplan, and R. F. Werneck, Reach for A*: Efficient point-to-point shortest path algorithms, in Workshop on Algorithm Engineering and Experiments, 2006, pp. 129-143.
  5. P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang, IDMaps: A global internet host distance estimation service, IEEE/ACM Trans. Networking, vol. 9, no. 5, pp. 525-540, 2001.
  6. T. S. E. Ng and H. Zhang, Predicting internet network distance with coordinates-based approaches, in INFOCOM, 2001, pp. 170-179.
  7. C. Shahabi, M. Kolahdouzan, and M. Sharifzadeh, A road network embedding technique for k-nearest neighbor search in moving object databases, in GIS, 2002, pp. 94-100.
  8. J. Kleinberg, A. Slivkins, and T. Wexler, Triangulation and embedding using small sets of beacons, in FOCS, 2004, pp. 444-453.
  9. M. Thorup and U. Zwick, Approximate distance oracles, Journal of the ACM, vol. 52, no. 1, pp. 1-24, 2005.
  10. M. J. Rattigan, M. Maier, and D. Jensen, Using structure indices for efficient approximation of network properties, in KDD, 2006.
  11. H.-P. Kriegel, P. Kr¨oger, M. Renz, and T. Schmidt, Hierarchical graph embedding for efficient query processing in very large traffic networks, in SSDBM, 2008, pp. 150-167.
  12. M. Potamias, F. Bonchi, C. Castillo, and A. Gionis, Fast shortest path distance estimation in large networks, in CIKM, 2009, pp. 867-876.
  13. A. D. Sarma, S. Gollapudi, M. Najork, and R. Panigrahy, A sketchbased distance oracle for web-scale graphs, in WSDM, 2010.
  14. A. Gubichev, S. Bedathur, S. Seufert, and G. Weikum, Fast and accurate estimation of shortest paths in large graphs, in CIKM, 2010.
  15. M. Qiao, H. Cheng, and J. X. Yu, “Querying shortest path distance with bounded errors in large graphs, in SSDBM, 2011.
  16. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  17. M. A. Bender and M. Farach-Colton, The LCA problem revisited, in LATIN 2000: Theoretical Informatics, ser. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, vol. 1776, pp. 88-94.
  18. A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, Measurement and analysis of online social networks, in IMC, 2007, pp. 29-42.
  19. J. Sankaranarayanan, H. Samet, and H. Alborzi, Path oracles for spatial networks, PVLDB, vol. 2, no. 1, 2009, pp. 1210-1221.
  20. D. Wagner, T. Willhalm, and C. D. Zaroliagis, Geometric containers for efficient shortest-path computation, ACM Journal of Experimental Algorithmics, vol. 10, 2005.
  21. D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao, Query processing in spatial network database, in VLDB, 2003, pp. 802-813.
  22. M. Kolahdouzan and C. Shahabi, Voronoi-based k nearest neighbor search for spatial network databases, in VLDB, 2004, pp. 840-851.
  23. H. Hu, D. L. Lee, and V. C. S. Lee, Distance indexing on road networks, in VLDB, 2006, pp. 894-905.
  24. H. Samet, J. Sankaranarayanan, and H. Alborzi, Scalable network distance browsing in spatial databases, in SIGMOD, 2008, pp. 43-54.
  25. F. Wei, TEDI: Efficient shortest path query answering on graphs, in SIGMOD, 2010, pp. 99-110.

Publication Details

Published in : Volume 3 | Issue 5 | May-June 2018
Date of Publication : 2018-06-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 1023-1028
Manuscript Number : CSEIT1835214
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

R Lisanya, K. Prakash, "Computation of shortest distance using query Dependent evolutionary algorithm", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 3, Issue 5, pp.1023-1028, May-June-2018.
Journal URL :

Article Preview