{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T15:20:38Z","timestamp":1777735238724,"version":"3.51.4"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:p>\n            Computing the reachability between two vertices in a graph is a fundamental problem in graph data analysis. Most of the existing works assume that the edges in the graph have no labels, but in many real application scenarios, edges naturally come with edge-labels, and label constraints may be placed on the edges appearing on a valid path between two query vertices. Therefore, we study the label-constrained reachability (LCR) queries in this paper, where we are given a source vertex\n            <jats:italic>s<\/jats:italic>\n            , a target vertex\n            <jats:italic>t<\/jats:italic>\n            , a label set \u0394, and the goal is to check whether there exists any path from\n            <jats:italic>s<\/jats:italic>\n            to\n            <jats:italic>t<\/jats:italic>\n            such that all the labels of edges on the path belong to \u0394.\n          <\/jats:p>\n          <jats:p>A plethora of methods have been proposed in the literature to support the LCR queries. All these methods take the assumption that the graph is resident in the main memory of a machine. Nevertheless, the graphs in many real application scenarios are generally big and may not reside in memory. In these cases, existing methods suffer from serious scalability problem, i.e., result in huge I\/O costs. Motivated by this, in this paper, we study the I\/O efficient LCR query problem and aim to efficiently answer the LCR queries when the graph cannot fit in the main memory. To achieve this goal, we propose a reduction-based indexing approach. We introduce two elegant graph reduction operators which aims to reduce the size of the graph loaded in memory while preserving the LCR information among the remaining vertices. With these two operators, we devise an index named LCR-Index and propose algorithms to adaptively construct the index based on the available memory. Equipped with LCR-Index, we can answer a LCR query by only scanning the LCR-Index sequentially. Experiments demonstrate our query processing algorithm can handle graphs with billions of edges.<\/jats:p>","DOI":"10.14778\/3675034.3675049","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:19:11Z","timestamp":1722982751000},"page":"2590-2602","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["I\/O Efficient Label-Constrained Reachability Queries in Large Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Long","family":"Yuan","sequence":"first","affiliation":[{"name":"Nanjing University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xia","family":"Li","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zi","family":"Chen","sequence":"additional","affiliation":[{"name":"Nanjing University of Aeronautics and Astronautics"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiaotong University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiang","family":"Zhao","sequence":"additional","affiliation":[{"name":"National University of Defense Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","first-page":"3","volume-title":"Proceedings of ALENEX","author":"Ajwani D.","year":"2007","unstructured":"D. Ajwani, U. Meyer, and V. Osipov. Improved external memory bfs implementations. In Proceedings of ALENEX, pages 3--12, 2007."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149196"},{"key":"e_1_2_1_4_1","first-page":"859","volume-title":"Proceedings of SODA","author":"Buchsbaum A. L.","year":"2000","unstructured":"A. L. Buchsbaum, M. H. Goldwasser, and S. Venkatasubramanian. On external memory graph traversal. In Proceedings of SODA, pages 859--860, 2000."},{"key":"e_1_2_1_5_1","first-page":"256","volume-title":"Proceedings ICDE","author":"Chen L.","year":"2019","unstructured":"L. Chen, Y. Gao, Y. Zhang, C. S. Jensen, and B. Zheng. Efficient and incremental clustering algorithms on star-schema heterogeneous graphs. In Proceedings ICDE, pages 256--267, 2019."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529348"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-023-00227-6"},{"key":"e_1_2_1_8_1","first-page":"193","volume-title":"Proceedings of SIGMOD","author":"Cheng J.","year":"2013","unstructured":"J. Cheng, S. Huang, H. Wu, and A. W. Fu. Tf-label: a topological-folding labeling scheme for reachability querying in a large graph. In Proceedings of SIGMOD, pages 193--204, 2013."},{"key":"e_1_2_1_9_1","first-page":"51","volume-title":"Proceedings of ICDE","author":"Cheng J.","year":"2011","unstructured":"J. Cheng, Y. Ke, S. Chu, and M. T. \u00d6zsu. Efficient core decomposition in massive networks. In Proceedings of ICDE, pages 51--62, 2011."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043654"},{"key":"e_1_2_1_11_1","first-page":"961","volume-title":"Proceedings of EDBT","author":"Cheng J.","year":"2006","unstructured":"J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. Fast computation of reachability labeling for large graphs. In Proceedings of EDBT, pages 961--979, 2006."},{"key":"e_1_2_1_12_1","volume-title":"External-memory graph algorithms","author":"Chiang Y.-J.","year":"1995","unstructured":"Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. 1995."},{"issue":"9","key":"e_1_2_1_13_1","first-page":"24","article-title":"A survey on social network analysis for counter-terrorism","volume":"112","author":"Choudhary P.","year":"2015","unstructured":"P. Choudhary and U. Singh. A survey on social network analysis for counter-terrorism. International Journal of Computer Applications, 112(9):24--29, 2015.","journal-title":"International Journal of Computer Applications"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"issue":"10","key":"e_1_2_1_15_1","first-page":"3453","article-title":"Time-respecting flow graph pattern matching on temporal graphs","volume":"33","author":"Gao Y.","year":"2020","unstructured":"Y. Gao, T. Zhang, L. Qiu, Q. Linghu, and G. Chen. Time-respecting flow graph pattern matching on temporal graphs. IEEE TKDE, 33(10):3453--3467, 2020.","journal-title":"IEEE TKDE"},{"key":"e_1_2_1_16_1","first-page":"439","volume-title":"Proceedings of the STOC","author":"Halld\u00f3rsson M.","year":"1994","unstructured":"M. Halld\u00f3rsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. In Proceedings of the STOC, pages 439--448, 1994."},{"key":"e_1_2_1_17_1","first-page":"627","volume-title":"Proceedings of FOCS","author":"Hastad J.","year":"1996","unstructured":"J. Hastad. Clique is hard to approximate within n1-\u03f5. In Proceedings of FOCS, pages 627--636, 1996."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_19_1","first-page":"123","volume-title":"Proceedings of SIGMOD","author":"Jin R.","year":"2010","unstructured":"R. Jin, H. Hong, H. Wang, N. Ruan, and Y. Xiang. Computing label-constraint reachability in graph databases. In Proceedings of SIGMOD, pages 123--134, 2010."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/2213836.2213856","volume-title":"Proceedings of SIGMOD","author":"Jin R.","year":"2012","unstructured":"R. Jin, N. Ruan, S. Dey, and J. X. Yu. SCARAB: scaling reachability computation on large graphs. In Proceedings of SIGMOD, pages 169--180, 2012."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556578"},{"key":"e_1_2_1_22_1","first-page":"813","volume-title":"Proceedings of SIGMOD","author":"Jin R.","year":"2009","unstructured":"R. Jin, Y. Xiang, N. Ruan, and D. Fuhry. 3-hop: a high-compression indexing scheme for reachability query. In Proceedings of SIGMOD, pages 813--826, 2009."},{"key":"e_1_2_1_23_1","series-title":"Lecture Notes in Computer Science","first-page":"62","volume-title":"Algorithms for Memory Hierarchies","author":"Katriel I.","year":"2002","unstructured":"I. Katriel and U. Meyer. Elementary graph algorithms in external memory. In Algorithms for Memory Hierarchies, volume 2625 of Lecture Notes in Computer Science, pages 62--84, 2002."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1145\/2882903.2915209","volume-title":"Proceedings of SIGMOD","author":"Kim H.","year":"2016","unstructured":"H. Kim, J. Lee, S. S. Bhowmick, W. Han, J. Lee, S. Ko, and M. H. A. Jarrah. DUALSIM: parallel subgraph enumeration in a massive graph on a single machine. In Proceedings of SIGMOD, pages 1231--1245, 2016."},{"key":"e_1_2_1_25_1","first-page":"169","volume-title":"Proceedings of SPDP","author":"Kumar V.","year":"1996","unstructured":"V. Kumar and E. J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In Proceedings of SPDP, pages 169--176, 1996."},{"key":"e_1_2_1_26_1","first-page":"74","volume-title":"Proceedings of ICDE","author":"Libkin L.","year":"2012","unstructured":"L. Libkin and D. Vrgo\u010d. Regular path queries on graphs with data. In Proceedings of ICDE, pages 74--85, 2012."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00606-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831366"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2023.3306773"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9131-5"},{"key":"e_1_2_1_31_1","first-page":"1","volume-title":"Proceedings of ICDT","volume":"98","author":"Martens W.","year":"2018","unstructured":"W. Martens and T. Trautner. Evaluation and enumeration problems for regular path queries. In Proceedings of ICDT, volume 98, pages 19:1--19:21, 2018."},{"key":"e_1_2_1_32_1","volume-title":"A survey of distributed graph algorithms on massive graphs. CoRR, abs\/2404.06037","author":"Meng L.","year":"2024","unstructured":"L. Meng, Y. Shao, L. Yuan, L. Lai, P. Cheng, X. Li, W. Yu, W. Zhang, X. Lin, and J. Zhou. A survey of distributed graph algorithms on massive graphs. CoRR, abs\/2404.06037, 2024."},{"key":"e_1_2_1_33_1","first-page":"2831","volume-title":"Proceedings ICDE","author":"Meng L.","year":"2022","unstructured":"L. Meng, L. Yuan, Z. Chen, X. Lin, and S. Yang. Index-based structural clustering on directed graphs. In Proceedings ICDE, pages 2831--2844, 2022."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36574-5","volume-title":"Algorithms for memory hierarchies: advanced lectures","author":"Meyer U.","year":"2003","unstructured":"U. Meyer and P. Sanders. Algorithms for memory hierarchies: advanced lectures, volume 2625. Springer Science & Business Media, 2003."},{"key":"e_1_2_1_35_1","volume-title":"AGP'17","author":"Mukkara A.","year":"2017","unstructured":"A. Mukkara, N. Beckmann, and D. Sanchez. Cache-guided scheduling: Exploiting caches to maximize locality in graph processing. AGP'17, 2017."},{"key":"e_1_2_1_36_1","first-page":"1415","volume-title":"Proceedings SIGMOD","author":"Pacaci A.","year":"2020","unstructured":"A. Pacaci, A. Bonifati, and M. T. \u00d6zsu. Regular path query evaluation on streaming graphs. In Proceedings SIGMOD, pages 1415--1430, 2020."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380753"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90032-5"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00548-x"},{"key":"e_1_2_1_41_1","first-page":"237","volume-title":"Proceedings of EDBT","author":"Schenkel R.","year":"2004","unstructured":"R. Schenkel, A. Theobald, and G. Weikum. HOPI: an efficient connection index for complex XML document collections. In Proceedings of EDBT, pages 237--255, 2004."},{"key":"e_1_2_1_42_1","first-page":"1009","volume-title":"Proceedings of ICDE","author":"Seufert S.","year":"2013","unstructured":"S. Seufert, A. Anand, S. J. Bedathur, and G. Weikum. FERRARI: flexible and efficient reachability range assignment for graph indexing. In Proceedings of ICDE, pages 1009--1020, 2013."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90032-1"},{"key":"e_1_2_1_44_1","first-page":"345","volume-title":"Proceedings SIGMOD","author":"Valstar L. D. J.","year":"2017","unstructured":"L. D. J. Valstar, G. H. L. Fletcher, and Y. Yoshida. Landmark indexing for evaluation of label-constrained reachability queries. In Proceedings SIGMOD, pages 345--358, 2017."},{"key":"e_1_2_1_45_1","first-page":"913","volume-title":"Proceedings of SIGMOD","author":"van Schaik S. J.","year":"2011","unstructured":"S. J. van Schaik and O. de Moor. A memory efficient reachability data structure through bit vector compression. In Proceedings of SIGMOD, pages 913--924, 2011."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1481557"},{"key":"e_1_2_1_47_1","first-page":"812","volume-title":"Proceedings of VLDB","author":"Wang J.","year":"2012","unstructured":"J. Wang and J. Cheng. Truss decomposition in massive networks. In Proceedings of VLDB, pages 812--823, 2012."},{"key":"e_1_2_1_48_1","first-page":"1","volume-title":"The VLDB Journal","author":"Wang K.","year":"2024","unstructured":"K. Wang, M. Cai, X. Chen, X. Lin, W. Zhang, L. Qin, and Y. Zhang. Efficient algorithms for reachability and path queries on temporal bipartite graphs. The VLDB Journal, pages 1--28, 2024."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732992"},{"key":"e_1_2_1_50_1","first-page":"1601","volume-title":"Proceedings of CIKM","author":"Yano Y.","year":"2013","unstructured":"Y. Yano, T. Akiba, Y. Iwata, and Y. Yoshida. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In Proceedings of CIKM, pages 1601--1606, 2013."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0256-4"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0408-z"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904484"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0451-4"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494148"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-023-00825-w"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00572-x"},{"key":"e_1_2_1_59_1","first-page":"208","volume-title":"Proceedings of ICDE","author":"Zhang Z.","year":"2014","unstructured":"Z. Zhang, L. Qin, and J. X. Yu. Contract & expand: I\/O efficient sccs computing. In Proceedings of ICDE, pages 208--219, 2014."},{"issue":"2","key":"e_1_2_1_60_1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00778-014-0372-z","article-title":"I\/O efficient: computing sccs in massive graphs","volume":"24","author":"Zhang Z.","year":"2015","unstructured":"Z. Zhang, J. X. Yu, L. Qin, L. Chang, and X. Lin. I\/O efficient: computing sccs in massive graphs. The VLDB Journal, 24(2):245--270, 2015.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_61_1","first-page":"445","volume-title":"Proceedings of SIGMOD","author":"Zhang Z.","year":"2015","unstructured":"Z. Zhang, J. X. Yu, L. Qin, and Z. Shang. Divide & conquer: I\/O efficient depth-first search. In Proceedings of SIGMOD, pages 445--458, 2015."},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1145\/2247596.2247651","volume-title":"Proceedings of EDBT","author":"Zhang Z.","year":"2012","unstructured":"Z. Zhang, J. X. Yu, L. Qin, Q. Zhu, and X. Zhou. I\/O cost minimization: reachability queries processing over massive graphs. In Proceedings of EDBT, pages 468--479, 2012."},{"key":"e_1_2_1_63_1","first-page":"45","volume-title":"Proceedings of FAST","author":"Zheng D.","year":"2015","unstructured":"D. Zheng, D. Mhembere, R. Burns, J. Vogelstein, C. E. Priebe, and A. S. Szalay. Flashgraph: Processing billion-node graphs on an array of commodity ssds. In Proceedings of FAST, pages 45--58, 2015."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.003"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3675034.3675049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:22:38Z","timestamp":1722982958000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3675034.3675049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":64,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10.14778\/3675034.3675049"],"URL":"https:\/\/doi.org\/10.14778\/3675034.3675049","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,6]]},"assertion":[{"value":"2024-08-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}