PRISM: Prefix-Sum based Range Queries Processing Method under Local Differential Privacy

Range query over data cubes is a powerful tool for online analytical processing (OLAP). In this paper, we focus on answering range queries while satisfying local differential privacy (LDP). The key technical challenges come from the problem of noise aggregation and the curse of high dimensionality: multiple LDP noise will be aggregated when answering range queries and collecting high-dimensional data under LDP will further degrade the utility of the results. To this end, we present a novel method called Prefix-Sum based Range QuerIes ProceSsing Method (PRISM). Its main idea is to selectively collect a few prefix-sums in a data-dependent way, and answer range queries over prefix-sum-based cubes based on which any range query can be processed by using constant pieces of prefix-sums. In PRISM, we first alleviate the problem of noise aggregation by proposing a LDP mechanism called Range based Randomized Response (RRR) and a new type of prefix-sums-based cube called Grained Prefix-Sum (GPS) cube. We then alleviate the curse of high dimensionality by proposing a Data-Dependent Selective Prefix-Sum Collection Strategy (DELFT). We conduct experiments on both real-world datasets and synthetic datasets. Experimental results confirm the effectiveness of PRISM over existing methods.