Survey of Approximate Shortest Distance Computing Using Improved Shortest Path Tree

Sonali Malode, Mansi Bhonsle

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