The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
LOCI: fast outlier detection using the local correlation integral
Abstract
Outlier detection is an integral part of data mining and has attracted much attention recently [M. Breunig et al., (2000)], [W. Jin et al., (2001)], [E. Knorr et al., (2000)]. We propose a new method for evaluating outlierness, which we call the local correlation integral (LOCI). As with the best previous methods, LOCI is highly effective for detecting outliers and groups of outliers (a.k.a. micro-clusters). In addition, it offers the following advantages and novelties: (a) It provides an automatic, data-dictated cutoff to determine whether a point is an outlier-in contrast, previous methods force users to pick cut-offs, without any hints as to what cut-off value is best for a given dataset. (b) It can provide a LOCI plot for each point; this plot summarizes a wealth of information about the data in the vicinity of the point, determining clusters, micro-clusters, their diameters and their inter-cluster distances. None of the existing outlier-detection methods can match this feature, because they output only a single number for each point: its outlierness score, (c) Our LOCI method can be computed as quickly as the best previous methods, (d) Moreover, LOCI leads to a practically linear approximate method, aLOCI (for approximate LOCI), which provides fast highly-accurate outlier detection. To the best of our knowledge, this is the first work to use approximate computations to speed up outlier detection. Experiments on synthetic and real world data sets show that LOCI and aLOCI can automatically detect outliers and micro-clusters, without user-required cut-offs, and that they quickly spot both expected and unexpected outliers.
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
Jain, A. K., Murty, M. N., & Flynn, P. J. (1999) · ACM Computing Surveys · doi:10.1145/331499.331504 · Cited by 13,199
Robust Regression and Outlier Detection
Piepel, G. F. (1989) · Technometrics · doi:10.1080/00401706.1989.10488524 · Cited by 6,144
Robust Regression and Outlier Detection
Rousseeuw, P. J., & Leroy, A. M. (1987) · Wiley Series in Probability and Statistics · doi:10.1002/0471725382 · Cited by 5,609
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
(1999) · Cited by 3,186
Hawkins, D. M. (1980) · doi:10.1007/978-94-015-3994-4 · Cited by 2,982
Barnett, V., Lewis, T., & Abeles, F. (1979) · Physics Today · doi:10.1063/1.2995737 · Cited by 2,824
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
Efficient algorithms for mining outliers from large data sets
Ramaswamy, S., Rastogi, R., & Shim, K. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335437 · Cited by 1,860
Atkinson, A., Barnett, V., & Lewis, T. (1995) · Journal of the Royal Statistical Society. Series A (Statistics in Society) · doi:10.2307/2983451 · Cited by 1,682
Cited by
Chandola, V., Banerjee, A., & Kumar, V. (2009) · ACM Computing Surveys · doi:10.1145/1541880.1541882 · Cited by 11,687
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
Pimentel, M. A. F., Clifton, D. A., Clifton, L., & Tarassenko, L. (2014) · Signal Processing · doi:10.1016/j.sigpro.2013.12.026 · Cited by 1,649
Graph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504
“The techniques can be classified into density-based [Breunig et al., 2000, Papadimitriou et al., 2003], distance-based [Aggarwal and Yu, 2001, Chaudhary et al., 2002, Ghoting et al., 2008, Knorr and Ng, 1998, Orair et al., 2010, Wang et al., 2011b], depth-based [Ruts and Rousseeuw, 1996],…”
MethodA 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
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
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
Reputation-based framework for high integrity sensor networks
Ganeriwal, S., Balzano, L. K., & Srivastava, M. B. (2008) · ACM Transactions on Sensor Networks · doi:10.1145/1362542.1362546 · Cited by 808
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
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
Anomaly detection in time series: a comprehensive evaluation
Schmidl, S., Wenig, P., & Papenbrock, T. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3538598.3538602 · Cited by 590
Reputation-based framework for high integrity sensor networks
Ganeriwal, S., & Srivastava, M. B. (2004) · Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks · doi:10.1145/1029102.1029115 · Cited by 583
oddball: Spotting Anomalies in Weighted Graphs
Akoglu, L., McGlohon, M., & Faloutsos, C. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13672-6_40 · Cited by 533
Self-citationProgress in Outlier Detection Techniques: A Survey
Wang, H., Bah, M. J., & Hammad, M. (2019) · IEEE Access · doi:10.1109/access.2019.2932769 · Cited by 523
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
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
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
Incremental Local Outlier Detection for Data Streams
Pokrajac, D., Lazarevic, A., & Latecki, L. J. (2007) · 2007 IEEE Symposium on Computational Intelligence and Data Mining · doi:10.1109/cidm.2007.368917 · Cited by 386
Anomaly detection in dynamic networks: a survey
Ranshous, S., Shen, S., Koutra, D., Harenberg, S., Faloutsos, C., & Samatova, N. F. (2015) · WIREs Computational Statistics · doi:10.1002/wics.1347 · Cited by 379
Self-citationHiCS: High Contrast Subspaces for Density-Based Outlier Ranking
Keller, F., Muller, E., & Bohm, K. (2012) · 2012 IEEE 28th International Conference on Data Engineering · doi:10.1109/icde.2012.88 · Cited by 373
A Review of Local Outlier Factor Algorithms for Outlier Detection in Big Data Streams
Alghushairy, O., Alsini, R., Soule, T., & Ma, X. (2020) · Big Data and Cognitive Computing · doi:10.3390/bdcc5010001 · Cited by 345
Outlier Detection: Methods, Models, and Classification
Boukerche, A., Zheng, L., & Alfandi, O. (2021) · ACM Computing Surveys · doi:10.1145/3381028 · Cited by 334
State of research in automatic as-built modelling
Pătrăucean, V., Armeni, I., Nahangi, M., Yeung, J., Brilakis, I., & Haas, C. (2015) · Advanced Engineering Informatics · doi:10.1016/j.aei.2015.01.001 · Cited by 328
Schubert, E., Zimek, A., & Kriegel, H.-P. (2014) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-012-0300-z · Cited by 300
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
Outlier Detection with Kernel Density Functions
Latecki, L. J., Lazarevic, A., & Pokrajac, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-73499-4_6 · Cited by 273
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
Multimodal Industrial Anomaly Detection via Hybrid Fusion
Wang, Y., Peng, J., Zhang, J., Yi, R., Wang, Y., & Wang, C. (2023) · 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr52729.2023.00776 · Cited by 246
Intrusion Detection in the IoT Under Data and Concept Drifts: Online Deep Learning Approach
Abdel Wahab, O. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2022.3167005 · Cited by 190
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
Statistical selection of relevant subspace projections for outlier ranking
Muller, E., Schiffer, M., & Seidl, T. (2011) · 2011 IEEE 27th International Conference on Data Engineering · doi:10.1109/icde.2011.5767916 · Cited by 126
Explaining Outliers by Subspace Separability
Micenkova, B., Ng, R. T., Dang, X.-H., & Assent, I. (2013) · 2013 IEEE 13th International Conference on Data Mining · doi:10.1109/icdm.2013.132 · Cited by 104
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
Local Outlier Detection with Interpretation
Dang, X. H., Micenková, B., Assent, I., & Ng, R. T. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40994-3_20 · Cited by 56
Outlying property detection with numerical attributes
Angiulli, F., Fassetti, F., Manco, G., & Palopoli, L. (2017) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-016-0458-x · Cited by 33
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
Metadata
- Authors
- Papadimitriou, S., Kitagawa, H., Gibbons, P. B., & Faloutsos, C.
- Venue
- Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405)
- Publisher
- IEEE
- Published
- 2004-05-13
- Pages
- 315-326
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2110784166
- Cited by
- 846
- References
- 25
- FWCI
- 16.91
- Type
- conference paper
- 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.