Survey of Approximate Shortest Distance Computing Using Improved Shortest Path Tree
International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
www.ijsr.net | Open Access | Fully Refereed | Peer Reviewed International Journal

ISSN: 2319-7064

Survey Paper | Computer Science & Engineering | India | Volume 3 Issue 11, November 2014

Survey of Approximate Shortest Distance Computing Using Improved Shortest Path Tree

Sonali Malode, Mansi Bhonsle

In large scale network, shortest distance query is a primary operation. In literature there is a number of existing systems presented that take a landmark embedding approach. These systems select a set of graph nodes as landmarks. Then it computes the shortest distances from each landmark to all nodes as an embedding. All the existing methods follow the triangulation based distance estimation that calculates approximately the shortest distance among a pair of query nodes as the sum of their distances to a landmark. The landmark set gives a lone global view for all possible queries that could be diameter apart or close by because the landmark selection stage is query independent. Hence it is difficult to accomplish consistently good performance on all queries as well as the landmark embedding approach may introduce a large relative error. Recently new method presented which is called as a query-dependent Local Landmark Scheme (LLS), which identifies a local landmark specific to a pair of query nodes. In these approach first needs to find query-dependent local landmark which is close to both query nodes for more accurate distance estimation. Then, the distance between the two query nodes is estimated as the sum of their shortest distances to the local landmark that is nearer than the any other. This method is only focusing on reducing the distance estimation error.

Keywords: Shortest Distance Query, Landmark selection, Local Landmark Scheme

Edition: Volume 3 Issue 11, November 2014

Pages: 2081 - 2083

Share this Article

How to Cite this Article?

Sonali Malode, Mansi Bhonsle, "Survey of Approximate Shortest Distance Computing Using Improved Shortest Path Tree", International Journal of Science and Research (IJSR), https://www.ijsr.net/search_index_results_paperid.php?id=OCT141363, Volume 3 Issue 11, November 2014, 2081 - 2083

106 PDF Views | 73 PDF Downloads

Download Article PDF



Similar Articles with Keyword 'Shortest Distance Query'

Survey Paper, Computer Science & Engineering, India, Volume 3 Issue 11, November 2014

Pages: 2081 - 2083

Survey of Approximate Shortest Distance Computing Using Improved Shortest Path Tree

Sonali Malode, Mansi Bhonsle

Share this Article

Survey Paper, Computer Science & Engineering, India, Volume 3 Issue 12, December 2014

Pages: 2698 - 2700

A Survey on Path Queries

Sithara M P, Varsha C

Share this Article
Top