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: 5569
Venue: SIGMOD
Year: 2018
Pagerank: 5.3111132e-05
Overall Rank: 5,827 | 59.51%
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,654	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.0129362e-05
8,528	FINEX: A Fast Index for Exact & Flexible Density-Based Clustering	2023	SIGMOD	4.4893996e-05
11,469	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1905499e-05
11,481	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.1905499e-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
263	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029955858
3,078	Dynamic Density Based Clustering	2017	SIGMOD	7.6041723e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
918	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00015286593
8,895	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB	4.423024e-05
11,481	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.1905499e-05
7,479	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7135369e-05
1,596	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00011210688
11,469	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1905499e-05
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	5.5162242e-05
6,073	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.2215154e-05
10,006	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS	4.1905499e-05
263	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029955858