Finding the shortest path in a graph is a fundamental operation that allows complex relationships discovering in a graph database.This paper considers top-k shortest-path queries on RDF(Resource Description Framework) graphs.To solve this problem, we provide a component-based index for path queries and present an approach to answer the top-k shortest-path query.To efficiently process queries, we propose frequent path strategy and structural pruning.For frequent path strategy, we precompute the top-k shortest-paths between frequent entities obtained from the frequent paths.For the structural pruning, we find out the termination condition for queries by considering the structural information of component-based index and derive two lemmas to guide this pruning mechanism.Experiments results show that the query runtime is improved by 92% using our answering approach and the construction time of our index for RDF graphs is speeded up by 56%.Meanwhile, the size of this index is only 0~0.2 times larger than that of the raw graphs.
[1] Syed A R,Dietmar S.Observing local and global properties of metabolic pathways:‘load points' and ‘choke points' in the metabolic networks[J].Bioinformatics,2006,22(14):1767-1774.
[2] Stefano B,et al.Complex networks:structure and dynamics[J].Physics Reports,2006,424(1):175-308.
[3] Takuya A,et al.Shortest-path queries for complex networks:exploiting low tree-width outside the core[A].International Conference on Extending DB Technology [C].London:Springer,2012.144-155.
[4] Zhigang W,et al.Shortest path computation over disk-resident large graphs based on extended bulk synchronous parallel methods[A].Database Systems for Advanced Applications [C].London:Springer,2013.1-15.
[5] Mohamed S,et al.Horton+:a distributed system for processing declarative reachability queries over partitioned graphs[J].The Proceedings of the VLDB Endowment,2013,6(14):1918-1929.
[6] Fang W.TEDI:efficient shortest path query answering on graphs[A].ACM Conference on Management of Data[C].New York:ACM,2010.99-110.
[7] Yanghua X,et al.Efficiently indexing shortest paths by exploiting symmetry in graphs[A].International Conference on Extending DB Technology [C].London:Springer,2009.24-26.
[8] Takuya A.Pruned labeling algorithms:fast,exact,dynamic,simple and general indexing scheme for shortest-path queries[A].International World Wide Web Conferences[C].London:Springer,2014.1339-1340.
[9] Lingkun W,et al.Shortest path and distance queries on road networks:an experimental evaluation[J].The Proceedings of the VLDB Endowment,2012,5(5):406-417.
[10] Jiefeng C,et al.Top-k graph pattern matching over large graphs[A].IEEE International Conference on Data Engineering[C].Washington:IEEE Press,2013.1033-1044.
[11] Qian W,et al.Finding top-k profitable products[A].IEEE International Conference on Data Engineering[C].Washington:IEEE Press,2011.1055-1066.
[12] Lu Q,et al.Diversifying top-k results[J].The Proceedings of the VLDB Endowment,2013,5(11):1124-1135.
[13] Yuanyuan Z,et al.Finding top-k similar graphs in graph databases[A].International Conference on Extending DB Technology[C].London:Springer,2012.456-467.
[14] Thomas N,Gerhard W.The RDF-3X engine for scalable management of RDF data[J].VLDB Journal,2010,19(1):91-149.
[15] Octavian U,et al.GRIN:A graph based RDF index[A].AAAI Conference on Artificial Intelligence [C].California:AAAI Press,2007.1465-1470.
[16] Mihaela A B,et al.Building an efficient RDF store over a relational database[A].ACM Conference on Management of Data[C].New York:ACM,2013.121-132.
[17] Takuya A,et al.Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling[A].International World Wide Web Conferences[C].London:Springer,2014.237-248.
2015, Vol. 43 
