Database Paper Browser

Back to papers

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
4637
Venue
SIGMOD
Year
2013
Pagerank
0.00019576567
Overall Rank
589 | 95.91%
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,257 Influential Community Search in Large Networks 2015 VLDB 0.00013020648
1,484 Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks 2019 VLDB 0.00011714263
1,500 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00011674394
2,215 The Input/Output Complexity of Triangle Enumeration 2014 PODS 9.2717602e-05
2,801 Scalable Distributed Subgraph Enumeration 2017 VLDB 8.0992955e-05
2,849 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0195487e-05
2,910 DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine 2016 SIGMOD 7.9266529e-05
3,063 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 7.6321424e-05
3,534 OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs 2014 SIGMOD 6.9997025e-05
4,432 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.1938383e-05
4,836 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 5.8896897e-05
4,879 Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage 2018 VLDB 5.8575676e-05
5,518 Hypergraph Motifs: Concepts, Algorithms, and Discoveries 2020 VLDB 5.4621935e-05
5,773 I/O-Efficient Butterfly Counting at Scale 2023 SIGMOD 5.3319911e-05
6,867 2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection 2017 PODS 4.9025083e-05
7,346 I/O Efficient ECC Graph Decomposition via Graph Reduction 2016 VLDB 4.7556749e-05
7,451 Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks 2023 SIGMOD 4.7263711e-05
8,540 On Asymptotic Cost of Triangle Listing in Random Graphs 2017 PODS 4.4937074e-05
8,809 Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks 2024 VLDB 4.4443756e-05
9,239 Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs 2024 VLDB 4.3690661e-05
9,483 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 4.3341665e-05
Previous Page 1 / 1 Next

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
108 Truss Decomposition in Massive Networks 2012 VLDB 0.00048300163
110 On Triangulation-based Dense Neighborhood Graph Discovery 2011 VLDB 0.00047892924
686 Finding Maximal Cliques in Massive Networks by H*-graph 2010 SIGMOD 0.00018178029
2,437 gSketch: On Query Estimation in Graph Streams 2012 VLDB 8.8231651e-05
3,677 Efficient External-Memory Bisimulation on DAGs 2012 SIGMOD 6.8533416e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,492 Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs 2022 VLDB 7.044442e-05
392 Counting Triangles in Data Streams 2006 PODS 0.00024556183
8,540 On Asymptotic Cost of Triangle Listing in Random Graphs 2017 PODS 4.4937074e-05
12,041 I/O Efficient: Computing SCCs in Massive Graphs 2013 SIGMOD 4.1945683e-05
5,046 Better Algorithms for Counting Triangles in Data Streams 2016 PODS 5.7405307e-05
3,534 OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs 2014 SIGMOD 6.9997025e-05
2,215 The Input/Output Complexity of Triangle Enumeration 2014 PODS 9.2717602e-05
4,459 Efficient Bi-triangle Counting for Large Bipartite Networks 2021 VLDB 6.1651553e-05
9,091 Efficiently Enumerating Minimal Triangulations 2017 PODS 4.39823e-05
1,344 Counting and Sampling Triangles from a Graph Stream 2013 VLDB 0.00012473724