  $d$-dimensional (for $d>1$) efficient range-summability ($d$D-ERS) of random
variables (RVs) is a fundamental algorithmic problem that has applications to
two important families of database problems, namely, fast approximate wavelet
tracking (FAWT) on data streams and approximately answering range-sum queries
over a data cube. Whether there are efficient solutions to the $d$D-ERS
problem, or to the latter database problem, have been two long-standing open
problems. Both are solved in this work. Specifically, we propose a novel
solution framework to $d$D-ERS on RVs that have Gaussian or Poisson
distribution. Our $d$D-ERS solutions are the first ones that have
polylogarithmic time complexities. Furthermore, we develop a novel $k$-wise
independence theory that allows our $d$D-ERS solutions to have both high
computational efficiencies and strong provable independence guarantees.
Finally, we show that under a sufficient and likely necessary condition,
certain existing solutions for 1D-ERS can be generalized to higher dimensions.

Data Structures and Algorithms