Fetching the paper…
Reading the bibliography…
Given $m$ distributed data streams $A_1, \dots, A_m$, we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over $A_1, \dots, A_m$.
Algorithm 65: Find
C. A. R. Hoare · 1961
Earlier work this paper cites.
Counting large numbers of events in small registers
R. Morris · 1978
Earlier work this paper cites.
Approximate counting: a detailed analysis
P. Flajolet · 1985
Earlier work this paper cites.
Probabilistic counting algorithms for data base applications
P. Flajolet and G. Nigel Martin · 1985
Earlier work this paper cites.
On adaptive sampling
P. Flajolet · 1990
Earlier work this paper cites.
The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching
D. E. Knuth · 1998
Earlier work this paper cites.
The space complexity of approximating the frequency moments
N. Alon, Y. Matias, and M. Szegedy · 1999
Earlier work this paper cites.
Estimating simple functions on the union of data streams
P. B. Gibbons and S. Tirthapura · 2001
Earlier work this paper cites.
Counting distinct elements in a data stream
Z. Bar-Yossef, T. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan · 2002
Earlier work this paper cites.
Processing set expressions over continuous update streams
S. Ganguly, M. Garofalakis, and R. Rastogi · 2003
Earlier work this paper cites.
Data streams: Algorithms and applications
S. Muthukrishnan · 2005
Cited alongside, same era.
A simple and efficient estimation method for stream expression cardinalities
A. Chen, J. Cao, and T. Bu · 2007
Cited alongside, same era.
Summarizing data using bottom-k sketches
E. Cohen and H. Kaplan · 2007
Cited alongside, same era.
Priority sampling for estimation of arbitrary subset sums
N. G. Duffield, C. Lund, and M. Thorup · 2007
Cited alongside, same era.
Distinct-values estimation over data streams
P. B. Gibbons · 2007
Cited alongside, same era.
Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm
P. Flajolet, É. Fusy, O. Gandouet, and F. Meunier · 2008
Cited alongside, same era.
Applying approximate counting for computing the frequency moments of long data streams
A. Gronemeier and M. Sauerhoff · 2009
Later among the works it cites.
Backyard cuckoo hashing: Constant worst-case operations with a succinct representation
Y. Arbitman, M. Naor, and G. Segev · 2010
Later among the works it cites.
An optimal algorithm for the distinct elements problem
D. M. Kane, J. Nelson, and D. P. Woodruff · 2010
Later among the works it cites.
Sketch techniques for massive data
G. Cormode · 2011
Later among the works it cites.
A General Method for Estimating Correlated Aggregates over a Data Stream. In Proceedings of ICDE , pages 162-173, 2012
S. Tirthapura and D. P. Woodruff · 2012
Later among the works it cites.
Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
De-amortized cuckoo hashing: Provable worst-case performance and experimental results
Y. Arbitman, M. Naor, and G. Segev · 2009
Cited alongside, same era.
Distinct-value synopses for multiset operations
K. Beyer, R. Gemulla, P. J. Haas, B. Reinwald, and Y. Sismanis · 2009
Cited alongside, same era.
Leveraging discarded samples for tighter estimation of multiple-set aggregates
E. Cohen and H. Kaplan · 2009
Cited alongside, same era.
Order statistics and estimating cardinalities of massive data sets
F. Giroire · 2009
Cited alongside, same era.
S. Heule, M. Nunkesser, and A. Hall · 2013
Later among the works it cites.
Bottom-k and priority sampling, set similarity and subset sums with minimal independence
M. Thorup · 2013
Later among the works it cites.
All-distances sketches, revisited: HIP estimators for massive graphs analysis
E. Cohen · 2014
Later among the works it cites.
Streamed approximate counting of distinct elements: Beating optimal batch methods
D. Ting · 2014
Later among the works it cites.