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)
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 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,141 | Effective Indexing for Dynamic Structural Graph Clustering | 2022 | VLDB | 5.6920203e-05 |
| 7,731 | Identifying Similar-Bicliques in Bipartite Graphs | 2022 | VLDB | 5.5566938e-05 |
| 7,862 | ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms | 2021 | VLDB | 5.5302333e-05 |
| 9,444 | An Efficient Algorithm for Distance-based Structural Graph Clustering | 2023 | SIGMOD | 5.2675506e-05 |
| 9,552 | Practical and Accurate Local Edge Differentially Private Graph Algorithms | 2025 | VLDB | 5.2528121e-05 |
| 9,690 | Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks | 2025 | VLDB | 5.2351259e-05 |
| 10,448 | Efficient Influential Community Search over Dynamic Graphs | 2026 | SIGMOD | 5.093636e-05 |
| 10,528 | Effective Durable Community Search in Large Temporal Graph | 2026 | VLDB | 5.093636e-05 |
| 11,102 | The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering | 2025 | VLDB | 5.093636e-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 |
|---|---|---|---|---|
| 291 | OPTICS: Ordering Points To Identify the Clustering Structure | 1999 | SIGMOD | 0.00022264197 |
| 2,482 | Efficient Structural Graph Clustering: An Index-Based Approach | 2018 | VLDB | 8.5183361e-05 |
| 2,839 | SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs | 2015 | VLDB | 8.066541e-05 |
| 3,616 | Parallel Local Graph Clustering | 2016 | VLDB | 7.2559471e-05 |
| 7,862 | ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms | 2021 | VLDB | 5.5302333e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 442 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB |
| 2 | 8,477 | Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs | 2025 | SIGMOD |
| 3 | 2,839 | SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs | 2015 | VLDB |
| 4 | 2,390 | Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing | 2013 | VLDB |
| 5 | 1,163 | Local Graph Sparsification for Scalable Clustering | 2011 | SIGMOD |
| 6 | 3,477 | Performance and Scalability of Indexed Subgraph Query Processing Methods | 2015 | VLDB |
| 7 | 3,616 | Parallel Local Graph Clustering | 2016 | VLDB |
| 8 | 9,444 | An Efficient Algorithm for Distance-based Structural Graph Clustering | 2023 | SIGMOD |
| 9 | 7,141 | Effective Indexing for Dynamic Structural Graph Clustering | 2022 | VLDB |
| 10 | 2,482 | Efficient Structural Graph Clustering: An Index-Based Approach | 2018 | VLDB |