Privately Counting Partially Ordered Data

Matthew Joseph, M'onica Ribero, Alexander Yu
10/1/2024

No confident code implementation found for this paper.

Abstract

We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d^2)$. Experiments show that, depending on the partial order in question, our solution dominates existing pure differentially private mechanisms, and can reduce their error by an order of magnitude or more.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

82% match2026

A Unifying Framework for Differentially Private Sums under Continual Observation

80% match2023

Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model

80% match2025

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy

80% match2024

A Smooth Binary Mechanism for Efficient Private Continual Observation

79% match1 repo32023

Faster Privacy Accounting via Evolving Discretization

79% match2022

Cite this paper

@article{joseph2024privately,
  title  = {Privately Counting Partially Ordered Data},
  author = {Matthew Joseph and M'onica Ribero and Alexander Yu},
  year   = {2024},
  eprint = {2410.06881},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2410.06881},
  journal = {ICLR 2024 2024}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2410.06881.svg)](https://codeofpaper.com/paper/2410.06881)

Discussion