Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space

Summary: Introduces a fast, bounded-precision Euclidean OPTICS for fixed-dimensional data, replacing exact O(n^2) with approximations that have provable discrepancy guarantees. Runs in O(n log n) time, yields a linear-space index enabling near-optimal cluster-group-by queries, with empirical validation on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5568
Venue: SIGMOD
Year: 2018
Pagerank: 5.2864259e-05
Overall Rank: 5,894 | 59.00%
DOI: 10.1145/3183713.3196922

Incoming Non-self Citations Over Time

Authors

1. Junhao Gan
2. Yufei Tao

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,657	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.0187213e-05
11,185	FINEX: A Fast Index for Exact & Flexible Density-Based Clustering	2023	SIGMOD	4.1945683e-05
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-05
11,477	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
270	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029505642
3,264	Dynamic Density Based Clustering	2017	SIGMOD	7.3094408e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
961	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00015001792
8,895	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB	4.427268e-05
11,477	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.1945683e-05
7,480	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7180617e-05
1,595	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00011222442
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	5.5194222e-05
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-05
6,076	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.223696e-05
10,007	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS	4.1945683e-05
270	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029505642