Better sum estimation via weighted sampling

DOI10.1145/3650030MaRDI QIDQ7023546zbMATH OpenFDO

Authors Lorenzo Beretta, Jakub Tětek

Publication date 21 February 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3650030

zbMATH Keywords

edge countinglower boundsublinear algorithmsweighted sampling

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites work

• A Generalization of Sampling Without Replacement From a Finite Universe
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Approximating Average Parameters of Graphs
• Edge sampling and graph parameter estimation via vertex neighborhood accesses
• Efficient sampling strategies for relational database operations
• Estimating Sum by Weighted Sampling
• scientific article; zbMATH DE number 7204459 (Why is no real title available?)
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Sequential sampling techniques for algorithmic learning theory
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• Testing probability distributions underlying aggregated data
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time

This page was built for publication: Better sum estimation via weighted sampling

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