2003 · 190 citations · 0 references
ComputingComputer ScienceData ScienceAlgorithmsData AnalyticsData MiningAnomaly DetectionApproximation AlgorithmsDimension ReductionDimensionality ReductionNearest Neighbor SearchOutlier DetectionAverage-case AnalysisDistance-based Outlier DetectionHigh-dimensional Anomaly DetectionHigh-dimensional Data MiningHigh-dimensional Outlier DetectionLinear-scaling AlgorithmsOutlier RemovalPruning
Defining outliers by their distance to neighboring examples is a popular approach to finding unusual examples in a data set. Recently, much work has been conducted with the goal of finding fast algorithms for this task. We show 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. We test our algorithm on real high-dimensional data sets with millions of examples and show that the near linear scaling holds over several orders of magnitude. Our average case analysis suggests that much of the efficiency is because the time to process non-outliers, which are the majority of examples, does not depend on the size of the data set.