Affirmative Sampling: Theory and Applications

Jérémie Lumbroso, Conrado Martínez

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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 “diversity” (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.

Original languageEnglish (US)
Title of host publication33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2022
EditorsMark Daniel Ward
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772303
DOIs
StatePublished - Jun 1 2022
Event33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2022 - Philadelphia, United States
Duration: Jun 20 2022Jun 24 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume225
ISSN (Print)1868-8969

Conference

Conference33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2022
Country/TerritoryUnited States
CityPhiladelphia
Period6/20/226/24/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Analysis of algorithms
  • Cardinality estimation
  • Data streams
  • Distinct sampling
  • Random sampling

Fingerprint

Dive into the research topics of 'Affirmative Sampling: Theory and Applications'. Together they form a unique fingerprint.

Cite this