A unified scheme for generalizing cardinality estimators to sum aggregation

DOI10.1016/J.IPL.2014.10.009MaRDI QIDQ477684zbMATHOpenAlexFDO

Authors Reuven Cohen, Liran Katzir, Aviv Yehezkel

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2014.10.009

zbMATH Keywords

beta distributionextreme order statisticsbig data processingcardinality estimation algorithms

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Software, source code, etc. for problems pertaining to statistics (62-04) Statistics of extreme values; tail inference (62G32) Order statistics; empirical distribution functions (62G30) General topics in the theory of algorithms (68W01)

Recommendations

• A universal procedure for aggregating estimators
• Estimating the size of a union of random subsets of fixed cardinality
• Aggregation of affine estimators
• Optimal exponential bounds for aggregation of density estimators
• scientific article
• Aggregating estimates by convex optimization
• Linear and convex aggregation of density estimators
• Efficient estimation of the cardinality of large data sets

Cites work

• scientific article; zbMATH DE number 5763313 (Why is no real title available?)
• An optimal cardinality estimation algorithm based on order statistics and its full analysis
• Efficient estimation of the cardinality of large data sets
• Estimating the number of active flows in a data stream over a sliding window
• Handbook of Statistical Distributions with Applications
• Order statistics and estimating cardinalities of massive data sets
• Probabilistic counting algorithms for data base applications
• Simulation and the Monte Carlo Method
• Size-estimation framework with applications to transitive closure and reachability
• Stable distributions, pseudorandom generators, embeddings, and data stream computation

Describes a project that uses

Uses Software

• HyperLogLog

This page was built for publication: A unified scheme for generalizing cardinality estimators to sum aggregation

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