2 Search Results for "Wang, Huayi"


Document
On Efficient Range-Summability of IID Random Variables in Two or Higher Dimensions

Authors: Jingfan Meng, Huayi Wang, Jun Xu, and Mitsunori Ogihara

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)


Abstract
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.

Cite as

Jingfan Meng, Huayi Wang, Jun Xu, and Mitsunori Ogihara. On Efficient Range-Summability of IID Random Variables in Two or Higher Dimensions. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{meng_et_al:LIPIcs.ICDT.2023.21,
  author =	{Meng, Jingfan and Wang, Huayi and Xu, Jun and Ogihara, Mitsunori},
  title =	{{On Efficient Range-Summability of IID Random Variables in Two or Higher Dimensions}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.21},
  URN =		{urn:nbn:de:0030-drops-177624},
  doi =		{10.4230/LIPIcs.ICDT.2023.21},
  annote =	{Keywords: fast range-summation, multidimensional data streams, Haar wavelet transform}
}
Document
A Dyadic Simulation Approach to Efficient Range-Summability

Authors: Jingfan Meng, Huayi Wang, Jun Xu, and Mitsunori Ogihara

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)


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.

Cite as

Jingfan Meng, Huayi Wang, Jun Xu, and Mitsunori Ogihara. A Dyadic Simulation Approach to Efficient Range-Summability. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{meng_et_al:LIPIcs.ICDT.2022.17,
  author =	{Meng, Jingfan and Wang, Huayi and Xu, Jun and Ogihara, Mitsunori},
  title =	{{A Dyadic Simulation Approach to Efficient Range-Summability}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.17},
  URN =		{urn:nbn:de:0030-drops-158915},
  doi =		{10.4230/LIPIcs.ICDT.2022.17},
  annote =	{Keywords: fast range-summation, locality-sensitive hashing, rejection sampling}
}
  • Refine by Author
  • 2 Meng, Jingfan
  • 2 Ogihara, Mitsunori
  • 2 Wang, Huayi
  • 2 Xu, Jun

  • Refine by Classification
  • 2 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 1 Mathematics of computing → Random number generation

  • Refine by Keyword
  • 2 fast range-summation
  • 1 Haar wavelet transform
  • 1 locality-sensitive hashing
  • 1 multidimensional data streams
  • 1 rejection sampling

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail