Simple Analysis of Priority Sampling

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication2024 Symposium on Simplicity in Algorithms, SOSA 2024
EditorsMerav Parter, Seth Pettie
PublisherSociety for Industrial and Applied Mathematics Publications
Pages224-229
Number of pages6
ISBN (Electronic)9781713887171
StatePublished - 2024
Event7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024 - Alexandria, United States
Duration: Jan 8 2024Jan 10 2024

Publication series

Name2024 Symposium on Simplicity in Algorithms, SOSA 2024

Conference

Conference7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024
Country/TerritoryUnited States
CityAlexandria
Period1/8/241/10/24

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Simple Analysis of Priority Sampling'. Together they form a unique fingerprint.

Cite this