SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs

Summary: SCAN++ introduces a DTAR (directly two-hop-away reachable node) data structure to accelerate clustering, hubs, and outlier detection on large-scale graphs. By limiting density computations to DTAR-relevant two-hop neighbors and sharing evaluations, it preserves SCAN’s results while delivering substantial runtime gains on real and synthetic graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10998
Venue: VLDB
Year: 2015
Pagerank: 8.2356874e-05
Overall Rank: 2,718 | 81.12%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,440	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.8166939e-05
4,488	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.139905e-05
4,654	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.0129362e-05
6,987	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB	4.8669464e-05
9,379	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD	4.3439594e-05
10,280	FB*: A Compact Index for Efficient and Exact Density-based Clustering	2026	VLDB	4.1905499e-05
11,795	Scaling Locally Linear Embedding	2017	SIGMOD	4.1905499e-05
13,350	Fast Algorithm for the Lasso based L1-Graph Construction	2017	VLDB	-

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019040811
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047955011
11,963	Scaling Manifold Ranking Based Image Retrieval	2015	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
313	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.0002809849
10,072	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.1905499e-05
11,470	Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach	2021	SIGMOD	4.1905499e-05
10,562	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	4.1905499e-05
2,541	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB	8.5710863e-05
4,341	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	6.268429e-05
4,488	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.139905e-05
6,987	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB	4.8669464e-05
2,440	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.8166939e-05
9,379	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD	4.3439594e-05