@inproceedings{4098f36a93fd4b569b2f30b05ad3e695,
title = "Affirmative Sampling: Theory and Applications",
abstract = "Affirmative Sampling is a practical and efficient novel algorithm to obtain random samples of distinct elements from a data stream. Its most salient feature is that the size S of the sample will, on expectation, grow with the (unknown) number n of distinct elements in the data stream. As any distinct element has the same probability to be sampled, and the sample size is greater when the {\textquotedblleft}diversity{\textquotedblright} (the number of distinct elements) is greater, the samples that Affirmative Sampling delivers are more representative than those produced by any scheme where the sample size is fixed a priori - hence its name. Our algorithm is straightforward to implement, and several implementations already exist.",
keywords = "Analysis of algorithms, Cardinality estimation, Data streams, Distinct sampling, Random sampling",
author = "J{\'e}r{\'e}mie Lumbroso and Conrado Mart{\'i}nez",
note = "Publisher Copyright: {\textcopyright} J{\'e}r{\'e}mie Lumbroso and Conrado Mart{\'i}nez; licensed under Creative Commons License CC-BY 4.0; 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2022 ; Conference date: 20-06-2022 Through 24-06-2022",
year = "2022",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.AofA.2022.12",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Ward, \{Mark Daniel\}",
booktitle = "33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2022",
address = "Germany",
}