Geodesic
The Adaptive sampling revisited
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3.

Voir la notice de l'article provenant de la source Episciences

The problem of estimating the number n of distinct keys of a large collection of N data is well known in computer science. A classical algorithm is the adaptive sampling (AS). n can be estimated by R2 J , where R is the final bucket size and J is the final depth at the end of the process. Several new interesting questions can be asked about AS (some of them were suggested by P.Flajolet and popularized by J.Lumbroso). The distribution of W = log(R2 J /n) is known, we rederive this distribution in a simpler way. We provide new results on the moments of J and W. We also analyze the final cache size R distribution. We consider colored keys: assume also that among the n distinct keys, m do have color K We show how to estimate p = m n. We study keys with some multiplicity : we provide a way to estimate the total number M of some color K keys among the total number N of keys. We consider the case where we know a priori the multiplicities but not the colors. There we want to estimate the total number of keys N. An appendix is devoted to the case where the hashing function provides bits with probability different from 1/2. 
@article{DMTCS_2019_21_3_a21,
     author = {Drescher, Matthew and Louchard, Guy and Swan, Yvik},
     title = {The {Adaptive} sampling revisited},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2019},
     doi = {10.23638/DMTCS-21-3-13},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-13/}
}
TY  - JOUR
AU  - Drescher, Matthew
AU  - Louchard, Guy
AU  - Swan, Yvik
TI  - The Adaptive sampling revisited
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-13/
DO  - 10.23638/DMTCS-21-3-13
LA  - en
ID  - DMTCS_2019_21_3_a21
ER  - 
%0 Journal Article
%A Drescher, Matthew
%A Louchard, Guy
%A Swan, Yvik
%T The Adaptive sampling revisited
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-13/
%R 10.23638/DMTCS-21-3-13
%G en
%F DMTCS_2019_21_3_a21
Drescher, Matthew; Louchard, Guy; Swan, Yvik. The Adaptive sampling revisited. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3. doi : 10.23638/DMTCS-21-3-13. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-13/

Cité par Sources :