BARC talk by Aleksander Łukasiewicz
On thursday, 16 October 2025, Aleksander Łukasiewicz, Postdoc at the Computer Science Institute of Charles University in Prague, will give a talk on "SplineSketch: Even More Accurate Quantiles with Error Guarantees".
Abstract
Space-efficient streaming estimation of quantiles in massive datasets is a fundamental problem with numerous applications in data monitoring and analysis. While theoretical research led to optimal algorithms, such as the Greenwald-Khanna algorithm or the KLL sketch, practitioners often use other sketches that perform significantly better in practice but lack theoretical guarantees. Most notably, the widely used t-digest has unbounded worst-case error.
In our work, we seek to get the best of both worlds. We present a new quantile summary, SplineSketch, for numeric data, offering near-optimal theoretical guarantees, namely uniformly bounded rank error, and outperforming t-digest by a factor of 2-20 on a range of synthetic and real-world datasets. To achieve such performance, we develop a novel approach that maintains a dynamic subdivision of the input range into buckets while fitting the input distribution using monotone cubic spline interpolation. The core challenge is implementing this method in a space-efficient manner while ensuring strong worst-case guarantees.
Joint work with Jakub Tětek and Pavel Veselý. Accepted to SIGMOD 2026.
Short bio
He is broadly interested in Theoretical Computer Science. The main theme of his research work is usage of tools from continuous mathematics (algebra, analysis, probability) to design and analyze combinatorial algorithms. This approach can be applied in many different contexts and so far, he has obtained new results in the realm of graph algorithms, fine-grained complexity, parameterized complexity, streaming algorithms and searching with noisy advice. Recently, he became heavily interested in designing theory-driven algorithms that achieve good performance in practical applications.Prior to his PhD studies Aleksander Łukasiewicz has obtained an M.Sc. in Computer Science and a B.Sc. in Joint Studies in Computer Science and Mathematics both from University of Wrocław. During his Masters he spent a semester in School of Computer and Communication Sciences at EPFL and a year at the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw as an exchange student. He has also been a tech intern at Facebook and Google several times.