Private Queries with Sigma-Counting

• URL: http://arxiv.org/abs/2509.07018v1
• Date: Sun, 07 Sep 2025 01:46:24 GMT
• Title: Private Queries with Sigma-Counting
• Abstract summary: A popular approach to enhance data privacy is to return a noisy version of the actual count.<n>This work presents the design and analysis of a new method, sigma-counting, that addresses these challenges.
• Score: 8.17265021040487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Multi-tier Differential Private Query Release [57.049084914202275]
  Multiple analysts may issue the same query, while receiving answers generated under different privacy budgets.<n>Existing approaches for such multi-tier DP queries either incur excessive cumulative privacy loss or suffer from suboptimal utility.<n>We propose a framework for multi-tier DP query release that simultaneously bound the cumulative privacy loss by the maximum privacy budget among all queries.
  arXiv  Detail & Related papers  (2026-06-14T02:10:22Z)
• Count Anything at Any Granularity [55.70950689938894]
  KubriCount is the largest and most comprehensively annotated counting dataset to date.<n>We train a multi-grained counting model that jointly leverages text and visual exemplars as complementary target specifications.<n>HieraCount substantially improves multi-grained counting accuracy and generalizes robustly to challenging real-world scenarios.
  arXiv  Detail & Related papers  (2026-05-11T17:32:37Z)
• Answering Counting Queries with Differential Privacy on a Quantum Computer [0.7129650436893149]
  We show how to answer counting queries on a quantum encoded dataset with differential privacy.<n>We analyze the differential privacy properties of two algorithms to measure amplitude.
  arXiv  Detail & Related papers  (2026-04-13T00:57:33Z)
• Private-RAG: Answering Multiple Queries with LLMs while Keeping Your Data Private [21.980739918403344]
  Retrieval-augmented generation (RAG) enhances large language models (LLMs) by retrieving documents from an external corpus at inference time.<n>When this corpus contains sensitive information, unprotected RAG systems are at risk of leaking private information.<n>In this paper, we study the more practical multi-query setting and propose two DP-RAG algorithms.
  arXiv  Detail & Related papers  (2025-11-10T21:12:32Z)
• Improving Statistical Privacy by Subsampling [0.0]
  A privacy mechanism often used is to take samples of the data for answering a query.<n>This paper proves precise bounds how much different methods of sampling increase privacy in the statistical setting.<n>For the DP setting tradeoff functions have been proposed as a finer measure for privacy compared to (epsilon,delta)-pairs.
  arXiv  Detail & Related papers  (2025-04-15T17:40:45Z)
• Statistical Privacy [0.0]
  This paper considers a situation where an adversary knows the distribution by which the database is generated, but no exact data of its entries.<n>We analyze in detail how the entropy of the distribution guarantes privacy for a large class of queries called property queries.
  arXiv  Detail & Related papers  (2025-01-22T14:13:44Z)
• UQE: A Query Engine for Unstructured Databases [71.49289088592842]
  We investigate the potential of Large Language Models to enable unstructured data analytics. We propose a new Universal Query Engine (UQE) that directly interrogates and draws insights from unstructured data collections.
  arXiv  Detail & Related papers  (2024-06-23T06:58:55Z)
• Database-Augmented Query Representation for Information Retrieval [59.57065228857247]
  We present a novel retrieval framework called Database-Augmented Query representation (DAQu) DAQu augments the original query with various (query-related) metadata across multiple tables. We validate DAQu in diverse retrieval scenarios that can incorporate metadata from the relational database.
  arXiv  Detail & Related papers  (2024-06-23T05:02:21Z)
• Private Approximate Query over Horizontal Data Federation [0.0]
  Existing approaches rely on cryptography, which improves privacy, but at the expense of query response time. We propose a new approach that considers a data distribution-aware online sampling technique to accelerate the execution of range queries. Our solution is able of providing up to 8 times faster processing than the basic non-secure solution.
  arXiv  Detail & Related papers  (2024-06-17T11:19:58Z)
• Active Sampling of Multiple Sources for Sequential Estimation [92.37271004438406]
  The objective is to design an active sampling algorithm for sequentially estimating parameters in order to form reliable estimates. This paper adopts emph conditional estimation cost functions, leading to a sequential estimation approach that was recently shown to render tractable analysis.
  arXiv  Detail & Related papers  (2022-08-10T15:58:05Z)
• Text Summarization with Latent Queries [60.468323530248945]
  We introduce LaQSum, the first unified text summarization system that learns Latent Queries from documents for abstractive summarization with any existing query forms. Under a deep generative framework, our system jointly optimize a latent query model and a conditional language model, allowing users to plug-and-play queries of any type at test time. Our system robustly outperforms strong comparison systems across summarization benchmarks with different query types, document settings, and target domains.
  arXiv  Detail & Related papers  (2021-05-31T21:14:58Z)
• Approximate Query Processing for Group-By Queries based on Conditional Generative Models [3.9837198605506963]
  Group-by query involves multiple values, which makes it difficult to provide sufficiently accurate estimations for all the groups. Stratified sampling improves the accuracy compared with the uniform sampling, but the samples chosen for some special queries cannot work for other queries. Online sampling chooses samples for the given query at query time, but it requires a long latency. The proposed framework can be combined with stratified sampling and online aggregation to improve the estimation accuracy for group-by queries.
  arXiv  Detail & Related papers  (2021-01-08T08:49:21Z)
• Session-Aware Query Auto-completion using Extreme Multi-label Ranking [61.753713147852125]
  We take the novel approach of modeling session-aware query auto-completion as an e Multi-Xtreme Ranking (XMR) problem. We adapt a popular XMR algorithm for this purpose by proposing several modifications to the key steps in the algorithm. Our approach meets the stringent latency requirements for auto-complete systems while leveraging session information in making suggestions.
  arXiv  Detail & Related papers  (2020-12-09T17:56:22Z)
• The Sparse Vector Technique, Revisited [67.57692396665915]
  We revisit one of the most basic and widely applicable techniques in the literature of differential privacy. This simple algorithm privately tests whether the value of a given query on a database is close to what we expect it to be. We suggest an alternative, equally simple, algorithm that can continue testing queries as long as any single individual does not contribute to the answer of too many queries.
  arXiv  Detail & Related papers  (2020-10-02T10:50:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.