Linear time identification of local and global outliers

Abstract Anomaly detection methods differ in their time complexity, sensitivity to data dimensions, and their ability to detect local/global outliers. The recently proposed algorithm FiRE is a ’sketching’ based linear-time algorithm for identifying global outliers. This work details FiRE.1, an extended implementation of FiRE that fares well on local outliers as well. We provide an extensive comparison with 18 state-of-the-art anomaly detection algorithms on a diverse collection of 1000 annotated datasets. Five different evaluation metrics have been employed. FiRE.1’s performance was particularly remarkable on datasets featuring a large number of local outliers. In the sequel, we propose a new ”outlierness” criterion to infer the local or global identity of outliers.