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 anovel 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.