Authentication of uncertain data based on K-means clustering

Abstract

Probabilistic databases are beginning to expand in the database literature because of the upcoming challenges of uncertainty. It is a very new topic for the community and there are still some open problems for the researchers. Outsourcing probabilistic databases has never been worked before since there are no commercial probabilistic database management systems yet. The aim of this research is to introduce authenticated query processing in outsourced probabilistic databases. In order to proceed with the authentication, indexing methods should be analyzed rst. We have surveyed the existing structures for this purpose and decided to use pdr-Tree as the indexing method, because it works very e ciently on probabilistic databases and ts really well with the authentication techniques. We have proposed a novel authenticated data structure (ADS) called PH-Tree, which is an hybrid model of pdr-Tree and MH-Tree. Straightforward approach is not competent for hybridization and produce very poor results. By this reason, we have also implemented k-means clustering as a preprocessor. We have compared our algorithm with an existing ADS called MR-Tree and proved that PH-Trees outperform MR-Trees signi cantly.