106 citations · 156 across the 7 of their papers we have counts for
8 papers
Streaming Quantiles Algorithms with Small Space and Update Time
Nikita Ivkin, Edo Liberty, Kevin Lang +2
Approximating quantiles and distributions over streaming data has been studied for roughly two decades now. Recently, Karnin, Lang, and Liberty proposed the first asymptotically op…
Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm
Kevin J Lang
We describe a new cardinality estimation algorithm that is extremely space-efficient. It applies one of three novel estimators to the compressed state of the Flajolet-Martin-85 cou…
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…
Optimal Quantile Approximation in Streams
Zohar Karnin, Kevin Lang, Edo Liberty
This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An approximate…
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,…
Bargaining for Revenue Shares on Tree Trading Networks
Arpita Ghosh, Satyen Kale, Kevin Lang +1
We study trade networks with a tree structure, where a seller with a single indivisible good is connected to buyers, each with some value for the good, via a unique path of interme…