EDOLOIS: Efficient discovery of local outliers in subspaces

For many KDD applications, such as data cleaning, detecting criminal activities in E-commerce, finding the outlier can be more meaningful and interesting than finding the common cases. In the paper, we present a novel and efficient subspace local outlier test algorithm: EDOLOIS, so as to avoid the computation-intensive distance computation. The algorithm takes full use of the character of subspace data processing and the initial LOF itself, thus it can not only reduce the computation dramatically, but also gain the precise LOF of all objects in the subspaces. Both formal analysis and comprehensive performance evaluation show that the method is efficient to find all local outliers from high-dimensional categorical datasets in all subspaces.