Data streams as random permutations: the distinct element problem

MaRDI QIDQ2920864zbMATH OpenFDO

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

Publication date 29 September 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAQ0124/0.html

zbMATH Keywords

data streamprobabilistic algorithmrandom permutationrandom-order model

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Asymptotic enumeration (05A16) Combinatorial probability (60C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 2019620
• Range‐Efficient Counting of Distinct Elements in a Massive Data Stream
• Order statistics and estimating cardinalities of massive data sets
• Order statistics and estimating cardinalities of massive data sets
• A statistical analysis of probabilistic counting algorithms

Cited in

(7)

• Regenerative random permutations of integers
• Distinct counting with a self-learning bitmap
• scientific article; zbMATH DE number 2079346 (Why is no real title available?)
• Analysis of the strategy ``hiring above the \(m\)-th best candidate
• A framework for estimating stream expression cardinalities
• Cardinality estimation using Gumbel distribution
• Non-mergeable sketching for cardinality estimation

This page was built for publication: Data streams as random permutations: the distinct element problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920864)