Fast Outlier Detection Despite the Duplicates

Abstract

Given a large cloud of multi-dimensional points, and an off-the-shelf outlier detection method, why does it take a week to finish? After careful analysis, we discovered that duplicate points create subtle issues, that the literature has ignored: if d(max) is the multiplicity of the most over-plotted point, typical algorithms are quadratic on d(max). We propose several ways to eliminate the problem; we report wall-clock times and our time savings; and we show that our methods give either exact results, or highly accurate approximate ones.