Authentication of uncertain data based on k-means clustering

Abstract

Probabilistic databases and database outsourcing are two recent and important applications of database systems. In this paper, we introduce authenticated query processing in outsourced probabilistic databases. We have proposed a novel authenticated data structure (ADS) called PH-tree, which is a combination of PDR-tree and MH-tree. We have also implemented k-means clustering as a preprocessor. We have compared our algorithm with an existing ADS called MR-tree and showed that PH-trees outperform MR-trees significantly.