会議発表論文

会議発表論文

text

Proceedings of the ACM SIGMOD International Conference on Management of Data. 2021, p. 36-48

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

Association for Computing Machinery

英語

text

2021-06-18

https://doi.org/10.1145/3448016.3452782

Distance-based outlier detection is widely adopted in many fields, e.g., data mining and machine learning, because it is unsupervised, can be employed in a generic metric space, and does not have any assumptions of data distributions. Data mining and machine learning applications face a challenge of dealing with large datasets, which requires efficient distance-based outlier detection algorithms. Due to the popularization of computational environments with large memory, it is possible to build a main-memory index and detect outliers based on it, which is a promising solution for fast distance-based outlier detection. Motivated by this observation, we propose a novel approach that exploits a proximity graph. Our approach can employ an arbitrary proximity graph and obtains a significant speed-up against state-of-the-art. However, designing an effective proximity graph raises a challenge, because existing proximity graphs do not consider efficient traversal for distance-based outlier detection. To overcome this challenge, we propose a novel proximity graph, MRPG. Our empirical study using real datasets demonstrates that MRPG detects outliers significantly faster than the state-of-the-art algorithms.

© 2021 ACM. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Amagata D., Onizuka M., Hara T.. Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach. Proceedings of the ACM SIGMOD International Conference on Management of Data , 36 (2021); https://doi.org/10.1145/3448016.3452782.

92849

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

Association for Computing Machinery

英語

2021-06-18

Proceedings of the ACM SIGMOD International Conference on Management of Data

36

48

https://doi.org/10.1145/3448016.3452782

https://hdl.handle.net/11094/92849