Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach

Summary: Disk-based, tree-structured index for single-source distance queries in massive graphs, leveraging vertex-cover partitioning to enable I/O-efficient query processing. I/O-efficient construction algorithm with explicit CPU/I/O bounds; validated on real-world large graphs, showing scalable performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4607
Venue: SIGMOD
Year: 2012
Pagerank: 7.0678455e-05
Overall Rank: 3,857 | 73.54%
DOI: 10.1145/2213836.2213888

Incoming Non-self Citations Over Time

Authors

1. James Cheng (Nanyang Technological University)
2. Yiping Ke (Institute of High Performance Computing)
3. Shumo Chu (Nanyang Technological University)
4. Carter Cheng (Nanyang Technological University)

BibTeX Citation

@inproceedings{cheng_sigmod12,
        title = {{Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach}},
        author = {Cheng, James and Ke, Yiping and Chu, Shumo and Cheng, Carter},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213888},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213888},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
937	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013091546
1,123	Path Problems in Temporal Graphs	2014	VLDB	0.00012089975
1,533	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010467148
1,622	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010201102
1,983	Pregelix: Big(ger) Graph Analytics on A Dataflow Engine	2015	VLDB	9.3544951e-05
2,575	K-Reach: Who is in Your Small World	2012	VLDB	8.3982298e-05
2,871	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	8.0110616e-05
3,065	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.7989716e-05
3,612	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.2579119e-05
4,541	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB	6.6397712e-05
5,571	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.1686653e-05
7,764	Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling	2017	SIGMOD	5.5499989e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
674	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015081844

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
2	10,366	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD
3	1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
4	1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
5	4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD
6	352	On Graph Query Optimization in Large Networks	2010	VLDB
7	7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
8	9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB
9	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
10	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD