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