Xin Chen
Jeffrey Xu Yu
Abstract
Many real-world graphs, e.g., social networks, biological networks, knowledge graphs, naturally come with edge-labels, with different labels representing different relationships between nodes. On such edge-labeled graphs, an important query is the label-constrained reachability (LCR) query, where we are given a source s, a target t, a label set ψ, and the goal is to check if there exists any path P from s to t such that labels of edges on P all belong to ψ. Existing indexing schemes for LCR queries still focus on static graphs, despite the fact that many edge-labeled graphs are dynamic in nature.
Motivated by the limitations of existing solutions, we present a study on how to effectively maintain the indexing scheme on dynamic graphs. Our proposed approach is based on the state-of-the-art 2-hop index for LCR queries. In this paper, we present efficient algorithms for updating the index structure in response to dynamic edge insertions/deletions and demonstrate the correctness of our update algorithms. Following that, we present that adopting a query-friendly but update-unfriendly indexing scheme results in surprisingly superb query/update efficiency and outperforms those update-friendly ones. We analyze and demonstrate that the query-friendly indexing scheme actually achieves the same time complexity as those of update-friendly ones. Finally, we present the batched update algorithms where the updates may include multiple edge insertions/deletions. Extensive experiments show the effectiveness of the proposed update algorithms, query-friendly indexing scheme, and batched update algorithms.
- Ittai Abraham, Daniel Delling, Andrew V Goldberg, and Renato F Werneck. 2012. Hierarchical hub labelings for shortest paths. In European Symposium on Algorithms. Springer, 24--35.Google Scholar
Digital Library
- Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 349--360.Google ScholarDigital Library
- Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5 (2017), 68:1--68:40.Google ScholarDigital Library
- Christopher L. Barrett, Riko Jacob, and Madhav V. Marathe. 2000. Formal-Language-Constrained Path Problems. SIAM J. Comput. 30, 3 (2000), 809--837.Google ScholarDigital Library
- Ramadhana Bramandia, Byron Choi, and Wee Keong Ng. 2010. Incremental Maintenance of 2-Hop Labeling of Large Graphs. TKDE 22, 5 (2010), 682--698.Google ScholarDigital Library
- Jiefeng Cheng and Jeffrey Xu Yu. 2009. On-line exact shortest distance query processing. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. ACM, 481--492.Google ScholarDigital Library
- Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2003. Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32, 5 (2003), 1338--1355.Google ScholarDigital Library
- Gianlorenzo D'Angelo, Mattia D'Emidio, and Daniele Frigioni. 2019. Fully Dynamic 2-Hop Cover Labeling. ACM J. Exp. Algorithmics 24, 1 (2019), 1.6:1--1.6:36.Google ScholarDigital Library
- Camil Demetrescu and Giuseppe F. Italiano. 2006. Fully dynamic all pairs shortest paths with real edge weights. J. Comput. Syst. Sci. 72, 5 (2006), 813--837.Google ScholarDigital Library
- Wenfei Fan, Chunming Hu, and Chao Tian. 2017. Incremental graph computations: Doable and undoable. In Proceedings of the 2017 ACM International Conference on Management of Data. 155--169.Google ScholarDigital Library
- Alastair Green, Martin Junghanns, Max Kießling, Tobias Lindaaker, Stefan Plantikow, and Petra Selmer. 2018. openCypher: New Directions in Property Graph Querying. In EDBT. 520--523.Google Scholar
- Monika Rauch Henzinger and Valerie King. 1995. Fully Dynamic Biconnectivity and Transitive Closure. In FOCS. 664--672.Google Scholar
- Ruoming Jin, Hui Hong, Haixun Wang, Ning Ruan, and Yang Xiang. 2010. Computing label-constraint reachability in graph databases. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM, 123--134.Google ScholarDigital Library
- Ruoming Jin, Ning Ruan, Yang Xiang, and Haixun Wang. 2011. Path-tree: An efficient reachability indexing scheme for large directed graphs. TODS 36, 1 (2011), 7:1--7:44.Google ScholarDigital Library
- Ruoming Jin, Yang Xiang, Ning Ruan, and Haixun Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In SIGMOD. 595--608.Google Scholar
- Ioannis Krommidas and Christos D. Zaroliagis. 2008. An experimental study of algorithms for fully dynamic transitive closure. ACM J. Exp. Algorithmics 12 (2008), 1.6:1--1.6:22.Google ScholarDigital Library
- Jérôme Kunegis. 2013. KONECT: the Koblenz network collection. In WWW. 1343--1350.Google Scholar
- Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.Google Scholar
- Zhe Lin, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Zhihong Tian. 2021. Hierarchical Core Maintenance on Large Dynamic Graphs. PVLDB 14, 5 (2021), 757--770.Google ScholarDigital Library
- You Peng, Xuemin Lin, Ying Zhang, Wenjie Zhang, and Lu Qin. 2021. Answering Reachability and K-Reach Queries on Large Graphs with Label-Constraints. The VLDB Journal (2021), 1--25.Google Scholar
- You Peng, Ying Zhang, Xuemin Lin, Lu Qin, and Wenjie Zhang. 2020. Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond. Proc. VLDB Endow. 13, 6 (2020), 812--825.Google ScholarDigital Library
- You Peng, Wenjie Zhao, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2021. DLQ: A System for Label-Constrained Reachability Queries on Dynamic Graphs. In Proceedings of the 230th ACM International Conference on Information & Knowledge Management.Google ScholarDigital Library
- Liam Roditty. 2013. Decremental maintenance of strongly connected components. In SODA. 1143--1150.Google Scholar
- Liam Roditty and Uri Zwick. 2004. A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In STOC. 184--191.Google Scholar
- Ralf Schenkel, Anja Theobald, and Gerhard Weikum. 2005. Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections. In ICDE. 360--371.Google Scholar
- Lucien D. J. Valstar, George H. L. Fletcher, and Yuichi Yoshida. 2017. Landmark Indexing for Evaluation of Label-Constrained Reachability Queries. In SIGMOD. 345--358.Google Scholar
- Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng, and Hassan Chafi. 2016. PGQL: a property graph query language. In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, Redwood Shores, CA, USA, June 24 - 24, 2016. 7.Google ScholarDigital Library
- Sarisht Wadhwa, Anagh Prasad, Sayan Ranu, Amitabha Bagchi, and Srikanta Bedathur. 2019. Efficiently Answering Regular Simple Path Queries on Large Labeled Networks. In SIGMOD. 1463--1480.Google Scholar
- Sibo Wang, Wenqing Lin, Yi Yang, Xiaokui Xiao, and Shuigeng Zhou. 2015. Efficient Route Planning on Public Transportation Networks: A Labelling Approach. In SIGMOD. ACM, 967--982.Google Scholar
- Sibo Wang, Xiaokui Xiao, Yin Yang, and Wenqing Lin. 2016. Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks. PVLDB 10, 2 (2016), 61--72.Google ScholarDigital Library
- Peter T. Wood. 2012. Query languages for graph databases. SIGMOD Rec. 41, 1 (2012), 50--60.Google ScholarDigital Library
- Hilmi Yildirim, Vineet Chaoji, and Mohammed J. Zaki. 2013. DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs. CoRR abs/1301.0977 (2013).Google Scholar
- Andy Diwen Zhu, Wenqing Lin, Sibo Wang, and Xiaokui Xiao. 2014. Reachability queries on large dynamic graphs: a total order approach. In SIGMOD. 1323--1334.Google Scholar
Recommendations
Comparison between the zeroth-order Randić index and the sum-connectivity index
The zeroth-order Randić index and the sum-connectivity index are very popular topological indices in mathematical chemistry. These two indices are based on vertex degrees of graphs and attracted a lot of attention in recent years. Recently Li and Li (...
The relationship between the eccentric connectivity index and Zagreb indices
Let G be a simple connected graph with vertex set V(G) and edge set E(G). The first Zagreb index M"1(G) and the second Zagreb index M"2(G) are defined as follows: M"1(G)=@?v@?V(G)(d"G(v))^2, and M"2(G)=@?uv@?E(G)d"G(u)d"G(v), where d"G(v) is the degree ...
Transform-Space View: Performing Spatial Join in the Transform Space Using Original-Space Indexes
Spatial joins find all pairs of objects that satisfy a given spatial relationship. In spatial joins using indexes, original-space indexes such as the R-tree are widely used. An original-space index is the one that indexes objects as represented in the ...
Comments