Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs

Summary: Introduces CAI, a core attribute index pruning vertices/edges not on any skyline s-t path in multi-attribute graphs, built via parallel hop-dependency label propagation. CAI-based querying cuts fruitless exploration, delivering large speedups and scalable memory on real graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7261
Venue: SIGMOD
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,748 | 26.26%
DOI: 10.1145/3725261

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yuanyuan Zeng (Chinese University of Hong Kong)
2. Yixiang Fang (Chinese University of Hong Kong)
3. Wensheng Luo (Chinese University of Hong Kong)
4. Chenhao Ma (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{zeng_sigmod25,
        title = {{Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs}},
        author = {Zeng, Yuanyuan and Fang, Yixiang and Luo, Wensheng and Ma, Chenhao},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3725261},
        url = {https://dl.acm.org/doi/10.1145/3725261},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,845	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
927	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00013161079
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.2411888e-05
3,148	Finding Locally Densest Subgraphs: A Convex Programming Approach	2022	VLDB	7.707548e-05
3,254	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.5928992e-05
3,836	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	7.0827068e-05
4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.7229209e-05
4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.6355948e-05
4,903	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	6.4520708e-05
5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	6.0896788e-05
5,938	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	6.0343238e-05
6,292	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD	5.9251728e-05
6,636	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	5.8172769e-05
7,158	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.6858492e-05
7,418	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	5.6236086e-05
8,478	T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph	2023	SIGMOD	5.4170414e-05
8,650	Towards Generating Hop-constrained s-t Simple Path Graphs	2023	SIGMOD	5.3916003e-05
8,651	Distributed Set Reachability	2016	SIGMOD	5.3916003e-05
9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3201316e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,261	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD
2	4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB
3	1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
4	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
5	4,289	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD
6	352	On Graph Query Optimization in Large Networks	2010	VLDB
7	9,358	SkyGraph: Retrieving Regions of Interest using Skyline Subgraph Queries	2017	VLDB
8	7,418	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB
9	9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD
10	5,938	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD