一句话：研究几何范围查询下高效计算 Shannon/Rényi 熵的数据结构，给出条件下界、精确结构与近似结构。
数据分区中最大化或最小化 Shannon 熵（以及更一般的 Rényi 熵）是数据压缩、列式存储和基数估计等算法的关键子程序。已有方法多关注离线或流式计算，本文研究查询场景：给定 R^d 中 n 个带权带色点集 P，查询为超矩形 R，目标是以低空间、亚线性时间计算 P∩R 内基于颜色和权重的 Shannon 熵与 Rényi 熵。论文首先给出条件下界，证明两个问题不能同时达到近线性空间和近常数查询时间；随后提出 d=1 与 d>1 的精确数据结构，空间为 o(n^{2d})、查询时间为 o(n)；最后给出近线性空间的数据结构，可返回加性或乘性近似熵。
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$.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{EsmailpourKS25,
title = {Range (Rényi) Entropy Queries and Partitioning},
author = {Aryan Esmailpour and Sanjay Krishnan and Stavros Sintos},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 4},
year = {2025},
doi = {10.46298/lmcs-21(4:17)2025}
}