Simple Analysis of Priority Sampling
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916362222305280 |
|---|---|
| author | Daliri, Majid Freire, Juliana Musco, Christopher Santos, Aécio Zhang, Haoxiang |
| author_facet | Daliri, Majid Freire, Juliana Musco, Christopher Santos, Aécio Zhang, Haoxiang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_05907 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Simple Analysis of Priority Sampling Daliri, Majid Freire, Juliana Musco, Christopher Santos, Aécio Zhang, Haoxiang Data Structures and Algorithms Databases 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. |
| title | Simple Analysis of Priority Sampling |
| topic | Data Structures and Algorithms Databases |
| url | https://arxiv.org/abs/2308.05907 |