Research map / Learning theory and algorithms / Clustering
Scalable DBSCAN with Random Projections
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes sDBSCAN, a random-projection-based DBSCAN for cosine distance (extended to L2, L1, χ2, JS via random features) that approximates core points and ε-neighborhoods in subquadratic time, plus sOPTICS for guiding ε selection.
Problem
DBSCAN and OPTICS require O(n^2) neighborhood queries and memory in high dimensions, making them infeasible on million-point datasets; choosing ε is also sensitive.
Approach
Use a large number of Gaussian random projections and keep only the top-k closest/furthest random vectors per point and top-m points per random vector, using extreme order statistics (CEOs) to find core points and approximate ε-neighborhoods with O(k·minPts) distance computations; add a sOPTICS reachability visualization to guide ε.
Key results
- On Mnist with cosine distance, sDBSCAN reaches 43% AMI, matching scikit-learn DBSCAN, and runs in 8.8s on 1 thread versus 86s for 64-thread scikit-learn.
- On Mnist8m, sDBSCAN-1NN reaches up to 38% NMI on χ2 within 15 minutes on a single 32-core machine, versus 41% for kernel k-means run on a 32-node supercomputer.
- sOPTICS runs in under 3 seconds on Mnist with L2 (64 threads) while scikit-learn OPTICS takes 1.5 hours; sOPTICS runs in 2 min on Pamap2 and 11 min on Mnist8m.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace scikit-learn DBSCAN with sDBSCAN | DBSCAN · Mnist, cosine | time: 86s -> 8.8s | Helped |
| replace sngDBSCAN with sDBSCAN | DBSCAN · Mnist, cosine | AMI: 33% -> 43% | Helped |
| use sDBSCAN instead of DBSCAN | DBSCAN · Pamap2, L1 | time: 29.3 min -> 0.3 min | Helped |
| use sDBSCAN instead of DBSCAN | DBSCAN · Pamap2, L1 | NMI: 50% -> 46% | Hurt |
| use sDBSCAN instead of sngDBSCAN | DBSCAN · Pamap2, L1 | NMI: 40% -> 46% | Helped |
| add the approximate 1NN heuristic (ablation) | sDBSCAN · Mnist8m, L2 | NMI: 25% -> 36% | Helped |
| add the approximate 1NN heuristic (ablation) | sDBSCAN · Mnist8m, cosine | NMI: 32% -> 37% | Helped |
| increase m and reduce k at a fixed candidate budget (ablation) | sDBSCAN · Mnist, cosine | NMI: 69% -> 76% -> 81% -> 86% -> 88% -> 91% | Helped |
| use k=2, m=2,000 rather than k=1, m=2,000 (ablation) | sDBSCAN · Mnist, cosine | NMI: 91% -> 95% | Helped |
Surprising findings
- On Pamap2 with cosine distance, DBSCAN at ε=0.005 gives 47% AMI but only 37% at ε=0.01, showing high ε sensitivity.
- sDBSCAN with cosine distance on Pamap2 reaches only 34% NMI, lower than sngDBSCAN and DBSCAN, while L1 gives better results.
Limitations
- Theoretical guarantees rely on assumptions (cluster not thin, Lemma 3 independence assumption) and large D, and the heuristic m=O(minPts) is used in practice.
- sDBSCAN can miss border points, leading to accuracy loss on datasets with many border points (motivating sDBSCAN-1NN).
- Accuracy drops relative to exact DBSCAN for small m, k; some datasets (Pamap2 cosine) show lower NMI than baselines.
Experimental setup
Datasets: Mnist Pamap2 Mnist8m
Benchmarks: Mnist Pamap2 Mnist8m
Metrics: AMI NMI running time
Baselines: scikit-learn DBSCAN scikit-learn OPTICS pDBSCAN uDBSCAN++ kDBSCAN++ sngDBSCAN kernel k-means
Builds on: DBSCAN OPTICS CEOs DBSCAN++ sngDBSCAN random Fourier features
Closest papers by meaning
- DBSCAN++: Towards fast and scalable density clustering (ICML 2019 · similarity 0.91)
- Faster DBSCAN via subsampled similarity queries (NeurIPS 2020 · similarity 0.89)
- The SpectACl of Nonconvex Clustering: A Spectral Approach to Density-Based Clustering (AAAI 2019 · similarity 0.86)
- Enhanced Denesity Peak Clustering for High-Dimensional Data (AAAI 2025 · similarity 0.83)
- You Can Trust Your Clustering Model: A Parameter-free Self-Boosting Plug-in for Deep Clustering (NeurIPS 2025 · similarity 0.83)
- Breaking the Reclustering Barrier in Centroid-based Deep Clustering (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.