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: 5630
Venue: SIGMOD
Year: 2018
Pagerank: 6.0613257e-05
Overall Rank: 5,867 | 59.75%
DOI: 10.1145/3183713.3196922

Incoming Non-self Citations Over Time

Authors

1. Junhao Gan (University of Queensland)
2. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{gan_sigmod18,
        title = {{Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space}},
        author = {Gan, Junhao and Tao, Yufei},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196922},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196922},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,423	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.7107949e-05
8,733	FINEX: A Fast Index for Exact & Flexible Density-Based Clustering	2023	SIGMOD	5.3766157e-05
11,664	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	5.093636e-05
11,675	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	5.093636e-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
291	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00022264197
3,020	Dynamic Density Based Clustering	2017	SIGMOD	7.8445412e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,034	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB
2	10,153	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS
3	11,675	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD
4	8,070	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD
5	1,646	Fast Algorithms for Projected Clustering	1999	SIGMOD
6	5,294	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD
7	11,664	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD
8	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
9	10,179	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS
10	291	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD