Efficient algorithms for mining outliers from large data sets
Open accessAbstract
In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its kth nearest neighbor. We rank each point on the basis of its distance to its kth nearest neighbor and declare the top n points in this ranking to be outliers. In addition to developing relatively straightforward solutions to finding such outliers based on the classical nested-loop join and index join algorithms, we develop a highly efficient partition-based algorithm for mining outliers. This algorithm first partitions the input data set into disjoint subsets, and then prunes entire partitions as soon as it is determined that they cannot contain outliers. This results in substantial savings in computation. We present the results of an extensive experimental study on real-life and synthetic data sets. The results from a real-life NBA database highlight and reveal several expected and unexpected aspects of the database. The results from a study on synthetic data sets demonstrate that the partition-based algorithm scales well with respect to both data set size and data set dimensionality.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
All pre-model XAD techniques are model-agnostic except for Reference [173].
“As shown in Table 1, all pre-model XAD techniques are model-agnostic except for Reference [173].”
From A Survey on Explainable Anomaly Detection (2024) · cites this paper as [173]
The Introduction describes this paper’s method as distance-based and contrasts it with approaches requiring a postulated statistical model. Related Work says its outlier definition is independent of how clusters are identified. That runs contrary to treating this paper as the exception to model-agnostic pre-model techniques; the paper does not assess the other techniques in the citing document’s Table 1. (LLM, conf=0.84)
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measured[173] symbolic representation using PAA enables human-in-the-loop.
“Enables”
From A Survey on Explainable Anomaly Detection (2024) · cites this paper as [173]
The passages in Sections 5.2 and 6 describe clustering, outlier-mining algorithms, and their performance, not symbolic representation using PAA. Searches for the claim and for piecewise aggregate approximation or human interaction found no passage addressing whether PAA enables human-in-the-loop work. (LLM, conf=0.72)
Experimental — accuracy not yet measured[173] symbolic representation using PAA is only applicable to symbolic based AD such as HOT-SAX and RRA.
“Only applicable to”
From A Survey on Explainable Anomaly Detection (2024) · cites this paper as [173]
The Problem Definition and Notation section describes mining outliers from point data sets, while the Index-Based Join section discusses nearest-neighbor searches using a spatial index. Searches for PAA, symbolic representation, HOT-SAX, and RRA found no passage addressing whether PAA is applicable only to symbolic-based anomaly detection. (LLM, conf=0.76)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 16
- A. Arning, Rakesh Agrawal, and P. Raghavan. A lin- ear method for deviation detection in large databases. In Int'l Conference on Knowledge Discovery in Databases and Data Mining (KDD-95), Portland, Oregon, August 1996.
- Rakesh Agrawal, Heikki Mannila, Ramakrishnan Srikant, Hannu Toivonen, and A. Inkeri Verkamo. Fast Discovery of Association Rules, chapter 14. 1995.
- Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng, and Jorg Sander. Lof:indetifying density-based local outliers. In Proc. of the ACM SIGMOD Confer- ence on Management of Data, May 2000.
- N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The é -tree: an efficient and robust ac- cess method for points and rectangles. In Proc. of ACM SIGMOD, pages 322-331, Atlantic City, NJ, May 1990.
- V. Barnett and T. Lewis. Outliers in Statistical Data. John Wiley and Sons, New York, 1994.
- Martin Ester, Hans-Peter Kriegel, and Xiaowei Xu. A database interface for clustering in large spatial databases. In Int'l Conference on Knowledge Discov- ery in Databases and Data Mining (KDD-95), Mon- treal, Canada, August 1995.
- Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim. Cure: An efficient clustering algorithm for large databases. In Proc. of the ACM SIGMOD Conference on Management of Data, June 1998.
- Anil K. Jain and Richard C. Dubes. Algorithms for Clustering Data. Prentice Hall, Englewood Cliffs, New Jersey, 1988.
- Edwin Knorr and Raymond Ng. Algorithms for mining distance-based outliers in large datasets. In Proc. of the VLDB Conference, pages 392-403, New York, USA, September 1998.
- Edwin Knorr and Raymond Ng. Finding intensional knowledge of distance-based outliers. In Proc. of the VLDB Conference, pages 211-222, Edinburgh, UK, September 1999.
- Raymond T. Ng and Jiawei Han. Efficient and effective clustering methods for spatial data mining. In Proc. of the VLDB Conference, Santiago, Chile, September 1994.
- N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proc. of ACM SIGMOD, pages 71-79, San Jose, CA, 1995.
- Rajeev Rastogi and Kyuseok Shim. Public: A decision tree classifier that integrates building and pruning. In Proc. of the Int'l Conf. on Very Large Data Bases, New York, 1998.
- H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.
- S. Sarawagi, R. Agrawal, and N. Megiddo. Discovery- driven exploration of olap data cubes. In Proc. of the Sixth Int'l Conference on Extending Database Technology (EDBT), Valencia, Spain, March 1998.
- Tian Zhang, Raghu Ramakrishnan, and Miron Livny. Birch: An efficient data clustering method for very large databases. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 103-114, Montreal, Canada, June 1996.
Cited by
Sorted by citations
Chandola, V., Banerjee, A., & Kumar, V. (2009) · ACM Computing Surveys · doi:10.1145/1541880.1541882 · Cited by 11,687 · see citing works
LOF: identifying density-based local outliers
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335388 · Cited by 5,207 · see citing works
Deep Learning for Anomaly Detection: A Review
Pang, G., Shen, C., Cao, L., & Hengel, A. V. D. (2022) · ACM Computing Surveys · doi:10.1145/3439950 · Cited by 2,837 · see citing works
Outlier Detection: Methods, Models, and Classification
Boukerche, A., Zheng, L., & Alfandi, O. (2021) · ACM Computing Surveys · doi:10.1145/3381028 · Cited by 334 · see citing works
A Survey on Explainable Anomaly Detection
Li, Z., Zhu, Y., & Van Leeuwen, M. (2024) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3609333 · Cited by 139 · see citing works
“For example, KNN [170] defines objects with ‘far’ 𝑘-nearest neighbours as anomalies, LOF [26] treats objects with a low local density as anomalies, and Isolation Forest [121] considers ‘easily isolated’ objects as anomalies.”
Interpretable Anomaly Detection with DIFFI: Depth-based feature importance of Isolation Forest
Carletti, M., Terzi, M., & Susto, G. A. (2023) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2022.105730 · Cited by 118 · see citing works
Detecting outlying properties of exceptional objects
Angiulli, F., Fassetti, F., & Palopoli, L. (2009) · ACM Transactions on Database Systems · doi:10.1145/1508857.1508864 · Cited by 88 · see citing works
Mining outlying aspects on numeric data
Duan, L., Tang, G., Pei, J., Bailey, J., Campbell, A., & Tang, C. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0398-2 · Cited by 70 · see citing works
Contextual Outlier Interpretation
Liu, N., Shin, D., & Hu, X. (2018) · Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/341 · Cited by 74 · see citing works
A new data mining based network Intrusion Detection model
Gudadhe, M., Prasad, P., & Kapil Wankhade, L. (2010) · 2010 International Conference on Computer and Communication Technology (ICCCT) · doi:10.1109/iccct.2010.5640375 · Cited by 59 · see citing works
Explainable outlier detection: What, for Whom and Why?
Sejr, J. H., & Schneider-Kamp, A. (2021) · Machine Learning with Applications · doi:10.1016/j.mlwa.2021.100172 · Cited by 32 · see citing works
Prediction-based outlier detection with explanations
Chen, L.-C., Kuo, T.-T., Lai, W.-C., Lin, S.-D., & Tsai, C.-H. (2012) · 2012 IEEE International Conference on Granular Computing · doi:10.1109/grc.2012.6468672 · Cited by 2 · see citing works
- Authors
- Ramaswamy, S., Rastogi, R., & Shim, K.
- Affiliations
- Epiphany Inc., Palo Alto, CA
- Bell Laboratories, Murray Hill, NJ
- Korea Advanced Institute of Science and Technology (KR)
- ORCID
- Shim, Kyuseok
- Venue
- Proceedings of the 2000 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 2000-05-16
- Pages
- 427-438
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W4253461361
- Cited by
- 1,171
- References
- 0
- Citations by year
- 2026: 38 · 2025: 85 · 2024: 99 · 2023: 88 · 2022: 64 · 2021: 75 · 2020: 64 · 2019: 52 · 2018: 46 · 2017: 48 · 2016: 53 · 2015: 41 · 2014: 38 · 2013: 29 · 2012: 40
- FWCI
- 7.33
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM SIGMOD International Conference on Management of Data (SIGMOD) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Anomaly Detection Techniques and Applications
- Physical Sciences › Computer Science › Signal Processing › Data Management and Algorithms
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Database Systems and Queries
- Keywords
- outlier detection, distance-based outliers, pruning, nested loop join, large data sets, scalability
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
