Order statistics and estimating cardinalities of massive data sets

DOI10.1016/J.DAM.2008.06.020MaRDI QIDQ1003691zbMATH OpenOpenAlexFDO

Authors F. Giroire

Publication date 4 March 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.06.020

zbMATH Keywords

algorithm analysistraffic analysiscardinality estimatesvery large multisets

Mathematics Subject Classification ID

Order statistics; empirical distribution functions (62G30) Analysis of algorithms (68W40) Data structures (68P05)

Recommendations

• Order statistics and estimating cardinalities of massive data sets
• An optimal cardinality estimation algorithm based on order statistics and its full analysis
• Efficient estimation of the cardinality of large data sets
• Statistics of orderings
• scientific article; zbMATH DE number 1194773
• Order statistics: applications
• Relations, bounds and approximations for order statistics
• On Ordering Problems: A Statistical Approach
• Order statistics: theory \& methods
• scientific article; zbMATH DE number 962463

Cites work

• scientific article; zbMATH DE number 1615265 (Why is no real title available?)
• scientific article; zbMATH DE number 5763313 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2019620 (Why is no real title available?)
• scientific article; zbMATH DE number 1898358 (Why is no real title available?)
• Efficient estimation of the cardinality of large data sets
• Estimating the number of active flows in a data stream over a sliding window
• LogLog counting of large cardinalities (extended abstract)
• On adaptive sampling
• Order statistics and estimating cardinalities of massive data sets

Cited in

(17)

• An optimal cardinality estimation algorithm based on order statistics and its full analysis
• A Modular CDF Approach for the Approximation of Percentiles
• Order statistics and estimating cardinalities of massive data sets
• Efficient estimation of the cardinality of large data sets
• On distributed cardinality estimation: random arcs recycled
• scientific article; zbMATH DE number 5967674 (Why is no real title available?)
• Give me some slack: efficient network measurements
• LogLog counting of large cardinalities (extended abstract)
• A result in order statistics related to probabilistic counting
• A framework for estimating stream expression cardinalities
• Data streams as random permutations: the distinct element problem
• Approximating the size of a radio network in beeping model
• Fast size approximation of a radio network in beeping model
• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• A statistical analysis of probabilistic counting algorithms
• Loglog counting for IP traffic
• A unified scheme for generalizing cardinality estimators to sum aggregation

Describes a project that uses

Uses Software

• HyperLogLog

This page was built for publication: Order statistics and estimating cardinalities of massive data sets

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