Geodesic
Order statistics and estimating cardinalities of massive data sets
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

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

We introduce a new class of algorithms to estimate the cardinality of very large multisets using constant memory and doing only one pass on the data. It is based on order statistics rather that on bit patterns in binary representations of numbers. We analyse three families of estimators. They attain a standard error of $\frac{1}{\sqrt{M}}$ using $M$ units of storage, which places them in the same class as the best known algorithms so far. They have a very simple internal loop, which gives them an advantage in term of processing speed. The algorithms are validated on internet traffic traces. 
@article{DMTCS_2005_special_249_a1,
     author = {Giroire, Fr\'ed\'eric},
     title = {Order statistics and estimating cardinalities of massive data sets},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3353},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3353/}
}
TY  - JOUR
AU  - Giroire, Frédéric
TI  - Order statistics and estimating cardinalities of massive data sets
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3353/
DO  - 10.46298/dmtcs.3353
LA  - en
ID  - DMTCS_2005_special_249_a1
ER  - 
%0 Journal Article
%A Giroire, Frédéric
%T Order statistics and estimating cardinalities of massive data sets
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3353/
%R 10.46298/dmtcs.3353
%G en
%F DMTCS_2005_special_249_a1
Giroire, Frédéric. Order statistics and estimating cardinalities of massive data sets. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3353. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3353/

Cité par Sources :