BARC talk by Hongxun Wu

Monday, November 11, 2024, Hongxun Wu, PhD student at UC Berkeley, USA, will give a talk on "Relative error streaming quantiles via resizable sketches".

Abstract:
Given a stream of elements arriving online with total order, how can we approximate the rank of an element x in this stream with an multiplicative error of eps*rank(x), while maintaining only a small number of elements in memory at any time? This problem, known as the relative error streaming quantiles problem, has numerous applications in areas like database systems, network measurement, and beyond.

In this work, we investigate the optimal space complexity for this problem. The state-of-the-art algorithm by (Cormode, Karnin, Liberty, Thaler, Veselý, 2021) requires storing (log^1.5 (eps * n)) / eps elements in memory, while the trivial lower bound is (log (eps * n)) / eps . We close this gap (up to lower-order factors)  by designing an algorithm that nearly matches the trivial lower bound. Interestingly, a key innovation in our paper is the use of resizable sketches, which dynamically adjust their space usage based on demand. This flexibility allows us to adaptively compress and expand different components of the algorithm, significantly reducing overall space consumption.

Bio:
Hongxun Wu is a third-year PhD student at UC Berkeley. His research interest is mostly in proving space upper and lower bounds, such as streaming and derandomizing RL. He was a research intern at BARC five years ago, working with Mikkel Thorup on k-out sampling. 

Host:
Hanwen Zhang