Index Optimization for L-Diversified Database-as-a-Service

Preserving the anonymity of individuals by technical means when outsourcing databases to semi-trusted providers gained importance in recent years. Anonymization approaches exist that fulfill anonymity notions like l-diversity and can be used to outsource databases. However, using indexes on anonymized data to increase query execution performance significantly differs from using plaintext indexes and it is not clear whether using an anonymized index is beneficial or not. In this paper, we present Dividat, an approach that makes anonymized database outsourcing more practical and deployable by optimizing the indexing of -diversified data. We show that the efficiency of anonymized indexes differs from traditional indexes and performance gains of a factor of 5 are possible by optimizing indexing strategies. We propose strategies to determine which indexes should be created for a given query workload and used for a given query. To apply these strategies without actually creating each possible index, we propose and validate models that estimate the performance of anonymized index tables a-priori.