Massive Graph Triangulation

Summary: Massive Graph Triangulation: I/O-efficient triangle listing for graphs that don't fit memory; finds all 3-vertex cliques. New algorithm provably I/O- and CPU-efficient, input-assumption-free, with a radically different approach, achieving ~10x speedups over prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hbe0e75095c1e469d
Venue: SIGMOD
Year: 2013
Pagerank: 0.00015740352
Overall Rank: 600 | 95.97%
DOI: 10.1145/2463676.2463704

Incoming Non-self Citations Over Time

Authors

1. Xiaocheng Hu (Chinese University of Hong Kong)
2. Yufei Tao (Chinese University of Hong Kong; Korea Advanced Institute of Science and Technology)
3. Chin-Wan Chung (Korea Advanced Institute of Science and Technology)

BibTeX Citation

@inproceedings{hu_sigmod13,
        title = {{Massive Graph Triangulation}},
        author = {Hu, Xiaocheng and Tao, Yufei and Chung, Chin-Wan},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2463704},
        url = {https://dl.acm.org/doi/10.1145/2463676.2463704},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,007	Influential Community Search in Large Networks	2015	VLDB	0.00012556573
1,046	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012319866
1,222	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011463714
2,020	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.1729558e-05
2,043	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1406885e-05
2,101	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD	9.0476814e-05
2,215	The Input/Output Complexity of Triangle Enumeration	2014	PODS	8.8194236e-05
2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.1531412e-05
3,380	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	7.3567664e-05
3,539	Hypergraph Motifs: Concepts, Algorithms, and Discoveries	2020	VLDB	7.2173698e-05
4,475	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.5838041e-05
4,487	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	6.5786974e-05
5,554	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	6.0858703e-05
5,558	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	6.0850942e-05
6,211	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	5.8487355e-05
6,957	2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection	2017	PODS	5.6341313e-05
7,602	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	5.4868396e-05
8,178	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	5.382671e-05
8,907	On Asymptotic Cost of Triangle Listing in Random Graphs	2017	PODS	5.2559789e-05
9,571	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	5.1571823e-05
9,805	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.1257999e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
265	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022748633
645	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015213733
2,420	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4898523e-05
4,433	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD	6.6015942e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,743	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB
2	462	Counting Triangles in Data Streams	2006	PODS
3	8,907	On Asymptotic Cost of Triangle Listing in Random Graphs	2017	PODS
4	12,530	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD
5	5,232	Better Algorithms for Counting Triangles in Data Streams	2016	PODS
6	3,380	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD
7	2,215	The Input/Output Complexity of Triangle Enumeration	2014	PODS
8	4,044	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB
9	9,516	Efficiently Enumerating Minimal Triangulations	2017	PODS
10	1,121	Counting and Sampling Triangles from a Graph Stream	2013	VLDB