Mining distance-based outliers in near linear time with randomization and a simple pruning rule

By Stephen D. Bay, Mark Schwabacher. Knowledge Discovery and Data Mining, 2003

748 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/79157c479db7cbf0cba2c6e197644b38aa0e80df

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Isolation-Based Anomaly Detection (2012, methodology): “ORCA [Bay and Schwabacher 2003] is an optimized nested-loop algorithm that has near linear time complexity.”
Quantitative Data Cleaning for Large Databases (2008, background): “, 2003]; Bay and Schwabacher present an algorithm with expected running time of O(N) for this outlier detection metric [Bay and Schwabacher, 2003].”
AdaBoost-Based Algorithm for Network Intrusion Detection (2008, background): “2, whereas 212 min is taken for the algorithm in [53].”
Interpreting and Unifying Outlier Scores (2011, neutral): “Scoring variants of the DB-outlier notion are proposed in [3] [8] [29] [40] [43] basically using the distances to the k-nearest neighbors (kNNs) or aggregates thereof.”
Sensor-Based Abnormal Human-Activity Detection (2008, background): “These approaches range from the computer vision area [6], [27], where variations of Markov models are designed to detect the out-of-norm behavior of users, to the data mining area [1], [12], where similarity or model-based approaches are employed to detect outliers.”
Distance-based detection and prediction of outliers (2006, methodology): “From this perspective, the solving set S is a learned model and can be seen as a compressed representation of D, analogously to sample compression schemes for a concept class [10] or to support vector extraction for classification tasks [24].”
A survey on unsupervised outlier detection in high‐dimensional numerical data (2012, methodology): “Finally, within each bin (as long as necessary), they use a variant of the nested loop algorithm [74], to derive the top-n outliers.”
Contextual Outlier Interpretation (2017, methodology): “Distance-based methods identify outliers as instances isolated far away from their neighbors [4, 7, 22, 29, 40].”
Loda: Lightweight on-line detector of anomalies (2016, methodology): “Other methods, such as Bay and Schwabacher (2003) assumes some additional knowledge which might not be available.”
HiCS: High Contrast Subspaces for Density-Based Outlier Ranking (2012, background): “1) a sensor node might be an outlier as it shows an abnormally high deviation w.r.t. air pollution index and noise level.”
Incremental Local Outlier Detection for Data Streams (2007, background): “network traffic monitoring, video surveillance, web usage logs) arrives continuously at an enormous pace thus posing a significant challenge to analyze it [36].”
k-means-: A Unified Approach to Clustering and Outlier Detection (2013, background): “However, an important point worth considering is that if there is no inherent clustering in the data it is unlikely that there exist any natural outliers.”
Local Search Methods for k-Means with Outliers (2017, background): “, separating the outlier detection from the clustering objective [2, 4, 7, 25, 26, 30, 37, 38].”
Outlier Analysis (2013, methodology): “The work in [60] designs a simple pruning technique in order to improve the efficiency of a k-nearest neighbor based outlier detection technique.”