Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach

Summary: MRPG proximity-graph approach for exact distance-based outlier detection in metric spaces. Supports arbitrary proximity graphs, enabling a main-memory index and significant speedups over the state-of-the-art on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6125
Venue: SIGMOD
Year: 2021
Pagerank: 5.2434488e-05
Overall Rank: 9,634 | 33.91%
DOI: 10.1145/3448016.3452782

Incoming Non-self Citations Over Time

Authors

1. Daichi Amagata (Japan Science and Technology Agency; Osaka University)
2. Makoto Onizuka (Osaka University)
3. Takahiro Hara (Osaka University)

BibTeX Citation

@inproceedings{amagata_sigmod21,
        title = {{Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach}},
        author = {Amagata, Daichi and Onizuka, Makoto and Hara, Takahiro},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452782},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452782},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,189	Adaptive Outlier Detection over Data Stream	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
693	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00014918477
1,557	Distance-based Outlier Detection in Data Streams	2016	VLDB	0.00010367451
2,756	NETS: Extremely Fast Outlier Detection from a Data Stream via Set-Based Processing	2019	VLDB	8.1604054e-05
3,135	Real-Time Distance-Based Outlier Detection in Data Streams	2021	VLDB	7.7214053e-05
4,627	Pivot-based Metric Indexing	2017	VLDB	6.5963674e-05
6,766	Sharing-Aware Outlier Analytics over High-Volume Data Streams	2016	SIGMOD	5.7802844e-05
7,715	Cache-oblivious High-performance Similarity Join	2019	SIGMOD	5.5606224e-05
11,664	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
2	2,660	Finding Intensional Knowledge of Distance-Based Outliers	1999	VLDB
3	3,135	Real-Time Distance-Based Outlier Detection in Data Streams	2021	VLDB
4	2,340	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB
5	10,189	Adaptive Outlier Detection over Data Stream	2026	SIGMOD
6	3,958	Continuous Outlier Detection in Data Streams: An Extensible Framework and State-Of-The-Art Algorithms	2013	SIGMOD
7	4,209	Outlier Detection for High Dimensional Data	2001	SIGMOD
8	693	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB
9	578	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD
10	9,952	Distance-Based Outlier Detection: Consolidation and Renewed Bearing	2010	VLDB