Open Access Open Access  Restricted Access Subscription or Fee Access

A Novel Shortest Path Identification Algorithm based on Optimization Strategies

J. Deepa, S. Srinivasan

Abstract


In present scenario of many application environments, analysis of large network that includes protein interactions in biological component, online social network and internet traffic analysis has become a decisive component. Accordingly, graph analysis applications play a significant role that may rely on computing distances between node pairs and the shortest path between such nodes. With those concerns, this paper presents a novel method of top-k path join strategy for group relationship analysis. The major intention of this work is to discover top-k shortest paths between a pair of node sets. Bellmam-ford algorithm is used here for finding the shortest path between the node pair. Further, the shortest path between the nodes pairs are identified based on two optimization strategies namely, push join constraint and pruning search space with some scalable determined thresholds. The cost and processing time is well optimized here using candidate path searching mechanism. The efficiency of the proposed work has been analyzed by conducting extensive performance studies.

Keywords


Transformed Graph, Shortest Path, Deviation Node, Push Join, Pruning.

Full Text:

PDF

References


Nicolas Bruno, Nick Koudas and DiveshSrivastava, “Holistic Twig Joins: Optimal XML Pattern Matching,”In Proceedings of the ACM SIGMOD international conference on Management of data, 2002, pp. 310-321.

Jiefeng Cheng and Jeffrey Xu Yu, “On-line Exact Shortest Distance Query Processing,”In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, 2009, pp. 481-492.

Jiefeng Cheng, Jeffrey Xu Yu, Bolin Ding, Philip S. Yu and Haixun Wang, “Fast Graph Pattern Matching,” IEEE 24th International Conference on Data Engineering (ICDE), 2008, pp. 913-922.

Ernesto Q.V. Martins and Marta M.B. Pascoal, “A new implementation of Yen’s ranking loopless paths algorithm,”4OR: A Quarterly Journal of Operations Research, 2003, pp. 121-133. [5] Ernesto, De Queirós Vieira Martins, Marta Margarida Braz Pascoal, and Jose Luis Esteves Dos Santos, “Deviation algorithms for ranking shortest paths," International Journal of Foundations of Computer Science 10.03, 1999, pp. 247-26.

Ruoming Jin, Yang Xiang, NingRuan and Haixun Wang, “Efficiently Answering Reachability Queries on Very Large Directed Graphs,” In Proceedings of the ACM SIGMOD international conference on Management of data, 2008, pp. 595- 608.

Jun Gao, HuidaQiu, Xiao Jiang, Tengjiao Wang and Dongqing Yang, Fast Top-k Simple Shortest Paths Discovery in Graphs,” In Proceedings of the 19th ACM international conference on Information and knowledge management, 2010, pp. 509-518. [8] Eppstein, David. "Finding the k shortest paths." SIAM Journal on computing, 28.2, 1998, pp. 652-673.

Jun Gao, Jeffrey Xu Yu, HuidaQiu, Xiao Jiang, Tengjiao Wang and Dongqing Yang, “Holistic Top-k Simple Shortest Path Join in Graphs,” IEEE Transactions On Knowledge And Data Engineering, Vol. 24, No. 4, 2010, pp. 665-677.

John Hershberger, MatthewMaxel and SubhashSuri, “Finding the k Shortest Simple Paths: A New Algorithm and its Implementation, ”ACM Transactions on Algorithms (TALG) 3.4, 2007.

Lei Zou, Lei Chen and M. Tamer Ozsu, “DistanceJoin: Pattern Match Query in a Large Graph Database, ”Proceedings of the VLDB Endowment 2.1, 2009, pp. 886-897. [12] Gao, J., Jin, R., Zhou, J., Yu, J. X., Jiang, X., & Wang, T., “Relational approach for shortest path discovery over large graphs, ”Proceedings of the VLDB Endowment, 5(4), 2011, pp. 358-369.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.