Authenticated Outlier Mining for Outsourced Databases

Boxiang Dong, Hui Wang, Anna Monreale, Dino Pedreschi, Fosca Giannotti, Wenge Guo

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


The Data-Mining-as-a-Service (DMaS) paradigm is becoming the focus of research, as it allows the data owner (client) who lacks expertise and/or computational resources to outsource their data and mining needs to a third-party service provider (server). Outsourcing, however, raises some issues about result integrity: how could the client verify the mining results returned by the server are both sound and complete? In this paper, we focus on outlier mining, an important mining task. Previous verification techniques use an authenticated data structure (ADS) for correctness authentication, which may incur much space and communication cost. In this paper, we propose a novel solution that returns a probabilistic result integrity guarantee with much cheaper verification cost. The key idea is to insert a set of artificial records (ARs) into the dataset, from which it constructs a set of artificial outliers (AOs) and artificial non-outliers (ANOs). The AOs and ANOs are used by the client to detect any incomplete and/or incorrect mining results with a probabilistic guarantee. The main challenge that we address is how to construct ARs so that they do not change the (non-)outlierness of original records, while guaranteeing that the client can identify ANOs and AOs without executing mining. Furthermore, we build a strategic game and show that a Nash equilibrium exists only when the server returns correct outliers. Our implementation and experiments demonstrate that our verification solution is efficient and lightweight.

Original languageEnglish (US)
Article number8048342
Pages (from-to)222-235
Number of pages14
JournalIEEE Transactions on Dependable and Secure Computing
Issue number2
StatePublished - Mar 1 2020

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


  • Authentication
  • game theory
  • outlier mining
  • outsourcing
  • probabilistic guarantees


Dive into the research topics of 'Authenticated Outlier Mining for Outsourced Databases'. Together they form a unique fingerprint.

Cite this