{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:49:37Z","timestamp":1774986577050,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62302421"],"award-info":[{"award-number":["62302421"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    As a building block of many graph-based areas, the\n                    <jats:italic toggle=\"yes\">s-t<\/jats:italic>\n                    path enumeration problem aims to find all paths between\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">t<\/jats:italic>\n                    by satisfying a given constraint, e.g., hop numbers. In many real-world scenarios, graphs are multi-attribute, where vertices and edges are associated with numerical attributes, such as expense or distance in road networks. However, existing methods have not fully leveraged all attributes in\n                    <jats:italic toggle=\"yes\">s-t<\/jats:italic>\n                    path analysis. Hence, in this paper, we study the problem of skyline path enumeration, which aims to identify paths that balance multiple attributes, ensuring that no skyline result is dominated by another, thus meeting diverse user needs. To efficiently tackle this problem, we design a task-oriented core attribute index, called CAI, to rule out all redundant vertices and edges not located in any skyline path. Additionally, we introduce a hop-dependency label propagation strategy to construct the CAI index in parallel, improving the indexing process. Based on this index, we further design a CAI-based querying strategy that reduces fruitless explorations between candidate vertices not in the same skyline path, significantly optimizing query processing time. Experimental evaluations on fifteen real-world graphs show that CAI outperforms existing methods by up to four orders of magnitude in speed while demonstrating enhanced scalability and well-bound memory costs.\n                  <\/jats:p>","DOI":"10.1145\/3725261","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3764-6476","authenticated-orcid":false,"given":"Yuanyuan","family":"Zeng","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1463-814X","authenticated-orcid":false,"given":"Wensheng","family":"Luo","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-8512","authenticated-orcid":false,"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD. ACM 349--360.","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2756553"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.153"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3198394.3198410"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588915"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2882837"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3425891"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI). 3544--3550","author":"Chen Yankai","year":"2021","unstructured":"Yankai Chen, Jie Zhang, Yixiang Fang, Xin Cao, and Irwin King. 2021. Efficient community search over large directed graphs: An augmented index-based approach. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI). 3544--3550."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30675-4_15"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626731"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517883"},{"key":"e_1_2_1_14_1","volume-title":"EDBT","author":"Gong Qixu","year":"2022","unstructured":"Qixu Gong and Huiping Cao. 2022. Backbone Index to Support Skyline Path Queries over Multi-cost Road Networks. In EDBT, 2022. OpenProceedings.org, 2:325--2:337."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Sairam Gurajada and Martin Theobald. 2016. Distributed Set Reachability. In SIGMOD. ACM 1247--1261.","DOI":"10.1145\/2882903.2915226"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071382"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489499"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447845"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183736"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Wentao Li Miao Qiao Lu Qin Ying Zhang Lijun Chang and Xuemin Lin. 2019. Scaling Distance Labeling on Small-World Networks. In SIGMOD. ACM 1060--1077.","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Wentao Li Miao Qiao Lu Qin Ying Zhang Lijun Chang and Xuemin Lin. 2020. Scaling Up Distance Labeling on Graphs with Core-Periphery Properties. In SIGMOD. ACM 1367--1381.","DOI":"10.1145\/3318464.3389748"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00322"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551826"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457299"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447851"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Masaaki Nishino Norihito Yasuda Shin-ichi Minato and Masaaki Nagata. 2017. Compiling Graph Substructures into Sentential Decision Diagrams. In AAAI. 1213--1221.","DOI":"10.1609\/aaai.v31i1.10697"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00071"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372720"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Michalis Potamias Francesco Bonchi Carlos Castillo and Aristides Gionis. 2009. Fast shortest path distance estimation in large networks. In CIKM. ACM 867--876.","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22363-6_3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Shixuan Sun Yuhang Chen Bingsheng He and Bryan Hooi. 2021. PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration. In SIGMOD. ACM 1758--1770.","DOI":"10.1145\/3448016.3457290"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Lucien D. J. Valstar George H. L. Fletcher and Yuichi Yoshida. 2017. Landmark Indexing for Evaluation of Label-Constrained Reachability Queries. In SIGMOD. ACM 345--358.","DOI":"10.1145\/3035918.3035955"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452826"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00104"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589315"},{"key":"e_1_2_1_38_1","volume-title":"AMBN (Proceedings of Machine Learning Research","volume":"140","author":"Yasuda Norihito","year":"2017","unstructured":"Norihito Yasuda, Teruji Sugaya, and Shin-ichi Minato. 2017. Fast Compilation of s-t Paths on a Graph for Counting and Enumeration. In AMBN (Proceedings of Machine Learning Research, Vol. 73). PMLR, 129--140."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588928"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009122115"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3139111"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00193"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589408"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:55:49Z","timestamp":1774983349000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725261"],"URL":"https:\/\/doi.org\/10.1145\/3725261","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}