@article{alon1999,
    title = {The Space Complexity of Approximating the Frequency Moments},
    journal = {Journal of Computer and System Sciences},
    volume = {58},
    number = {1},
    pages = {137-147},
    year = {1999},
    issn = {0022-0000},
    _doi = {https://doi.org/10.1006/jcss.1997.1545},
    _url = {https://www.sciencedirect.com/science/article/pii/S0022000097915452},
    author = {Noga Alon and Yossi Matias and Mario Szegedy},
}

@InProceedings{baryossef2002,
    author="Bar-Yossef, Ziv
    and Jayram, T. S.
    and Kumar, Ravi
    and Sivakumar, D.
    and Trevisan, Luca",
    _editor="Rolim, Jos{\'e} D. P.
    and Vadhan, Salil",
    title="Counting Distinct Elements in a Data Stream",
    booktitle="Randomization and Approximation Techniques in Computer Science",
    year="2002",
    publisher="Springer Berlin Heidelberg",
    _address="Berlin, Heidelberg",
    pages="1--10",
}

@inproceedings{kane2010,
    author = {Kane, Daniel M. and Nelson, Jelani and Woodruff, David P.},
    title = {An Optimal Algorithm for the Distinct Elements Problem},
    year = {2010},
    isbn = {9781450300339},
    _publisher = {Association for Computing Machinery},
    address = {New York},
    _url = {https://doi.org/10.1145/1807085.1807094},
    _doi = {10.1145/1807085.1807094},
    abstract = {We give the first optimal algorithm for estimating the number of distinct elements in a data stream, closing a long line of theoretical research on this problem begun by Flajolet and Martin in their seminal paper in FOCS 1983. This problem has applications to query optimization, Internet routing, network topology, and data mining. For a stream of indices in {1,...,n}, our algorithm computes a (1 \<plusminus> \<epsilon>)-approximation using an optimal O(1/\<epsilon>-2 + log(n)) bits of space with 2/3 success probability, where 0&lt;\<epsilon>&lt;1 is given. This probability can be amplified by independent repetition. Furthermore, our algorithm processes each stream update in O(1) worst-case time, and can report an estimate at any point midstream in O(1) worst-case time, thus settling both the space and time complexities simultaneously.We also give an algorithm to estimate the Hamming norm of a stream, a generalization of the number of distinct elements, which is useful in data cleaning, packet tracing, and database auditing. Our algorithm uses nearly optimal space, and has optimal O(1) update and reporting times.},
    booktitle = {Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems},
    pages = {41--52},
    numpages = {12},
    keywords = {streaming, query optimization, distinct elements, data mining},
    location = {Indianapolis, Indiana, USA},
    series = {PODS '10}
}
