Modelling the Outlier Detection Problem in ASP(Q)

Knowledge discovery techniques had important impact in several relevant application domains. Among the most important knowledge discovery tasks is outlier detection. Outlier detection is the task of identifying anomalous individuals in a given population. This task is very demanding from the computational complexity point of view, being located in the second level of the polynomial hierarchy. Angiulli et al. in 2007 proposed to employ Answer Set Programming (ASP) to compute outliers. Their solution is based on the saturation technique and, as a consequence, it is very hard to evaluate by ASP systems. In this paper we resort to Answer Set Programming with Quantifiers (ASP(Q)) to provide a more declarative, compact and efficient modeling of the outlier detection problem. An experiment on syntetic benchmarks proves that our ASP(Q)-based solution can handle databases that are three order of magnitude larger than the ASP-based one proposed by Angiulli et al.