2026-08-03T16:51:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17762 2024-03-06T11:00:26Z ddc:004 open_access

On Efficient Range-Summability of IID Random Variables in Two or Higher Dimensions Meng, Jingfan Wang, Huayi Xu, Jun Ogihara, Mitsunori fast range-summation multidimensional data streams Haar wavelet transform d-dimensional (for d > 1) efficient range-summability (dD-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 dD-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 dD-ERS on RVs that have Gaussian or Poisson distribution. Our dD-ERS solutions are the first ones that have polylogarithmic time complexities. Furthermore, we develop a novel k-wise independence theory that allows our dD-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jingfan Meng and Huayi Wang and Jun Xu and Mitsunori Ogihara 2023 Is Part Of LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2023.21 urn:nbn:de:0030-drops-177624 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.21 eng https://creativecommons.org/licenses/by/4.0/legalcode