91 citations · 178 across the 17 of their papers we have counts for
5 papers · 1 filter
Sketch-Flip-Merge: Mergeable Sketches for Private Distinct Counting
Jonathan Hehir, Daniel Ting, Graham Cormode
Data sketching is a critical tool for distinct counting, enabling multisets to be represented by compact summaries that admit fast cardinality estimates. Because sketches may be me…
Order-Invariant Cardinality Estimators Are Differentially Private
Charlie Dickens, Justin Thaler, Daniel Ting
We consider privacy in the context of streaming algorithms for cardinality estimation. We show that a large class of algorithms all satisfy -differential privacy, so long as (a)…
Simple, Optimal Algorithms for Random Sampling Without Replacement
Daniel Ting
Consider the fundamental problem of drawing a simple random sample of size k without replacement from [n] := {1, . . . , n}. Although a number of classical algorithms exist for thi…
Conditional Cuckoo Filters
Daniel Ting, Rick Cole
Bloom filters, cuckoo filters, and other approximate set membership sketches have a wide range of applications. Oftentimes, expensive operations can be skipped if an item is not in…
Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions
Daniel Ting
The Count-Min sketch is an important and well-studied data summarization method. It allows one to estimate the count of any item in a stream using a small, fixed size data sketch.…