A Dyadic Simulation Approach to Efficient Range-Summability

Jingfan Meng, Huayi Wang, Jun Xu, Mitsunori Ogihara

Abstract

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.
BibTeX
@inproceedings{meng2022dyadic,
  author = {Jingfan Meng and Huayi Wang and Jun Xu and Mitsunori Ogihara},
  title = {{A Dyadic Simulation Approach to Efficient Range-Summability}},
  booktitle = {ICDT},
  year = {2022},
  url = {https://openreview.net/forum?id=hrg4ZZ_-HS},
}

Loading related content...

Figure