Improved sublinear-time moment estimation using weighted sampling

DOI10.1007/978-3-031-92932-8_12MaRDI QIDQ6902197zbMATH OpenFDO

Authors Anup Bhattacharya, Pinki Pradhan

Publication date 11 November 2025

Full work available at URL https://doi.org/10.1007/978-3-031-92932-8_12

zbMATH Keywords

beyond-worst case analysislower boundsmoment estimationsample complexitysublinear algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Approximating average parameters of graphs
• Asymptotically optimal bounds for estimating \(h\)-index in sublinear time with applications to subgraph counting
• Better sum estimation via weighted sampling
• Counting stars and other small subgraphs in sublinear-time
• Edge sampling and graph parameter estimation via vertex neighborhood accesses
• Estimating Sum by Weighted Sampling
• scientific article; zbMATH DE number 7204459 (Why is no real title available?)
• Introduction to Property Testing
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Sublinear time estimation of degree distribution moments: the arboricity connection
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• The space complexity of approximating the frequency moments
• Towards Optimal Moment Estimation in Streaming and Distributed Models

This page was built for publication: Improved sublinear-time moment estimation using weighted sampling

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