COP: Privacy-Preserving Multidimensional Partition in DAS Paradigm
Authors
- Jieping Wang, School of Information, Renmin University (China)
- Xiaoyong Du, School of Information, Renmin University (China)
- Haocong Wang, School of Information, Renmin University (China)
- Pingping Yang, School of Information, Renmin University (China)
Abstract
Database-as-a-Service (DAS) is an emerging database management paradigm wherein partition based index is an effective way to querying encrypted data. However, previous research either focuses on one-dimensional partition or ignores multidimensional data distribution characteristic, especially sparsity and locality. In this paper, we propose Cluster based Onion Partition (COP), which is designed to decrease both false positive and dead space at the same time. Basically, COP is composed of two steps. First, it partition covered space level by level, which is like peeling of onion; second, at each level, a clustering algorithm based on local density is proposed to achieve local optimal secure partition. Extensive experiments on real dataset and synthetic dataset show that COP is a secure multidimensional partition with much less efficiency loss than previous top down or bottom up counterparts.