M. Ajtai, T. S. Jayram, R. Kumar, and D. Sivakumar, Approximate counting of inversions in a data stream, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , STOC '02, pp.370-379, 2002.
DOI : 10.1145/509907.509964

M. Archibald and C. Martínez, The hiring problem and permutations, Proceedings of the Twenty- First International Conference on Formal Power Series and Algebraic Combinatorics, Discrete Mathematics & Theoretical Computer Science Proceedings, pp.63-76, 2009.
URL : https://hal.archives-ouvertes.fr/hal-01185423

Z. Bar-yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan, Counting Distinct Elements in a Data Stream, Randomization and Approximation Techniques (RANDOM), pp.1-10, 2002.
DOI : 10.1007/3-540-45726-7_1

A. Z. Broder, A. Kirsch, R. Kumar, M. Mitzenmacher, E. Upfal et al., The Hiring Problem and Lake Wobegon Strategies, Proceedings of the Nineteenth ACM-SIAM Symposium On Discrete Algorithms, pp.1184-1193, 2008.
DOI : 10.1137/07070629X

A. Chakrabarti, G. Cormode, and A. Mcgregor, Robust lower bounds for communication and stream computation, Proceedings of the fourtieth annual ACM symposium on Theory of computing, STOC 08, pp.641-650, 2008.
DOI : 10.1145/1374376.1374470

M. Durand, Combinatoire analytique et algorithmique des ensembles de données, 2004.

M. Durand and P. Flajolet, Loglog Counting of Large Cardinalities, Proceedings of the Eleventh European Symposium on Algorithms, pp.605-617, 2003.
DOI : 10.1007/978-3-540-39658-1_55

F. Ergun and H. Jowhari, On distance to monotonicity and longest increasing subsequence of a data stream, Proceedings of the Nineteenth ACM-SIAM Symposium On Discrete Algorithms, pp.730-736, 2008.

P. Flajolet, Adaptives Abtasten, Computing, vol.14, issue.4, pp.391-400, 1990.
DOI : 10.1007/BF02241657

P. Flajolet, Adaptive sampling Encyclopaedia of Mathematics, volume Supplement I, page 28, 1997.

P. Flajolet, Counting by Coin Tossings, Proceedings of the Ninth Asian Computing Science Conference, pp.1-12, 2004.
DOI : 10.1007/978-3-540-30502-6_1
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.1577

P. Flajolet, E. Fusy, O. Gandouet, and F. Meunier, HyperLoglog: the analysis of a nearoptimal cardinality estimation algorithm, Proceedings of Analysis of Algorithms, pp.127-146, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00406166

P. Flajolet, G. N. Nigel, and . Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, vol.31, issue.2, pp.182-209, 1985.
DOI : 10.1016/0022-0000(85)90041-8
URL : https://hal.archives-ouvertes.fr/inria-00076244

R. Peter and . Freeman, The secretary problem and its extensions: A review, International Statistical, vol.51, issue.2, pp.189-206, 1983.

P. B. Gibbons, Distinct sampling for highly-accurate answers to distinct values queries and event reports, Proceedings of the International Conference on Very Large Data Bases, pp.541-550, 2001.

P. Gopalan, T. S. Jayram, R. Krauthgamer, and R. Kumar, Estimating the sortedness of a data stream, Proceedings of the Eighteenth ACM-SIAM Symposium On Discrete Algorithms, pp.318-327, 2007.

A. Helmi, C. Martínez, and A. Panholzer, Hiring above the m-th Best Candidate: A Generalization of Records in Permutations, Proceedings of LATIN 2012, 2012.
DOI : 10.1007/978-3-642-29344-3_40

G. Louchard, Probabilistic analysis of adaptive sampling. Random Structures & Algorithms, pp.157-168, 1997.

J. Lumbroso, A full analysis of distinct sampling, and applications, Preprint, 2012.

J. Lumbroso, An optimal cardinality estimation algorithm based on order statistics and its full analysis, Proceedings of the Twenty-First International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms, pp.489-504, 2010.
URL : https://hal.archives-ouvertes.fr/hal-01185578

A. Mcgregor, Processing Data Streams, 2007.

M. Mitzenmacher and S. Vadhan, Why simple hash functions work: Exploiting the entropy in a data stream, Proceedings of the Nineteenth ACM-SIAM Symposium On Discrete Algorithms, pp.746-755, 2008.

M. Monemizadeh and D. P. Woodruff, One-pass relative-error Lp-sampling with applications, Proceedings of the Twenty-First ACM-SIAM Symposium on Discrete Algorithms, pp.1143-1160, 2010.

J. , I. Munro, and M. S. Paterson, Selection and sorting with limited storage, Theoretical Computer Science, vol.12, issue.3, pp.315-323, 1980.
DOI : 10.1109/sfcs.1978.32
URL : http://dx.doi.org/10.1016/0304-3975(80)90061-4

S. and M. Muthukrishnan, Data Streams: Algorithms and Applications, Foundations and Trends?? in Theoretical Computer Science, vol.1, issue.2, pp.117-236, 2005.
DOI : 10.1561/0400000002
URL : http://ce.sharif.edu/courses/90-91/1/ce797-1/resources/root/Data_Streams_-_Algorithms_and_Applications.pdf

K. Whang, T. Bradley, H. M. Vander-zanden, and . Taylor, A linear-time probabilistic counting algorithm for database applications, ACM Transactions on Database Systems, vol.15, issue.2, pp.208-229, 1990.
DOI : 10.1145/78922.78925

D. Woodruff, Distinct elements is hard even for random data streams, 2008.