Simple Analysis of Priority Sampling

Majid Daliri,Juliana Freire,Christopher Musco,Aécio Santos,Haoxiang Zhang

SIAM Symposium on Simplicity in Algorithms（2023）

引用 0|浏览15

暂无评分

摘要

We prove a tight upper bound on the variance of the priority sampling method (aka sequential Poisson sampling). Our proof is significantly shorter and simpler than the original proof given by Mario Szegedy at STOC 2006, which resolved a conjecture by Duffield, Lund, and Thorup.

查看译文

AI 理解论文

溯源树

样例

生成溯源树，研究论文发展脉络

Chat Paper

正在生成论文摘要