document: Mining distance-based outliers from large databases in any metric space Let R be a set of objects . An object o ∈ R is an outlier , if there exist less than k objects in R whose distances to o are at most r. The values of k , r , and the distance metric are provided by a user at the run time . The objective is to return all outliers with the smallest I\/O cost . This paper considers a generic version of the problem , where no information is available for outlier computation , except for objects ' mutual distances . We prove an upper bound for the memory consumption which permits the discovery of all outliers by scanning the dataset 3 times . The upper bound turns out to be extremely low in practice , e.g. , less than 1 % of R. Since the actual memory capacity of a realistic DBMS is typically larger , we develop a novel algorithm , which integrates our theoretical findings with carefully-designed heuristics that leverage the additional memory to improve I\/O efficiency . Our technique reports all outliers by scanning the dataset at most twice ( in some cases , even once ) , and significantly outperforms the existing solutions by a factor up to an order of magnitude .
doc_bio_tags: B O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O