{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T15:21:22Z","timestamp":1771600882412,"version":"3.50.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,2]]},"abstract":"<jats:p>In this paper, we study the problem of label-constrained reachability (LCR) query which is fundamental in many applications with directed edge-label graphs. Although the classical reachability query (i.e., reachability query without label constraint) has been extensively studied, LCR query is much more challenging because the number of possible label constraint set is exponential to the size of the labels. We observe that the existing techniques for LCR queries only construct partial index for better scalability, and their worst query time is not guaranteed and could be the same as an online breadth-first search (BFS).<\/jats:p>\n          <jats:p>In this paper, we propose novel label-constrained 2-hop indexing techniques with novel pruning rules and order strategies. It is shown that our worst query time could be bounded by the in-out index entry size. With all these techniques, comprehensive experiments show that our proposed methods significantly outperform the state-of-the-art technique in terms of query response time (up to 5 orders of magnitude speedup), index size and index construction time. In particular, our proposed method can answer LCR queries within microsecond over billion-scale graphs in a single machine.<\/jats:p>","DOI":"10.14778\/3380750.3380753","type":"journal-article","created":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T21:49:08Z","timestamp":1583963348000},"page":"812-825","source":"Crossref","is-referenced-by-count":60,"title":["Answering billion-scale label-constrained reachability queries within microsecond"],"prefix":"10.14778","volume":"13","author":[{"given":"You","family":"Peng","sequence":"first","affiliation":[{"name":"The University of New South, Wales"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of Technology, Sydney"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South, Wales"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"The University of Technology, Sydney"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South, Wales"}]}],"member":"320","published-online":{"date-parts":[[2020,3,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.14"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"R. Angles M. Arenas P. Barcel\u00f3 A. Hogan J. Reutter and D. Vrgo\u010d. Foundations of modern query languages for graph databases. ACM Computing Surveys (CSUR) 50(5):68 2017.  R. Angles M. Arenas P. Barcel\u00f3 A. Hogan J. Reutter and D. Vrgo\u010d. Foundations of modern query languages for graph databases. ACM Computing Surveys (CSUR) 50(5):68 2017.","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_5_1","first-page":"175","volume-title":"Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013","author":"Baeza P. B.","year":"2013"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/702694"},{"key":"e_1_2_1_8_1","first-page":"547","volume-title":"EDBT","author":"Bonchi F.","year":"2014"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05810-8_13"},{"key":"e_1_2_1_10_1","volume-title":"2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE","author":"Chen X.","year":"2020"},{"key":"e_1_2_1_11_1","article-title":"Exploring communities in large profiled graphs","author":"Chen Y.","year":"2018","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516417"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_56"},{"issue":"09","key":"e_1_2_1_15_1","article-title":"A survey on social network analysis for counterterrorism","volume":"112","author":"Choudhary P.","year":"2015","journal-title":"International Journal of Computer Applications"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539702403098"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137800"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845414"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2872982"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Y. Fang Y. Yang W. Zhang X. Lin and X. Cao. Effective and efficient community search over large heterogeneous information networks. PVLDB 13(6) Feb. 2020.  Y. Fang Y. Yang W. Zhang X. Lin and X. Cao. Effective and efficient community search over large heterogeneous information networks. PVLDB 13(6) Feb. 2020.","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882933"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00072"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2730873"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807183"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213856"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556578"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_33_1","volume-title":"Universitat des Saarlandes","author":"Klodt P.","year":"2011"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339494"},{"key":"e_1_2_1_36_1","unstructured":"J. Leskovec. Snap: Stanford large network dataset collection 2016.  J. Leskovec. Snap: Stanford large network dataset collection 2016."},{"issue":"4","key":"e_1_2_1_37_1","first-page":"445","article-title":"An experimental study on hub labeling based shortest path algorithms","volume":"11","author":"Li Y.","year":"2017","journal-title":"PVLDB"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34223-4_44"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90032-1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035955"},{"key":"e_1_2_1_44_1","first-page":"7","volume-title":"Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems","author":"van Rest O."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989419"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319882"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00030"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_1_49_1","volume-title":"2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE","author":"Wang K.","year":"2020"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732992"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505724"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339491"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2880976"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00057"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303756"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247651"},{"key":"e_1_2_1_60_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\/3380750.3380753","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:29:30Z","timestamp":1672219770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3380750.3380753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2]]},"references-count":60,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["10.14778\/3380750.3380753"],"URL":"https:\/\/doi.org\/10.14778\/3380750.3380753","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,2]]}}}