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: 4638
Venue: SIGMOD
Year: 2013
Pagerank: 0.00019588834
Overall Rank: 588 | 95.92%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,256	Influential Community Search in Large Networks	2015	VLDB	0.00013009097
1,484	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011705344
1,487	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00011691164
2,219	The Input/Output Complexity of Triangle Enumeration	2014	PODS	9.2653868e-05
2,787	Scalable Distributed Subgraph Enumeration	2017	VLDB	8.1219297e-05
2,799	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD	8.109137e-05
2,856	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0120856e-05
3,067	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	7.6247945e-05
3,537	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	6.9929946e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
4,883	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8519327e-05
5,030	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.7445683e-05
5,529	Hypergraph Motifs: Concepts, Algorithms, and Discoveries	2020	VLDB	5.4569473e-05
5,782	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	5.3268721e-05
6,869	2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection	2017	PODS	4.8978627e-05
7,343	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	4.7511136e-05
7,450	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7218383e-05
8,538	On Asymptotic Cost of Triangle Listing in Random Graphs	2017	PODS	4.4893996e-05
8,809	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	4.4401156e-05
9,246	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	4.3648789e-05
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-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
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047955011
682	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.0001816451
2,439	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8181328e-05
3,675	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD	6.8500291e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,496	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	7.0376611e-05
389	Counting Triangles in Data Streams	2006	PODS	0.00024649634
8,538	On Asymptotic Cost of Triangle Listing in Random Graphs	2017	PODS	4.4893996e-05
12,049	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1905499e-05
5,043	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	5.7350154e-05
3,537	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	6.9929946e-05
2,219	The Input/Output Complexity of Triangle Enumeration	2014	PODS	9.2653868e-05
4,460	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.1592411e-05
9,088	Efficiently Enumerating Minimal Triangulations	2017	PODS	4.3940132e-05
1,348	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012461666