Range Entropy Queries and Partitioning

Sanjay Krishnan, Stavros Sintos

Introduction

Entropy serves as a critical metric for uncertainty and information density across diverse fields, from ecology to network security. In many practical applications, analysts need to compute the entropy of a specific subset of data defined by geometric constraints—for instance, calculating the Shannon entropy of sensor readings within a specific geographic bounding box. This paper introduces the first efficient data structures designed specifically for these "range entropy queries."

A 2D range entropy query R over a set of colored points.

The primary challenge lies in the fact that entropy is non-decomposable. Unlike simple metrics like sums or counts, the entropy of a union of sets cannot be derived solely from the individual entropies of those sets without knowing the underlying distribution of categories (or "colors") across the entire range. Naive approaches require a full data scan for every query, resulting in $O(n)$ time, which is impractical for large-scale interactive analysis.

Algorithmic Approaches

The authors propose a suite of data structures tailored to different accuracy requirements:

Exact Solutions

For 1D data, the researchers employ a "bucketing" strategy using canonical intervals and search trees to handle fringe points. In higher dimensions ($d > 1$), they introduce a novel method for partitioning points by category. A key technical contribution is a formula that allows updating Shannon and Rényi entropy in $O(1)$ time when merging sets with disjoint categories, enabling the structure to efficiently "stitch" precomputed results.

Approximations

To achieve even faster query times, the paper explores additive and multiplicative approximations:

  • Additive Approximation: By adapting the "dual access model" from property testing, the structures use range trees to sample points and estimate probabilities within the query window.
  • Multiplicative Approximation: This approach handles cases where entropy might be near zero by distinguishing between "heavy" distributions (dominated by one category) and "light" distributions (more uniform).

Theoretical Bounds and Performance

The paper establishes rigorous conditional lower bounds, proving that near-linear space combined with constant query time is likely impossible for this problem. This is achieved by reducing range entropy queries to known hard problems like Boolean Matrix Multiplication.

Summary of space and time complexities for various range entropy query algorithms.

Despite these theoretical limits, the proposed structures achieve significant speedups. For additive approximations, query times can become independent of the total number of points $n$, depending instead on the error threshold $\Delta$. For exact queries, the structures achieve sublinear $o(n)$ query times while maintaining manageable space complexity.

Practical Implications

The utility of these structures extends to several data engineering domains:

  • Database Optimization: In columnar storage formats like Apache Parquet, these algorithms can optimize horizontal partitioning to maximize compression ratios.
  • Data Partitioning: The structures reduce the time complexity of finding optimal $k$-bucket partitions from $O(kn^2)$ to $o(kn^2)$, facilitating faster indexing and histogram generation for massive datasets.

While the current exact structures are static, future work aims to bridge the gap between upper and lower bounds and develop fully dynamic versions capable of handling real-time data streams.

Summary updated

Abstract

Data partitioning that maximizes/minimizes the Shannon entropy, or more generally the Rényi entropy is a crucial subroutine in data compression, columnar storage, and cardinality estimation algorithms. These partition algorithms can be accelerated if we have a data structure to compute the entropy in different subsets of data when the algorithm needs to decide what block to construct. Such a data structure will also be useful for data analysts exploring different subsets of data to identify areas of interest. While it is generally known how to compute the Shannon or the Rényi entropy of a discrete distribution in the offline or streaming setting efficiently, we focus on the query setting where we aim to efficiently derive the entropy among a subset of data that satisfy some linear predicates. We solve this problem in a typical setting when we deal with real data, where data items are geometric points and each requested area is a query (hyper)rectangle. More specifically, we consider a set $P$ of $n$ weighted and colored points in $\mathbb{R}^d$, where $d$ is a constant. For the range S-entropy (resp. R-entropy) query problem, the goal is to construct a low space data structure, such that given a query (hyper)rectangle $R$, it computes the Shannon (resp. Rényi) entropy based on the colors and the weights of the points in $P\cap R$, in sublinear time. We show conditional lower bounds proving that we cannot hope for data structures with near-linear space and near-constant query time for both the range S-entropy and R-entropy query problems. Then, we propose exact data structures for $d=1$ and $d>1$ with $o(n^{2d})$ space and $o(n)$ query time for both problems. Finally, we propose near linear space data structures for returning either an additive or a multiplicative approximation of the Shannon (resp. Rényi) entropy in $P\cap R$.
BibTeX
@inproceedings{krishnan2024range,
  author = {Sanjay Krishnan and Stavros Sintos},
  title = {{Range Entropy Queries and Partitioning}},
  booktitle = {Icdt},
  year = {2024},
  doi = {10.4230/lipics.icdt.2024.6},
}
Figure