53 citations · 247 across the 33 of their papers we have counts for
18 papers · 1 filter
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)…
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud…
Relative Error Streaming Quantiles
Graham Cormode, Zohar Karnin, Edo Liberty +2
Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of items from a data universe equipped with…
A High-Performance Algorithm for Identifying Frequent Items in Data Streams
Daniel Anderson, Pryce Bevan, Kevin Lang +3
Estimating frequencies of items over data streams is a common building block in streaming data measurement and analysis. Misra and Gries introduced their seminal algorithm for the…
Determining Tournament Payout Structures for Daily Fantasy Sports
Christopher Musco, Maxim Sviridenko, Justin Thaler
With an exploding global market and the recent introduction of online cash prize tournaments, fantasy sports contests are quickly becoming a central part of the social gaming and s…
A Framework for Estimating Stream Expression Cardinalities
Anirban Dasgupta, Kevin Lang, Lee Rhodes +1
Given distributed data streams , we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over $A_1, \dots,…