{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:31:35Z","timestamp":1768109495650,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,3,18]],"date-time":"2021-03-18T00:00:00Z","timestamp":1616025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>We empirically evaluate lightweight moment estimators for the single-pass quantile approximation problem, including maximum entropy methods and orthogonal series with Fourier, Cosine, Legendre, Chebyshev and Hermite basis functions. We show how to apply stable summation formulas to offset numerical precision issues for higher-order moments, leading to reliable single-pass moment estimators up to order 15. Additionally, we provide an algorithm for GPU-accelerated quantile approximation based on parallel tree reduction. Experiments evaluate the accuracy and runtime of moment estimators against the state-of-the-art KLL quantile estimator on 14,072 real-world datasets drawn from the OpenML database. Our analysis highlights the effectiveness of variants of moment-based quantile approximation for highly space efficient summaries: their average performance using as few as five sample moments can approach the performance of a KLL sketch containing 500 elements. Experiments also illustrate the difficulty of applying the method reliably and showcases which moment-based approximations can be expected to fail or perform poorly.<\/jats:p>","DOI":"10.1145\/3442337","type":"journal-article","created":{"date-parts":[[2021,3,18]],"date-time":"2021-03-18T10:29:12Z","timestamp":1616063352000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["An Empirical Study of Moment Estimators for Quantile Approximation"],"prefix":"10.1145","volume":"46","author":[{"given":"Rory","family":"Mitchell","sequence":"first","affiliation":[{"name":"Nvidia and University of Waikato, Hamilton, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eibe","family":"Frank","sequence":"additional","affiliation":[{"name":"University of Waikato, Hamilton, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Geoffrey","family":"Holmes","sequence":"additional","affiliation":[{"name":"University of Waikato, Hamilton, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"The Classical Moment Problem: And Some Related Questions in Analysis","author":"Akhiezer Naum I.","unstructured":"Naum I. Akhiezer . 1965. The Classical Moment Problem: And Some Related Questions in Analysis . Vol. 5 . Oliver & Boyd , Edinburgh, UK . Naum I. Akhiezer. 1965. The Classical Moment Problem: And Some Related Questions in Analysis. Vol. 5. Oliver & Boyd, Edinburgh, UK."},{"key":"e_1_2_1_2_1","unstructured":"Bernd Bischl Giuseppe Casalicchio Matthias Feurer Frank Hutter Michel Lang Rafael G. Mantovani Jan N. van Rijn and Joaquin Vanschoren. 2017. OpenML Benchmarking Suites. arxiv:stat.ML\/1708.03731  Bernd Bischl Giuseppe Casalicchio Matthias Feurer Frank Hutter Michel Lang Rafael G. Mantovani Jan N. van Rijn and Joaquin Vanschoren. 2017. OpenML Benchmarking Suites. arxiv:stat.ML\/1708.03731"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_4_1","first-page":"1559","article-title":"Estimation of an unknown distribution density from observations","volume":"3","author":"Cencov Nikolai N.","year":"1962","unstructured":"Nikolai N. Cencov . 1962 . Estimation of an unknown distribution density from observations . Soviet Mathematics 3 (1962), 1559 -- 1566 . Nikolai N. Cencov. 1962. Estimation of an unknown distribution density from observations. Soviet Mathematics 3 (1962), 1559--1566.","journal-title":"Soviet Mathematics"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/00031305.1983.10483115"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_2_1_7_1","volume-title":"Professional CUDA C Programming","author":"Cheng John","unstructured":"John Cheng , Max Grossman , and Ty McKercher . 2014. Professional CUDA C Programming . John Wiley & Sons , Indianapolis, IN . John Cheng, Max Grossman, and Ty McKercher. 2014. Professional CUDA C Programming. John Wiley & Sons, Indianapolis, IN."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4208\/aamm.2014.m504"},{"key":"e_1_2_1_10_1","unstructured":"Ted Dunning and Otmar Ertl. 2019. Computing extremely accurate quantiles using t-digests. arxiv:stat.CO\/1902.04023  Ted Dunning and Otmar Ertl. 2019. Computing extremely accurate quantiles using t-digests. arxiv:stat.CO\/1902.04023"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/wics.97"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/898758"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236212"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914050"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.106.620"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Karnin Z.","unstructured":"Z. Karnin , K. Lang , and E. Liberty . 2016. Optimal quantile approximation in streams . In Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916) . IEEE, Los Alamitos, CA, 71--78. Z. Karnin, K. Lang, and E. Liberty. 2016. Optimal quantile approximation in streams. In Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916). IEEE, Los Alamitos, CA, 71--78."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.09.001"},{"key":"e_1_2_1_19_1","volume-title":"Information Theory and Statistics","author":"Kullback Solomon","unstructured":"Solomon Kullback . 1997. Information Theory and Statistics . Dover Publications , Mineola, NY . Solomon Kullback. 1997. Information Theory and Statistics. Dover Publications, Mineola, NY."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0424-7"},{"key":"e_1_2_1_21_1","volume-title":"Handscomb","author":"Mason John C.","year":"2002","unstructured":"John C. Mason and David C . Handscomb . 2002 . Chebyshev Polynomials. Chapman & Hall . John C. Mason and David C. Handscomb. 2002. Chebyshev Polynomials. Chapman & Hall."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352135"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365490.1365500"},{"key":"e_1_2_1_25_1","first-page":"8","article-title":"Nvidia Cuda C programming guide","volume":"120","author":"Nvidia CUDA","year":"2011","unstructured":"CUDA Nvidia . 2011 . Nvidia Cuda C programming guide . Nvidia Corporation 120 , 18 (2011), 8 . CUDA Nvidia. 2011. Nvidia Cuda C programming guide. Nvidia Corporation 120, 18 (2011), 8.","journal-title":"Nvidia Corporation"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00180-015-0637-z"},{"key":"e_1_2_1_27_1","volume-title":"Flannery","author":"Press William H.","year":"2007","unstructured":"William H. Press , Saul A. Teukolsky , William T. Vetterling , and Brian P . Flannery . 2007 . Numerical Recipes 3rd Edition : The Art of Scientific Computing. Cambridge University Press , Cambridge, UK. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. 2007. Numerical Recipes 3rd Edition: The Art of Scientific Computing. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_28_1","first-page":"224","article-title":"\u00dcber empirische Funktionen und die Interpolation zwischen \u00e4quidistanten Ordinaten","volume":"46","author":"Runge Carl","year":"1901","unstructured":"Carl Runge . 1901 . \u00dcber empirische Funktionen und die Interpolation zwischen \u00e4quidistanten Ordinaten . Zeitschrift f\u00fcr Mathematik und Physik 46 , 224 \u2013 243 (1901), 20. Carl Runge. 1901. \u00dcber empirische Funktionen und die Interpolation zwischen \u00e4quidistanten Ordinaten. Zeitschrift f\u00fcr Mathematik und Physik 46, 224\u2013243 (1901), 20.","journal-title":"Zeitschrift f\u00fcr Mathematik und Physik"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-EJS1245"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1971.10488826"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:15Z","timestamp":1750193295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,18]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3442337"],"URL":"https:\/\/doi.org\/10.1145\/3442337","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,18]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}