# Private Queries with Sigma-Counting

arXiv: https://arxiv.org/abs/2509.07018 · HTML: https://mlsanity.com/paper/2509.07018/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 7 Sep 2025.

## Builds on (most cited first, 6 of 6)

- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [New Oracle-Efficient Algorithms for Private Synthetic Data Release](https://mlsanity.com/paper/2007.05453/) (2020)
- [Private Post-GAN Boosting](https://mlsanity.com/paper/2007.11934/) (2020)
- [Towards Practical Differential Privacy for SQL Queries](https://mlsanity.com/paper/1706.09479/) (2017)
- [Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy](https://mlsanity.com/paper/1502.07526/) (2015)
- [Collaboratively Learning Preferences from Ordinal Data](https://mlsanity.com/paper/1506.07947/) (2015)

## Abstract (arXiv)

Many data applications involve counting queries, where a client specifies a feasible range of variables and a database returns the corresponding item counts. A program that produces the counts of different queries often risks leaking sensitive individual-level information. A popular approach to enhance data privacy is to return a noisy version of the actual count. It is typically achieved by adding independent noise to each query and then control the total privacy budget within a period. This approach may be limited in the number of queries and output accuracy in practice. Also, the returned counts do not maintain the total order for nested queries, an important feature in many applications. This work presents the design and analysis of a new method, sigma-counting, that addresses these challenges. Sigma-counting uses the notion of sigma-algebra to construct privacy-preserving counting queries. We show that the proposed concepts and methods can significantly improve output accuracy while maintaining a desired privacy level in the presence of massive queries to the same data. We also discuss how the technique can be applied to address large and time-varying datasets.