Fast Perfect Sampling
En palabras de los autores
Perfect sampling is a powerful primitive for turnstile data streams, allowing algorithms to extract an index with probability proportional to its squared frequency, with applications to dynamic join size estimation, query optimization, heavy-hitters, sampling from self-joins, and real-time monitoring of evolving datasets. The setting is also the largest for which sampling can be achieved in polylogarithmic space. However, existing space-optimal perfect samplers rely on explicit polynomial duplication, requiring inefficient polynomial update times per stream arrival. Resolving a open question left by Swartworth, Woodruff, and Zhou [FOCS 2025], we present a perfect sampler that achieves an expected update time while maintaining an optimal bits of space.
Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: PODS 2027