{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T00:31:59Z","timestamp":1778373119931,"version":"3.51.4"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T00:00:00Z","timestamp":1630108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T00:00:00Z","timestamp":1630108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00778-021-00695-0","type":"journal-article","created":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T03:27:55Z","timestamp":1630121275000},"page":"101-127","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Answering reachability and K-reach queries on large graphs with label constraints"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5115-0872","authenticated-orcid":false,"given":"You","family":"Peng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,28]]},"reference":[{"key":"695_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In European Symposium on Algorithms, pages 24\u201335. Springer, (2012)","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"695_CR2","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Kawarabayashi, K.-i., Kawata, Y.: Fast shortest-path distance queries on road networks by pruned highway labeling. In 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 147\u2013154. SIAM, (2014)","DOI":"10.1137\/1.9781611973198.14"},{"key":"695_CR3","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: 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, pages 349\u2013360. ACM, (2013)","DOI":"10.1145\/2463676.2465315"},{"issue":"3","key":"695_CR4","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"C Barrett","year":"2000","unstructured":"Barrett, C., Jacob, R., Marathe, M.: Formal-language-constrained path problems. SIAM J. Comput. 30(3), 809\u2013837 (2000)","journal-title":"SIAM J. Comput."},{"key":"695_CR5","unstructured":"Bonchi, F., Gionis, A., Gullo, F., Ukkonen, A.: Distance oracles in edge-labeled graphs. In EDBT, pages 547\u2013558, (2014)"},{"key":"695_CR6","doi-asserted-by":"crossref","unstructured":"Chen, M., Gu, Y., Bao, Y., Yu, G.: Label and distance-constraint reachability queries in uncertain graphs. In International Conference on Database Systems for Advanced Applications, pages 188\u2013202. Springer, (2014)","DOI":"10.1007\/978-3-319-05810-8_13"},{"key":"695_CR7","doi-asserted-by":"crossref","unstructured":"Chen, X., Lai, L., Qin, L., Lin, X., Liu, B.: A framework to quantify approximate simulation on graph data. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 1308\u20131319. IEEE, (2021)","DOI":"10.1109\/ICDE51399.2021.00117"},{"key":"695_CR8","doi-asserted-by":"crossref","unstructured":"Cheng, J., Huang, S., Wu, H., Fu, A.W.-C.: Tf-label: a topological-folding labeling scheme for reachability querying in a large graph. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 193\u2013204. ACM, (2013)","DOI":"10.1145\/2463676.2465286"},{"key":"695_CR9","doi-asserted-by":"crossref","unstructured":"Cheng, J., Shang, Z., Cheng, H., Wang, H., K-reach, J.XYu.: who is in your small world. Proceedings of the VLDB Endowment 5(11), 1292\u20131303 (2012)","DOI":"10.14778\/2350229.2350247"},{"key":"695_CR10","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X.: On-line exact shortest distance query processing. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pages 481\u2013492. ACM, (2009)","DOI":"10.1145\/1516360.1516417"},{"key":"695_CR11","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X., Lin, X., Wang, H., Philip, S.Y.: Fast computation of reachability labeling for large graphs. In International Conference on Extending Database Technology, pages 961\u2013979. Springer, (2006)","DOI":"10.1007\/11687238_56"},{"issue":"5","key":"695_CR12","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"695_CR13","first-page":"709","volume":"10","author":"Y Fang","year":"2017","unstructured":"Fang, Y., Cheng, R., Li, X., Luo, S., Hu, J.: Effective community search over large spatial graphs. PVLDB 10(6), 709\u2013720 (2017)","journal-title":"PVLDB"},{"issue":"12","key":"695_CR14","first-page":"1233","volume":"9","author":"Y Fang","year":"2016","unstructured":"Fang, Y., Cheng, R., Luo, S., Hu, J.: Effective community search for large attributed graphs. PVLDB 9(12), 1233\u20131244 (2016)","journal-title":"PVLDB"},{"issue":"12","key":"695_CR15","first-page":"1885","volume":"10","author":"Y Fang","year":"2017","unstructured":"Fang, Y., Cheng, R., Luo, S., Hu, J., Huang, K.: C-explorer: browsing communities in large graphs. PVLDB 10(12), 1885\u20131888 (2017)","journal-title":"PVLDB"},{"issue":"1","key":"695_CR16","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00778-019-00556-x","volume":"29","author":"Y Fang","year":"2020","unstructured":"Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., Lin, X.: A survey of community search over big graphs. VLDB J. 29(1), 353\u2013392 (2020)","journal-title":"VLDB J."},{"issue":"6","key":"695_CR17","first-page":"854","volume":"13","author":"Y Fang","year":"2020","unstructured":"Fang, Y., Yang, Y., Zhang, W., Lin, X., Cao, X.: Effective and efficient community search over large heterogeneous information networks. PVLDB 13(6), 854\u2013857 (2020)","journal-title":"PVLDB"},{"issue":"11","key":"695_CR18","first-page":"1719","volume":"12","author":"Y Fang","year":"2019","unstructured":"Fang, Y., Yu, K., Cheng, R., Lakshmanan, L.V., Lin, X.: Efficient algorithms for densest subgraph discovery. PVLDB 12(11), 1719\u20131732 (2019)","journal-title":"PVLDB"},{"key":"695_CR19","doi-asserted-by":"crossref","unstructured":"Hassan, M.S., Aref, W.G., Aly, A.M.: Graph indexing for shortest-path finding over dynamic sub-graphs. In Proceedings of the 2016 International Conference on Management of Data, pages 1183\u20131197. ACM, (2016)","DOI":"10.1145\/2882903.2882933"},{"key":"695_CR20","doi-asserted-by":"crossref","unstructured":"Hu, J., Cheng, R., Chang, K.C.-C., Sankar, A., Fang, Y., Lam, B.Y.: Discovering maximal motif cliques in large heterogeneous information networks. In International Conference on Data Engineering (ICDE), pages 746\u2013757. IEEE, (2019)","DOI":"10.1109\/ICDE.2019.00072"},{"key":"695_CR21","doi-asserted-by":"crossref","unstructured":"Jin, R., Hong, H., Wang, H., Ruan, N., Xiang, Y.: Computing label-constraint reachability in graph databases. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 123\u2013134. ACM, (2010)","DOI":"10.1145\/1807167.1807183"},{"key":"695_CR22","doi-asserted-by":"crossref","unstructured":"Jin, R., Wang, G.: Simple, fast, and scalable reachability oracle. Proceedings of the VLDB Endowment 6(14), 1978\u20131989 (2013)","DOI":"10.14778\/2556549.2556578"},{"key":"695_CR23","doi-asserted-by":"crossref","unstructured":"Jin, X., Yang, Z., Lin, X., Yang, S., Qin, L., Peng, Y.: Fast: Fpga-based subgraph matching on massive graphs. arXiv preprint arXiv:2102.10768, (2021)","DOI":"10.1109\/ICDE51399.2021.00129"},{"key":"695_CR24","unstructured":"Klodt, P., Weikum, G., Bedathur, S., Seufert, S.: Indexing strategies for constrained shortest paths over large social networks. Universitat des Saarlandes, (2011)"},{"key":"695_CR25","doi-asserted-by":"crossref","unstructured":"Koschmieder, A., Leser, U.: Regular path queries on large graphs. In International Conference on Scientific and Statistical Database Management, pages 177\u2013194. Springer, (2012)","DOI":"10.1007\/978-3-642-31235-9_12"},{"key":"695_CR26","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: Konect: the koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web, pages 1343\u20131350. ACM, (2013)","DOI":"10.1145\/2487788.2488173"},{"key":"695_CR27","doi-asserted-by":"crossref","unstructured":"Lai, Z., Peng, Y., Yang, S., Lin, X., Zhang, W.: Pefp: Efficient k-hop constrained s-t simple path enumeration on fpga. In ICDE, IEEE (2021)","DOI":"10.1109\/ICDE51399.2021.00118"},{"key":"695_CR28","doi-asserted-by":"crossref","unstructured":"Leskovec, J.: Snap: Stanford large network dataset collection, (2016)","DOI":"10.1145\/2898361"},{"key":"695_CR29","unstructured":"Leskovec, J., Sosic, R.: Snap: A general purpose network analysis and graph mining library in c++, (2014)"},{"key":"695_CR30","doi-asserted-by":"crossref","unstructured":"Li, Y., Yiu, M.L., Kou, N.M., et al.: An experimental study on hub labeling based shortest path algorithms. Proceedings of the VLDB Endowment 11(4), 445\u2013457 (2017)","DOI":"10.1145\/3186728.3164141"},{"issue":"1","key":"695_CR31","first-page":"24","volume":"9","author":"Z Li","year":"2015","unstructured":"Li, Z., Fang, Y., Qin, L., Cheng, J., Cheng, R., Lui, J.C.: Walking in the cloud: parallel simrank at scale. PVLDB 9(1), 24\u201335 (2015)","journal-title":"PVLDB"},{"key":"695_CR32","doi-asserted-by":"crossref","unstructured":"Ma, C., Fang, Y., Cheng, R., Lakshmanan, L.V., Zhang, W., Lin, X.: Efficient algorithms for densest subgraph discovery on large directed graphs. In ACM SIGMOD, pages 1051\u20131066, (2020)","DOI":"10.1145\/3318464.3389697"},{"key":"695_CR33","doi-asserted-by":"crossref","unstructured":"Peng, Y., Lin, X., Zhang, Y., Zhang, W., Qin, L., Zhou, J.: Efficient hop-constrained s-t simple path enumeration. The VLDB Journal, pages 1\u201324, (2021)","DOI":"10.1007\/s00778-021-00674-5"},{"key":"695_CR34","doi-asserted-by":"crossref","unstructured":"Peng, Y., Zhang, Y., Lin, X., Qin, L., Zhang, W.: Answering billion-scale label-constrained reachability queries within microsecond. Proceedings of the VLDB Endowment 13(6), 812\u2013825 (2020)","DOI":"10.14778\/3380750.3380753"},{"issue":"4","key":"695_CR35","doi-asserted-by":"publisher","first-page":"463","DOI":"10.14778\/3372716.3372720","volume":"13","author":"Y Peng","year":"2019","unstructured":"Peng, Y., Zhang, Y., Lin, X., Zhang, W., Qin, L., Zhou, J.: Hop-constrained s-t simple path enumeration: Towards bridging theory and practice. Proceedings of the VLDB Endowment 13(4), 463\u2013476 (2019)","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"4","key":"695_CR36","doi-asserted-by":"publisher","first-page":"463","DOI":"10.14778\/3372716.3372720","volume":"13","author":"Y Peng","year":"2019","unstructured":"Peng, Y., Zhang, Y., Lin, X., Zhang, W., Qin, L., Zhou, J.: Towards bridging theory and practice: hop-constrained st simple path enumeration. Proc. VLDB Endow. 13(4), 463\u2013476 (2019)","journal-title":"Proc. VLDB Endow."},{"key":"695_CR37","doi-asserted-by":"crossref","unstructured":"Peng, Y., Zhang, Y., Zhang, W., Lin, X., Qin, L.: Efficient probabilistic k-core computation on uncertain graphs. In 2018 IEEE 34th International Conference on Data Engineering (ICDE), pages 1192\u20131203. IEEE, (2018)","DOI":"10.1109\/ICDE.2018.00110"},{"key":"695_CR38","doi-asserted-by":"crossref","unstructured":"Peng, Y., Zhao, W., Zhang, W., Lin, X., Zhang, Y.: Dlq: A system for label-constrained reachability queries on dynamic graphs. In Proceedings of the 230th ACM International Conference on Information & Knowledge Management, (2021)","DOI":"10.1145\/3459637.3481978"},{"issue":"12","key":"695_CR39","doi-asserted-by":"publisher","first-page":"1876","DOI":"10.14778\/3229863.3229874","volume":"11","author":"X Qiu","year":"2018","unstructured":"Qiu, X., Cen, W., Qian, Z., Peng, Y., Zhang, Y., Lin, X., Zhou, J.: Real-time constrained cycle detection in large dynamic graphs. Proc. VLDB Endow. 11(12), 1876\u20131888 (2018)","journal-title":"Proc. VLDB Endow."},{"issue":"12","key":"695_CR40","first-page":"1876","volume":"11","author":"X Qiu","year":"2018","unstructured":"Qiu, X., Cen, W., Qian, Z., Peng, Y., Zhang, Y., Lin, X., Zhou, J.: Real-time constrained cycle detection in large dynamic graphs. PVLDB 11(12), 1876\u20131888 (2018)","journal-title":"PVLDB"},{"key":"695_CR41","doi-asserted-by":"crossref","unstructured":"Valstar, L.D., Fletcher, G.H., Yoshida, Y.: Landmark indexing for evaluation of label-constrained reachability queries. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 345\u2013358. ACM, (2017)","DOI":"10.1145\/3035918.3035955"},{"key":"695_CR42","doi-asserted-by":"crossref","unstructured":"van Rest, O., Hong, S., Kim, J., Meng, X., Chafi, H.: Pgql: a property graph query language. In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, page\u00a07. ACM, (2016)","DOI":"10.1145\/2960414.2960421"},{"key":"695_CR43","first-page":"v7","volume":"3","author":"S Wadhwa","year":"2019","unstructured":"Wadhwa, S., Prasad, A., Ranu, S., Bagchi, A., Bedathur, S.: Efficiently answering regular simple path queries on large labeled networks. Age 3, v7 (2019)","journal-title":"Age"},{"issue":"1","key":"695_CR44","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/2206869.2206879","volume":"41","author":"PT Wood","year":"2012","unstructured":"Wood, P.T.: Query languages for graph databases. ACM SIGMOD Rec. 41(1), 50\u201360 (2012)","journal-title":"ACM SIGMOD Rec."},{"issue":"10","key":"695_CR45","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.14778\/3339490.3339491","volume":"12","author":"Y Yuan","year":"2019","unstructured":"Yuan, Y., Lian, X., Wang, G., Ma, Y., Wang, Y.: Constrained shortest path query in a large time-dependent graph. Proc. VLDB Endow. 12(10), 1058\u20131070 (2019)","journal-title":"Proc. VLDB Endow."},{"key":"695_CR46","doi-asserted-by":"crossref","unstructured":"Yue, D., Wu, X., Wang, Y., Li, Y., Chu, C.-H.: A review of data mining-based financial fraud detection research. In 2007 International Conference on Wireless Communications, Networking and Mobile Computing, pages 5519\u20135522. Ieee, (2007)","DOI":"10.1109\/WICOM.2007.1352"},{"issue":"5","key":"695_CR47","doi-asserted-by":"publisher","first-page":"488","DOI":"10.14778\/3303753.3303756","volume":"12","author":"X Zhang","year":"2019","unstructured":"Zhang, X., \u00d6zsu, M.T.: Correlation constraint shortest path over large multi-relation graphs. Proc. VLDB Endow. 12(5), 488\u2013501 (2019)","journal-title":"Proc. VLDB Endow."},{"key":"695_CR48","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.is.2013.10.003","volume":"40","author":"L Zou","year":"2014","unstructured":"Zou, L., Xu, K., Yu, J.X., Chen, L., Xiao, Y., Zhao, D.: Efficient processing of label-constraint reachability queries in large graphs. Inf. Syst. 40, 47\u201366 (2014)","journal-title":"Inf. Syst."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00695-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00695-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00695-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,28]],"date-time":"2022-01-28T11:07:38Z","timestamp":1643368058000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00695-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,28]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["695"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00695-0","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,28]]},"assertion":[{"value":"10 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}