2026-07-24T12:23:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15891 2024-03-06T10:56:27Z ddc:004 open_access

A Dyadic Simulation Approach to Efficient Range-Summability Meng, Jingfan Wang, Huayi Xu, Jun Ogihara, Mitsunori fast range-summation locality-sensitive hashing rejection sampling 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jingfan Meng and Huayi Wang and Jun Xu and Mitsunori Ogihara 2022 Is Part Of LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2022.17 urn:nbn:de:0030-drops-158915 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.17 eng https://creativecommons.org/licenses/by/4.0/legalcode