Lunch Talk: Rudi Poepsel Lemaitre

Pacha Sketches: Organizing Multidimensional Space for Efficient Aggregation

Join us for our Lunch Talk in July 2026. We’re very happy that Rudi Poepsel Lemaitre will present "Pacha Sketches: Organizing Multidimensional Space for Efficient Aggregation."

Abstract: Aggregating data items over subpopulations of a multidimensional space is a fundamental operation in applications such as statistical analysis, query optimization, and machine learning, but evaluating such queries at scale is infeasible without data summarization. In this paper, we introduce a principled hierarchical organization that distinguishes between categorical and numerical dimensions to organize the multidimensional space effectively. For numerical attributes, we extend dyadic ranges from one-dimensional to multi-dimensional domains, while for categorical attributes, we leverage AD-trees to efficiently identify and summarize categorical regions. Together, these components enable scalable and composable summarization of multidimensional data. We instantiate this organization in a novel data summarization technique, called Pacha Sketches. Pacha Sketches are designed to be mergeable, supporting efficient distributed computation in both federated and streaming settings. Moreover, Pacha Sketches are modular, allowing easy adaptation to different workloads, support for new aggregate functions, and extensions that provide formal privacy guarantees. Extensive experiments on real-world and synthetic datasets demonstrate that Pacha Sketches consistently achieve high accuracy and efficiency, even in high-dimensional settings with more than ten attributes and millions of tuples. Under equivalent space budgets, Pacha Sketches outperform state-of-the-art Omni Sketches by up to three orders of magnitude in estimation accuracy and two orders of magnitude in query performance.

The BIFOLD Lunch Talk series gives BIFOLD members and external partners the opportunity to engage in dialogue about their research in Machine Learning and Big Data. Each Lunch Talk offers BIFOLD members, fellows, and colleagues from other research institutes the chance to present their research and to network with each other. The Lunch Talk takes place at BIFOLD and online. For further information about the Lunch Talks, registration, and online participation, contact Dr. Laura Wollenweber via email.