International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Call for Papers | Fully Refereed | Open Access | Double Blind Peer Reviewed

ISSN: 2319-7064


Downloads: 109

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 [5]


Abstract: 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


How to Download this Article?

You Need to Register Your Email Address Before You Can Download the Article PDF


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), Volume 3 Issue 11, November 2014, pp. 2081-2083, https://www.ijsr.net/get_abstract.php?paper_id=OCT141363

Similar Articles with Keyword 'Shortest'

Downloads: 2 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1

Experimental Result Paper, Computer Science & Engineering, India, Volume 11 Issue 11, November 2022

Pages: 667 - 674

Exploring a Minimum Cost Solution for Traveling Salesman Problem using Parallel Simulated Annealing

Geerisha Jain | Dr. Anto S | Dewang Mehta

Share this Article

Downloads: 5 | Weekly Hits: ⮙5 | Monthly Hits: ⮙5

Research Paper, Computer Science & Engineering, India, Volume 13 Issue 2, February 2024

Pages: 736 - 741

Energy Efficient Routing Algorithm for Future Ad-hoc Wireless Networks

Dr. J. Seetaram | Dr. M. Nagaraju Naik

Share this Article
Top