The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Efficient algorithms for mining outliers from large data sets
Abstract
In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its k th nearest neighbor. We rank each point on the basis of its distance to its k th 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Algorithms for Clustering Data
Sarle, W. S. (1990) · Technometrics · doi:10.1080/00401706.1990.10484648 · Cited by 7,865
Algorithms for clustering data
Flury, B. (1989) · Journal of Statistical Planning and Inference · doi:10.1016/0378-3758(89)90033-5 · Cited by 6,432
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
Computational Geometry--An Introduction.
Atallah, M. J., Preparata, F. P., & Shamos, M. I. (1986) · Mathematics of Computation · doi:10.2307/2008200 · Cited by 4,238
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · Proceedings of the 1990 ACM SIGMOD international conference on Management of data · doi:10.1145/93597.98741 · Cited by 4,161
LOF: identifying density-based local outliers
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335388 · Cited by 4,149
BIRCH: an efficient data clustering method for very large databases
Zhang, T., Ramakrishnan, R., & Livny, M. (1996) · Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96 · doi:10.1145/233269.233324 · Cited by 3,935
Barnett, V., Lewis, T., & Abeles, F. (1979) · Physics Today · doi:10.1063/1.2995737 · Cited by 2,824
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,380
Fast discovery of association rules
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H. T. T., & Verkamo, A. I. (1996) · Knowledge Discovery and Data Mining · Cited by 2,376
Cited by
Chandola, V., Banerjee, A., & Kumar, V. (2009) · ACM Computing Surveys · doi:10.1145/1541880.1541882 · Cited by 11,687
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
A Survey of Outlier Detection Methodologies
Hodge, V., & Austin, J. (2004) · Artificial Intelligence Review · doi:10.1007/s10462-004-4304-y · Cited by 3,596
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
A Survey of Clustering Data Mining Techniques
Berkhin, P. (2006) · Grouping Multidimensional Data · doi:10.1007/3-540-28349-8_2 · Cited by 2,804
Isolation-Based Anomaly Detection
Liu, F. T., Ting, K. M., & Zhou, Z.-H. (2012) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2133360.2133363 · Cited by 2,063
An overview of anomaly detection techniques: Existing solutions and latest technological trends
Patcha, A., & Park, J.-M. (2007) · Computer Networks · doi:10.1016/j.comnet.2007.02.001 · Cited by 1,561
Efficient algorithms for mining outliers from large data sets
Ramaswamy, S., Rastogi, R., & Shim, K. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335437 · Cited by 1,171
Self-citationDiscovering cluster-based local outliers
He, Z., Xu, X., & Deng, S. (2003) · Pattern Recognition Letters · doi:10.1016/s0167-8655(03)00003-5 · Cited by 1,055
A Comparative Evaluation of Unsupervised Anomaly Detection Algorithms for Multivariate Data
Goldstein, M., & Uchida, S. (2016) · PLOS ONE · doi:10.1371/journal.pone.0152173 · Cited by 1,032
Outlier detection for high dimensional data
Aggarwal, C. C., & Yu, P. S. (2001) · Proceedings of the 2001 ACM SIGMOD international conference on Management of data · doi:10.1145/375663.375668 · Cited by 1,029
Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection
Campello, R. J. G. B., Moulavi, D., Zimek, A., & Sander, J. (2015) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2733381 · Cited by 915
A survey on unsupervised outlier detection in high‐dimensional numerical data
Zimek, A., Schubert, E., & Kriegel, H. (2012) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.11161 · Cited by 864
A Comparative Study of Anomaly Detection Schemes in Network Intrusion Detection
Lazarevic, A., Ertoz, L., Kumar, V., Ozgur, A., & Srivastava, J. (2003) · Proceedings of the 2003 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972733.3 · Cited by 865
LOCI: fast outlier detection using the local correlation integral
Papadimitriou, S., Kitagawa, H., Gibbons, P. B., & Faloutsos, C. (2004) · Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405) · doi:10.1109/icde.2003.1260802 · Cited by 846
Fast Outlier Detection in High Dimensional Spaces
Angiulli, F., & Pizzuti, C. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45681-3_2 · Cited by 836
Angle-based outlier detection in high-dimensional data
Kriegel, H.-P., Schubert, M., & Zimek, A. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401946 · Cited by 828
Outlier Detection Techniques for Wireless Sensor Networks: A Survey
Zhang, Y., Meratnia, N., & Havinga, P. (2010) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2010.021510.00088 · Cited by 797
On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study
Campos, G. O., Zimek, A., Sander, J., Campello, R. J. G. B., Micenková, B., Schubert, E., Assent, I., & Houle, M. E. (2016) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-015-0444-8 · Cited by 735
Anomaly Detection for Discrete Sequences: A Survey
Chandola, V., Banerjee, A., & Kumar, V. (2012) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.235 · Cited by 715
Outlier Detection Using Replicator Neural Networks
Hawkins, S., He, H., Williams, G., & Baxter, R. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-46145-0_17 · Cited by 710
DeepAnT: A Deep Learning Approach for Unsupervised Anomaly Detection in Time Series
Munir, M., Siddiqui, S. A., Dengel, A., & Ahmed, S. (2019) · IEEE Access · doi:10.1109/access.2018.2886457 · Cited by 696
Feature bagging for outlier detection
Lazarevic, A., & Kumar, V. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081891 · Cited by 656
Mining distance-based outliers in near linear time with randomization and a simple pruning rule
Bay, S. D., & Schwabacher, M. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956758 · Cited by 613
Greenhouse gas emissions from lakes and impoundments: Upscaling in the face of global change
DelSontro, T., Beaulieu, J. J., & Downing, J. A. (2018) · Limnology and Oceanography Letters · doi:10.1002/lol2.10073 · Cited by 577
Similarity Measures for Categorical Data: A Comparative Evaluation
Boriah, S., Chandola, V., & Kumar, V. (2008) · Proceedings of the 2008 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972788.22 · Cited by 575
Unsupervised Machine Learning for Networking: Techniques, Applications and Research Challenges
Usama, M., Qadir, J., Raza, A., Arif, H., Yau, K.-L. A., Elkhatib, Y., Hussain, A., & Al-Fuqaha, A. (2019) · IEEE Access · doi:10.1109/access.2019.2916648 · Cited by 575
Enhancing Effectiveness of Outlier Detections for Low Density Patterns
Tang, J., Chen, Z., Fu, A. W.-C., & Cheung, D. W. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47887-6_53 · Cited by 552
A survey of anomaly detection techniques in financial domain
Ahmed, M., Mahmood, A. N., & Islam, M. R. (2016) · Future Generation Computer Systems · doi:10.1016/j.future.2015.01.001 · Cited by 528
Halder, R. K., Uddin, M. N., Uddin, M. A., Aryal, S., & Khraisat, A. (2024) · Journal of Big Data · doi:10.1186/s40537-024-00973-y · Cited by 520
ECOD: Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functions
Li, Z., Zhao, Y., Hu, X., Botta, N., Ionescu, C., & Chen, G. H. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3159580 · Cited by 494
LoOP: local outlier probabilities
Kriegel, H.-P., Kröger, P., Schubert, E., & Zimek, A. (2009) · Proceedings of the 18th ACM conference on Information and knowledge management · doi:10.1145/1645953.1646195 · Cited by 492
Trajectory Outlier Detection: A Partition-and-Detect Framework
Lee, J.-G., Han, J., & Li, X. (2008) · 2008 IEEE 24th International Conference on Data Engineering · doi:10.1109/icde.2008.4497422 · Cited by 443
A hybrid machine learning approach to network anomaly detection
Shon, T., & Moon, J. (2007) · Information Sciences · doi:10.1016/j.ins.2007.03.025 · Cited by 440
Outlier Detection with Autoencoder Ensembles
Chen, J., Sathe, S., Aggarwal, C., & Turaga, D. (2017) · Proceedings of the 2017 SIAM International Conference on Data Mining · doi:10.1137/1.9781611974973.11 · Cited by 438
Enhancing one-class support vector machines for unsupervised anomaly detection
Amer, M., Goldstein, M., & Abdennadher, S. (2013) · Proceedings of the ACM SIGKDD Workshop on Outlier Detection and Description · doi:10.1145/2500853.2500857 · Cited by 427
A comprehensive survey of anomaly detection techniques for high dimensional big data
Thudumu, S., Branch, P., Jin, J., & Singh, J. (2020) · Journal of Big Data · doi:10.1186/s40537-020-00320-x · Cited by 425
Ranking Outliers Using Symmetric Neighborhood Relationship
Jin, W., Tung, A. K. H., Han, J., & Wang, W. (2006) · Lecture Notes in Computer Science · doi:10.1007/11731139_68 · Cited by 415
A New Local Distance-Based Outlier Detection Approach for Scattered Real-World Data
Zhang, K., Hutter, M., & Jin, H. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-01307-2_84 · Cited by 392
COPOD: Copula-Based Outlier Detection
Li, Z., Zhao, Y., Botta, N., Ionescu, C., & Hu, X. (2020) · 2020 IEEE International Conference on Data Mining (ICDM) · doi:10.1109/icdm50108.2020.00135 · Cited by 387
Song, X., Wu, M., Jermaine, C., & Ranka, S. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.1009 · Cited by 374
Outlier mining in large high-dimensional data sets
Angiulli, F., & Pizzuti, C. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.31 · Cited by 365
Brito, L. C., Susto, G. A., Brito, J. N., & Duarte, M. A. V. (2022) · Mechanical Systems and Signal Processing · doi:10.1016/j.ymssp.2021.108105 · Cited by 343
Generative Adversarial Active Learning for Unsupervised Outlier Detection
Liu, Y., Li, Z., Zhou, C., Jiang, Y., Sun, J., Wang, M., & He, X. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2905606 · Cited by 335
Mining top-n local outliers in large databases
Jin, W., Tung, A. K. H., & Han, J. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502554 · Cited by 328
Big data analytics for preventive medicine
Razzak, M. I., Imran, M., & Xu, G. (2020) · Neural Computing and Applications · doi:10.1007/s00521-019-04095-y · Cited by 327
Outlier detection by active learning
Abe, N., Zadrozny, B., & Langford, J. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150459 · Cited by 322
A local density-based approach for outlier detection
Tang, B., & He, H. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.02.039 · Cited by 301
Schubert, E., Zimek, A., & Kriegel, H.-P. (2014) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-012-0300-z · Cited by 300
Anomaly detection in streaming environmental sensor data: A data-driven modeling approach
Hill, D. J., & Minsker, B. S. (2010) · Environmental Modelling & Software · doi:10.1016/j.envsoft.2009.08.010 · Cited by 300
Distance-based detection and prediction of outliers
Angiulli, F., Basta, S., & Pizzuti, C. (2006) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2006.29 · Cited by 291
Learning Discriminative Reconstructions for Unsupervised Outlier Removal
Xia, Y., Cao, X., Wen, F., Hua, G., & Sun, J. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.177 · Cited by 285
Ensembles for unsupervised outlier detection: challenges and research questions a position paper
Zimek, A., Campello, R. J. G. B., & Sander, J. (2014) · ACM SIGKDD Explorations Newsletter · doi:10.1145/2594473.2594476 · Cited by 278
Interpreting and Unifying Outlier Scores
Kriegel, H.-P., Kroger, P., Schubert, E., & Zimek, A. (2011) · Proceedings of the 2011 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972818.2 · Cited by 266
Map building with mobile robots in dynamic environments
Hahnel, D., Triebel, R., Burgard, W., & Thrun, S. (2004) · 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422) · doi:10.1109/robot.2003.1241816 · Cited by 266
Zheng, Q., Yang, M., Yang, J., Zhang, Q., & Zhang, X. (2018) · IEEE Access · doi:10.1109/access.2018.2810849 · Cited by 259
Distributed Anomaly Detection in Wireless Sensor Networks
Rajasegarar, S., Leckie, C., Palaniswami, M., & Bezdek, J. (2006) · 2006 10th IEEE Singapore International Conference on Communication Systems · doi:10.1109/iccs.2006.301508 · Cited by 256
FP-outlier: Frequent pattern based outlier detection
He, Z., Xu, X., Huang, Z., & Deng, S. (2005) · Computer Science and Information Systems · doi:10.2298/csis0501103h · Cited by 188
A comprehensive survey of numeric and symbolic outlier mining techniques
Agyemang, M., Barker, K., & Alhajj, R. (2006) · Intelligent Data Analysis · doi:10.3233/ida-2006-10604 · Cited by 164
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
Machine learning with a reject option: A survey
Hendrickx, K., Perini, L., Van der Plas, D., Meert, W., & Davis, J. (2024) · Machine Learning · doi:10.1007/s10994-024-06534-x · Cited by 134
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
Mining class outliers: concepts, algorithms and applications in CRM
He, Z., Xu, X., Huang, J. Z., & Deng, S. (2004) · Expert Systems with Applications · doi:10.1016/j.eswa.2004.07.002 · Cited by 79
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
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
A Survey of Privacy-Preserving Methods Across Vertically Partitioned Data
Vaidya, J. (2008) · Advances in Database Systems · doi:10.1007/978-0-387-70992-5_14 · Cited by 46
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
Metadata
- Authors
- Ramaswamy, S., Rastogi, R., & Shim, K.
- Venue
- ACM SIGMOD Record
- Published
- 2000-05-16
- Volume
- 29
- Issue
- 2
- Pages
- 427-438
- ISSN
- 0163-5808 (ISSN-L)
- OpenAlex
- W2129281431
- Cited by
- 1,860
- References
- 23
- FWCI
- 19.58
- Type
- journal article
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.