Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure

Summary: TriParts introduces triangle preservation as a streaming graph-partitioning objective, retaining community structure alongside balance and low replication. Bloom Filters, Triangle Map, and High Degree Map yield up to 4–8.3× more local triangles than DBH/HDRF on 1.6B-edge graphs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14125
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,903 | 25.20%
DOI: 10.14778/3746405.3746423

Incoming Non-self Citations Over Time

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

Authors

1. Ruchi Bhoot (Indian Institute of Science)
2. Tuhin Khare (Georgia Institute of Technology)
3. Manoj Agarwal (GiKA.AI)
4. Siddharth Jaiswal (Indian Institute of Technology)
5. Yogesh Simmhan (Indian Institute of Science)

BibTeX Citation

@article{bhoot_vldb25,
        title = {{Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure}},
        author = {Bhoot, Ruchi and Khare, Tuhin and Agarwal, Manoj and Jaiswal, Siddharth and Simmhan, Yogesh},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {9},
        pages = {2992--3006},
        doi = {10.14778/3746405.3746423},
        url = {https://doi.org/10.14778/3746405.3746423},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
389	One Trillion Edges: Graph Processing at Facebook-Scale	2015	VLDB	0.00019386526
1,432	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.0001080346
2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.9260308e-05
2,325	Giraph Unchained: Barrierless Asynchronous Parallel Execution in Pregel-like Graph Processing Systems	2015	VLDB	8.7495171e-05
2,332	LEOPARD: Lightweight Edge-Oriented Partitioning and Replication for Dynamic Graphs	2016	VLDB	8.7410236e-05
4,365	Application Driven Graph Partitioning	2020	SIGMOD	6.740899e-05
5,811	Incrementalization of Graph Partitioning Algorithms	2020	VLDB	6.0782651e-05
7,277	Real Time Discovery of Dense Clusters in Highly Dynamic Graphs: Identifying Real World Events in Highly Dynamic Environments	2012	VLDB	5.6581746e-05
9,053	CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics	2025	VLDB	5.3251649e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,847	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB
2	2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB
3	10,411	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD
4	8,991	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
5	5,252	Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner	2017	VLDB
6	3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB
7	10,877	Efficient and Adaptive Estimation of Local Triadic Coefficients	2025	VLDB
8	458	Counting Triangles in Data Streams	2006	PODS
9	4,500	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
10	5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD