Quality assurance of outsourced outlier mining

Spurred by developments such as in cloud computing, there has been considerable recent interest in the paradigm of data mining-as-service. A company (data owner) lacking in expertise or computational resources can outsource its mining needs to a third-party service provider. However, as the service providers may not be fully trusted, a dishonest service provider may return inaccurate mining results to the database owner. In this paper, we study the problem of providing quality assurance for outsourced outlier mining. We propose an efficient and practical auditing approach that can verify (1) whether the service provider returns the outliers originated from the hosted database, and (2) whether the service provider returns correct and complete outlier mining results. The key of our approach is to insert a small amount of artificial tuples into the outsourced database; the mining results of the service provider will be audited by analyzing the inserted tuples in the returned results with probabilistic guarantee. Our empirical results demonstrate the effectiveness and efficiency of our method.