A theoretical and empirical study of affirmative sampling

Autor:	Montes Sanabria, Jordi
Přispěvatelé:	Martínez Parra, Conrado, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Jazyk:	angličtina
Rok vydání:	2020
Předmět:	68 Computer science::68W Algorithms [Classificació AMS] Cardinality estimation Affirmative sampling Matemàtiques i estadística [Àrees temàtiques de la UPC] Algorismes Random sampling Algorithms Distinct sampling
Zdroj:	UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC)
Popis:	Distinct random sampling is widely used in many applications due to its ability to answer aggregate queries on data with provable probabilistic guarantees on the quality of the answer. We consider the data stream model where a single pass over the data is allowed and only a small number of elements in the stream can be stored. We analyze Affirmative Sampling, an algorithm for distinct random sampling with adaptive sample size. We discuss an unbiased cardinality estimator of the stream using the elements in the random sample from Affirmative sampling and provide bounds for its accuracy. Random samples can be used for much more than just cardinality estimation. We introduce Nooh, a fast genome distance estimation tool that uses Affirmative sampling to compete with the current state-of-the-art tools in bioinformatics.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::7b8d2804fedb8739626f961f4fa95638 http://hdl.handle.net/2117/328097 Zobrazit plný text záznamu