Cluster Based Partition for Multi-dimensional Range Query in DAS Model

Database-as-a-service (DAS) is an emerging database management paradigm wherein querying on encrypted data directly is a performance critical problem, to which partition based index is an effective solution. For multi-dimensional range query, generating partition on each dimension would increase information leakage to a large extent, while previous multi-dimensional partition would cause large efficiency loss, especially when the data distribution is sparse. To achieve guaranteed security with much less efficiency loss, in this paper we propose cluster based multi-dimensional partition (CBMP). First, CBMP decompose the whole space into clusters, which only cover non-empty area. To get better clustering effect, a new cluster criteria based on full neighbor is proposed. Second, since optimal secure partition is NP-hard, several heuristic based algorithms including distance based and Hilbert based are proposed. Experiments on real dataset and synthetic dataset show that distance based algorithm could achieve approximately least efficiency loss.