106 citations · 156 across the 7 of their papers we have counts for
7 papers · 1 filter
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,…
Empirical Comparison of Algorithms for Network Community Detection
Jure Leskovec, Kevin J. Lang, Michael W. Mahoney
Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses…