Private Counting of Distinct and k-Occurring Items in Time Windows
summary
Paper gives private algorithms for counting distinct and k-occurring items over time windows by reducing these queries to differentially private range queries and using the binary tree mechanism. Event-level results: cumulative error O(log^{1.5} T), fixed-window error O(k·log^{1.5} W) with lower bound Ω(√k), time-window error O(k·log^3 T) with lower bound Ω(√k+log T). Item-level becomes harder: fixed-window upper bound ≈ k·T/W and lower bound Ω(T/W+√k), and time-window bounds are Θ(T).
AI-written summary · about
chapters (10)
- 0:00Count Distinct in Time Windows
- 1:51k-Occurring Elements in Time Windows
- 3:25Differential Privacy
- 4:30Three Families of Queries
- 6:23Two Neighboring Notions
- 8:20Results: k-Occurring Items
- 11:33Results: Count Distinct
- 12:44Range Query
- 20:28Fixed-Window Count Distinct
- 24:45Conclusion
related talks
27mOn Distributed Differential Privacy and Counting Distinct Elements
01h 00mDifferential Privacy And The Complexity Of Simple Queries
26mLocally Private Histograms in All Privacy Regimes
44mBandit Learning under Differential Privacy
40mApplied Privacy Engineering Study
27mMetadata-private data transfer
31mPractical Private DB Querying
47mDifferentially Private Change-Point Detection