DOAJ Open Access 2012

Data Streams as Random Permutations: the Distinct Element Problem

Ahmed Helmi Jérémie Lumbroso Conrado Martínez Alfredo Viola

Lihat Sumber DOI

Abstrak

In this paper, we show that data streams can sometimes usefully be studied as random permutations. This simple observation allows a wealth of classical and recent results from combinatorics to be recycled, with minimal effort, as estimators for various statistics over data streams. We illustrate this by introducing RECORDINALITY, an algorithm which estimates the number of distinct elements in a stream by counting the number of $k$-records occurring in it. The algorithm has a score of interesting properties, such as providing a random sample of the set underlying the stream. To the best of our knowledge, a modified version of RECORDINALITY is the first cardinality estimation algorithm which, in the random-order model, uses neither sampling nor hashing.

Topik & Kata Kunci

Mathematics

Penulis (4)

Ahmed Helmi

Jérémie Lumbroso

Conrado Martínez

Alfredo Viola

Format Sitasi

APA MLA BibTeX

Helmi, A., Lumbroso, J., Martínez, C., Viola, A. (2012). Data Streams as Random Permutations: the Distinct Element Problem. https://doi.org/10.46298/dmtcs.3002

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.3002

Informasi Jurnal

Tahun Terbit: 2012
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.3002
Akses: Open Access ✓