PRIMA: Privacy preserving Multi-dimensional Analytic Approach

Sum query is an important and fundamental operator for online analytical processing. In this paper, we focus on the process of answering sum queries over data cube, each of which consists of a collection of cuboids, while satisfying differential privacy (DP). Existing works fail to process the sum queries in online analytical processing with high utility due to sum queries' high sensitivity and the noise aggregation: constructing a base cuboid requires the data curator to answer a workload of linear sum queries under DP in advance, whose sensitivity will result in a large amount of DP noise, and the noise will finally be aggregated when constructing the remaining cuboids. To this end, we present a Differentially PRIvate Multi-dimensional Analytic Approach (PRIMA). In PRIMA, we propose a Symmetric Bounded Sum Query Processing Method (SBS) which reduces the sensitivity of sum queries by bounding both the maximum and minimum contribution of each record in the data table in a symmetricaly manner. Moreover, we propose a Hypothesis Testing based Prefix Sum Computing Method (SCOPE) to compute a base prefix-sum cuboid based on hypothesis testing. By employing the base prefix-sum cuboid, any remaining cuboid can be constructed with constant pieces of DP noise aggregated. We conduct experiments on both real-world and synthetic datasets. Experimental results confirm the effectiveness of PRIMA over existing works.

• Publication year

  2025

• Venue

  International Conference on Information and Knowledge Management

• Publication date

  2025-11-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3746252.3761310
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys

  2023cited by this paper
• Releasing Private Data for Numerical Queries

  2022cited by this paper
• Algorithms for bounding contribution for histogram estimation under user-level privacy

  2022cited by this paper
• R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys

  2022cited by this paper
• Instance-optimal Mean Estimation Under Differential Privacy

  2021cited by this paper
• The power of factorization mechanisms in local and central differential privacy

  2019cited by this paper
• PrivateSQL: A Differentially Private SQL Query Engine

  2019cited by this paper
• Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation

  2019cited by this paper
• Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy

  2019cited by this paper
• Differentially Private SQL with Bounded User Contribution

  2019cited by this paper
• Optimizing error of high-dimensional statistical queries under differential privacy

  2018cited by this paper
• EKTELO: A Framework for Defining Differentially-Private Computations

  2018cited by this paper
• APEx: Accuracy-Aware Differentially Private Data Exploration

  2017cited by this paper
• Towards Practical Differential Privacy for SQL Queries

  2017cited by this paper
• Utility Cost of Formal Privacy for Releasing National Employer-Employee Statistics

  2017cited by this paper
• Prochlo: Strong Privacy for Analytics in the Crowd

  2017cited by this paper
• Convex Optimization for Linear Query Processing under Approximate Differential Privacy

  2016cited by this paper
• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy

  2015cited by this paper
• The matrix mechanism: optimizing linear counting queries under differential privacy

  2015influential reference
• RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response

  2014cited by this paper
• Understanding Hierarchical Methods for Differentially Private Histograms

  2013cited by this paper
• Local Privacy and Statistical Minimax Rates

  2013cited by this paper
• Calibrating Data to Sensitivity in Private Data Analysis

  2012cited by this paper
• Differentially private data cubes: optimizing noise sources and consistency

  2011cited by this paper
• A Simple and Practical Algorithm for Differentially Private Data Release

  2010cited by this paper
• Differentially private aggregation of distributed time-series with transformation and encryption

  2010cited by this paper
• X. On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling

  2009cited by this paper
• Differential privacy and robust statistics

  2009cited by this paper
• Optimizing linear counting queries under differential privacy

  2009cited by this paper
• Differential privacy via wavelet transforms

  2009cited by this paper
• Boosting the accuracy of differentially private histograms through consistency

  2009cited by this paper
• Privacy integrated queries: an extensible platform for privacy-preserving data analysis

  2009cited by this paper
• Privacy: Theory meets Practice on the Map

  2008cited by this paper
• Smooth sensitivity and sampling in private data analysis

  2007cited by this paper
• Calibrating Noise to Sensitivity in Private Data Analysis

  2006cited by this paper
• The IPUMS Project: An Update

  1999cited by this paper
• Range queries in OLAP data cubes

  1997cited by this paper
• Asymptotic Theory of Certain "Goodness of Fit" Criteria Based on Stochastic Processes

  1952cited by this paper

• No citing papers are available for this paper.