Parallel Index-Based Structural Graph Clustering and Its Approximation

Summary: Parallel index-based SCAN for large graphs using GS*-Index enables precomputation to accelerate SCAN parameter sweeps. Integer-sort acceleration yields logarithmic-span construction and queries; LSH-based approximate SCAN with guarantees achieves 5–32× query speedups and 50–151× index speedups vs GS*-Index, beating ppSCAN. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6109d05a8227328b
Venue: SIGMOD
Year: 2021
Pagerank: 6.657571e-05
Overall Rank: 4,308 | 71.13%
DOI: 10.1145/3448016.3457278

Incoming Non-self Citations Over Time

Authors

1. Tom Tseng (Massachusetts Institute of Technology)
2. Laxman Dhulipala (Massachusetts Institute of Technology)
3. Julian Shun (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{tseng_sigmod21,
        title = {{Parallel Index-Based Structural Graph Clustering and Its Approximation}},
        author = {Tseng, Tom and Dhulipala, Laxman and Shun, Julian},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457278},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457278},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,309	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB	5.5432822e-05
7,915	Identifying Similar-Bicliques in Bipartite Graphs	2022	VLDB	5.4114919e-05
7,986	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.3960574e-05
9,083	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD	5.209913e-05
9,336	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	5.1783355e-05
9,766	Practical and Accurate Local Edge Differentially Private Graph Algorithms	2025	VLDB	5.115551e-05
10,394	Effective Structurally Similar Community Search in Large Temporal Graphs	2027	SIGMOD	4.9605343e-05
10,708	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.9605343e-05
10,783	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.9605343e-05
11,510	The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering	2025	VLDB	4.9605343e-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
300	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00021743411
2,470	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.4015437e-05
2,815	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB	7.9544959e-05
3,697	Parallel Local Graph Clustering	2016	VLDB	7.0690317e-05
7,986	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.3960574e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	440	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
2	8,087	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD
3	2,815	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB
4	2,369	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB
5	1,179	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD
6	3,506	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB
7	3,697	Parallel Local Graph Clustering	2016	VLDB
8	9,083	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD
9	7,309	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB
10	2,470	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB