Ahmed Helmi ; Jérémie Lumbroso ; Conrado Martínez ; Alfredo Viola - Data Streams as Random Permutations: the Distinct Element Problem

dmtcs:3002 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.3002
Data Streams as Random Permutations: the Distinct Element Problem

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

    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.


    Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
    Section: Proceedings
    Published on: January 1, 2012
    Imported on: January 31, 2017
    Keywords: 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]

    Linked data

    Source : ScholeXplorer IsCitedBy DOI 10.13140/rg.2.2.23700.37761
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.aofa.2022.12
    • 10.13140/rg.2.2.23700.37761
    • 10.4230/lipics.aofa.2022.12
    Affirmative Sampling: Theory and Applications
    Lumbroso, Jérémie ; Martínez, Conrado ;

    2 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 184 times.
    This article's PDF has been downloaded 153 times.