@inproceedings{957f0d9e2b6a444687fcb0b37b6a1857,
title = "Simple Analysis of Priority Sampling",
abstract = "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.",
author = "Majid Daliri and Juliana Freire and Christopher Musco and A{\'e}cio Santos and Haoxiang Zhang",
note = "Publisher Copyright: Copyright {\textcopyright} 2024 by SIAM.; 7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024 ; Conference date: 08-01-2024 Through 10-01-2024",
year = "2024",
language = "English (US)",
series = "2024 Symposium on Simplicity in Algorithms, SOSA 2024",
publisher = "Society for Industrial and Applied Mathematics Publications",
pages = "224--229",
editor = "Merav Parter and Seth Pettie",
booktitle = "2024 Symposium on Simplicity in Algorithms, SOSA 2024",
}