  Efficient range-summability (ERS) of a long list of random variables is a
fundamental algorithmic problem that has applications to three important
database applications, namely, data stream processing, space-efficient
histogram maintenance (SEHM), and approximate nearest neighbor searches (ANNS).
In this work, we propose a novel dyadic simulation framework and develop three
novel ERS solutions, namely Gaussian-dyadic simulation tree (DST), Cauchy-DST
and Random Walk-DST, using it. We also propose novel rejection sampling
techniques to make these solutions computationally efficient. Furthermore, we
develop a novel k-wise independence theory that allows our ERS solutions to
have both high computational efficiencies and strong provable independence
guarantees.
