التفاصيل البيبلوغرافية
| العنوان: |
On Efficient Range-Summability of Ideally IID Random Variables in Two or Higher Dimensions |
| المؤلفون: |
Meng, Jingfan, Wang, Huayi, Xu, Jun, Ogihara, Mitsunori |
| سنة النشر: |
2021 |
| المجموعة: |
Computer Science |
| مصطلحات موضوعية: |
Computer Science - Data Structures and Algorithms |
| الوصف: |
$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. |
| نوع الوثيقة: |
Working Paper |
| URL الوصول: |
http://arxiv.org/abs/2110.07753 |
| رقم الانضمام: |
edsarx.2110.07753 |
| قاعدة البيانات: |
arXiv |