Data Streams as Random Permutations: the Distinct Element Problem

Data Streams as Random Permutations: the Distinct Element Problem

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 thi...

Full description

Bibliographic Details
Main Authors: Ahmed Helmi, Jérémie Lumbroso, Conrado Martínez, Alfredo Viola
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2012-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
probabilistic algorithm
random permutation
random-order model.
data stream
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
[info.info-cg] computer science [cs]/computational geometry [cs.cg]
Online Access:https://dmtcs.episciences.org/3002/pdf

Internet

https://dmtcs.episciences.org/3002/pdf

Similar Items