Distance-based Outlier Detection
MINGXI WU

Mining distance-based outlier attracts much research attention
for its distribution free assumption. Recently, much work has been
conducted with the goal of finding fast algorithms for this task. The
state-of-art algorithm achieves near linear performance but in the worst
case is still quadratic. We show that a simple sampling algorithm can
return an approximate answer with probabilistic accuracy guarantees in
O(NlogN) time.