Online Outlier Exploration Over Large Datasets
Published 7 August 2015
Lei Cao, Mingrui Wei, Di Yang, Elke A. Rundensteiner
Citations31
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work presents the first online outlier exploration platform, called ONION, that enables analysts to effectively explore anomalies even in large datasets and confirms the effectiveness of ONION in recognizing "true" outliers.
Abstract
Traditional outlier detection systems process each individual outlier detection request instantiated with a particular parameter setting one at a time. This is not only prohibitively time-consuming for large datasets, but also tedious for analysts as they explore the data to hone in on the appropriate parameter setting and desired results.
Keywords
Computer Science
A density-based algorithm for discovering clusters in large spatial Databases with Noise
19,114 Citations1996Martin Ester, Hans‐Peter Kriegel +2 more
DBSCAN, a new clustering algorithm relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape, is presented which requires only one input parameter and supports the user in determining an appropriate value for it.
ACM Computing SurveysAnomaly detection
11,146 Citations2009Varun Chandola, Arindam Banerjee +1 more
This survey tries to provide a structured and comprehensive overview of the research on anomaly detection by grouping existing techniques into different categories based on the underlying approach adopted by each technique.
BIRCH
3,906 Citations1996Tian Zhang, Raghu Ramakrishnan +1 more
A data clustering method named BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) is presented, and it is demonstrated that it is especially suitable for very large databases.
LOF
3,862 Citations2000Markus Breunig, Hans‐Peter Kriegel +2 more
This paper contends that for many scenarios, it is more meaningful to assign to each object a degree of being an outlier, called the local outlier factor (LOF), and gives a detailed formal analysis showing that LOF enjoys many desirable properties.
Identification of Outliers
2,808 Citations1980D. M. Hawkins
A computer normalizes the one or more sets of historical data points and creates a first visual representation corresponding to the first set of the oneor more sets and the second set of additional points.
Introduction to Algorithms, third edition
2,317 Citations2009Thomas H. Cormen, Charles E. Leiserson +2 more
Pseudo-code explanation of the algorithms coupled with proof of their accuracy makes this book a great resource on the basic tools used to analyze the performance of algorithms.
Efficient and Effective Clustering Methods for Spatial Data Mining
1,788 Citations1994Raymond T. Ng, Jiawei Han
The analysis and experiments show that with the assistance of CLAHANS, these two algorithms are very effective and can lead to discoveries that are difficult to find with current spatial data mining algorithms.
Algorithms for Mining Distance-Based Outliers in Large Datasets
1,530 Citations1998Edwin M. Knorr, Raymond T. Ng
This paper provides formal and empirical evidence showing the usefulness of DB-outliers and presents two simple algorithms for computing such outliers, both having a complexity of O(k N’), k being the dimensionality and N being the number of objects in the dataset.
OPTICS
1,269 Citations1999Mihael Ankerst, Markus Breunig +2 more
A new algorithm is introduced for the purpose of cluster analysis which does not produce a clustering of a data set explicitly; but instead creates an augmented ordering of the database representing its density-based clustering structure.
LOCI: fast outlier detection using the local correlation integral
848 Citations2004Spiros Papadimitriou, Hiroyuki Kitagawa +2 more
Experiments 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.
Mining distance-based outliers in near linear time with randomization and a simple pruning rule
615 Citations2003Stephen D. Bay, Mark Schwabacher
This work shows that a simple nested loop algorithm that in the worst case is quadratic can give near linear time performance when the data is in random order and a simple pruning rule is used.
Lecture notes in computer scienceOutlier Detection in Axis-Parallel Subspaces of High Dimensional Data
306 Citations2009Hans‐Peter Kriegel, Peer Kröger +2 more
This work proposes an original outlier detection schema that detects outliers in varying subspaces of a high dimensional feature space and shows that it is superior to existing full-dimensional approaches and scales well to high dimensional databases.
Data Mining and Knowledge DiscoveryFast mining of distance-based outliers in high-dimensional datasets
196 Citations2008Amol Ghoting, Srinivasan Parthasarathy +1 more
RBRP is presented, a fast algorithm for mining distance-based outliers, particularly targeted at high-dimensional datasets, and demonstrates that it outperforms the state-of-the-art algorithm, often by an order of magnitude.
Proceedings of the VLDB EndowmentDistance-based outlier detection
110 Citations2010Gustavo Henrique Orair, Carlos H. C. Teixeira +3 more
A family of state of the art distance-based outlier detection algorithms are evaluated and a factorial design study highlights the important fact that no single optimization or combination of optimizations (factors) always dominates on all types of data.
IEEE Transactions on Aerospace and Electronic SystemsJointSTARS and GMTI: past, present and future
104 Citations1999J.N. Entzminger, Corbin Fowler +1 more
The program history is traced starting with the Army's Stand Off Target Acquisition System as it evolved through the Small Aerostat Surveillance System and the Assault Breaker/Pave Mover programs into the currently fielded Joint Surveillance and Target Attack System [JointSTARS], which more than proved its worth in the 1991 Gulf War.
ACM Transactions on Knowledge Discovery from DataDOLPHIN
104 Citations2009Fabrizio Angiulli, Fabio Fassetti
In this work a novel distance-based outlier detection algorithm, named DOLPHIN, working on disk-resident datasets and whose I/O cost corresponds to the cost of sequentially reading the input dataset file twice, is presented.
Algorithms for speeding up distance-based outlier detection
87 Citations2011Kanishka Bhaduri, Bryan Matthews +1 more
By combining simple but effective indexing and disk block accessing techniques, a sequential algorithm iOrca is developed that is up to an order- of-magnitude faster than the state-of-the-art.