{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:35:04Z","timestamp":1774949704108,"version":"3.50.1"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>Interactive analytics increasingly involves querying for quantiles over sub-populations of high cardinality datasets. Data processing engines such as Druid and Spark use mergeable summaries to estimate quantiles, but summary merge times can be a bottleneck during aggregation. We show how a compact and efficiently mergeable quantile sketch can support aggregation workloads. This data structure, which we refer to as the moments sketch, operates with a small memory footprint (200 bytes) and computationally efficient (50ns) merges by tracking only a set of summary statistics, notably the sample moments. We demonstrate how we can efficiently estimate quantiles using the method of moments and the maximum entropy principle, and show how the use of a cascade further improves query time for threshold predicates. Empirical evaluation shows that the moments sketch can achieve less than 1 percent quantile error with 15\u00d7 less overhead than comparable summaries, improving end query time in the MacroBase engine by up to 7\u00d7 and the Druid engine by up to 60\u00d7.<\/jats:p>","DOI":"10.14778\/3236187.3236212","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1647-1660","source":"Crossref","is-referenced-by-count":44,"title":["Moment-based quantile sketches for efficient high cardinality aggregation queries"],"prefix":"10.14778","volume":"11","author":[{"given":"Edward","family":"Gan","sequence":"first","affiliation":[{"name":"Stanford InfoLab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jialin","family":"Ding","sequence":"additional","affiliation":[{"name":"Stanford InfoLab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai Sheng","family":"Tai","sequence":"additional","affiliation":[{"name":"Stanford InfoLab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vatsal","family":"Sharan","sequence":"additional","affiliation":[{"name":"Stanford InfoLab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Bailis","sequence":"additional","affiliation":[{"name":"Stanford InfoLab"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Yahoo! data sketches library 2017. https:\/\/datasketches.github.io\/.  Yahoo! data sketches library 2017. https:\/\/datasketches.github.io\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536231"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_5_1","volume-title":"Oliver & Boyd","author":"Akhiezer N.","year":"1965"},{"key":"e_1_2_1_6_1","volume-title":"Springer Science & Business Media","author":"Ambrosio L.","year":"2008"},{"key":"e_1_2_1_7_1","first-page":"33","volume-title":"COLT","author":"Anandkumar A.","year":"2012"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035928"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.23919\/ECC.2003.7085055"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.057701"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.16"},{"key":"e_1_2_1_12_1","unstructured":"Y. Ben-Haim and E. Tom-Tov. A streaming parallel decision tree algorithm. Journal of Machine Learning Research 11(Feb):849--872 2010.   Y. Ben-Haim and E. Tom-Tov. A streaming parallel decision tree algorithm. Journal of Machine Learning Research 11(Feb):849--872 2010."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/234285.234289"},{"key":"e_1_2_1_14_1","volume-title":"Incorporated","author":"Beyer B.","year":"2016"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742783"},{"key":"e_1_2_1_17_1","volume-title":"Interacting with Large Distributed Datasets Using Sketch. In Eurographics Symposium on Parallel Graphics and Visualization","author":"Budiu M.","year":"2016"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-39940-9_290"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.196"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142480"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247649"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872838"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.23919\/ECC.2013.6669541"},{"key":"e_1_2_1_28_1","unstructured":"T. Dunning and O. Ertl. Computing extremeley accurate quantiles using t-digests. https:\/\/github.com\/tdunning\/t-digest 2017.  T. Dunning and O. Ertl. Computing extremeley accurate quantiles using t-digests. https:\/\/github.com\/tdunning\/t-digest 2017."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113425"},{"key":"e_1_2_1_30_1","volume-title":"Stanford University, 2018","author":"Gan E.","year":"1803"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-208360-0.50008-5"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"W. C. Gibson. The method of moments in electromagnetics. CRC press 2014.  W. C. Gibson. The method of moments in electromagnetics . CRC press 2014.","DOI":"10.1201\/b17119"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_1_35_1","first-page":"2121","volume-title":"ICDE","author":"Hall A.","year":"2016"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912775"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233333"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098184"},{"key":"e_1_2_1_39_1","unstructured":"T. Hunter H. Falaki and J. Bradley. Approximate algorithms in apache spark: Hyperloglog and quantiles. https:\/\/databricks.com\/blog\/2016\/05\/19\/approximate-algorithms-in-apache-spark-hyperloglog-and-quantiles.html 2016.  T. Hunter H. Falaki and J. Bradley. Approximate algorithms in apache spark: Hyperloglog and quantiles. https:\/\/databricks.com\/blog\/2016\/05\/19\/approximate-algorithms-in-apache-spark-hyperloglog-and-quantiles.html 2016."},{"key":"e_1_2_1_40_1","unstructured":"T. Italia. Telecommunications - sms call internet - mi 2015.  T. Italia. Telecommunications - sms call internet - mi 2015."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.106.620"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3097992"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806765"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816674"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946317"},{"key":"e_1_2_1_46_1","unstructured":"V. Khuc. lbfgs4j 2017. https:\/\/github.com\/vinhkhuc\/lbfgs4j.  V. Khuc. lbfgs4j 2017. https:\/\/github.com\/vinhkhuc\/lbfgs4j."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1525"},{"key":"e_1_2_1_48_1","first-page":"282","volume-title":"ICML","author":"Lafferty J. D.","year":"2001"},{"key":"e_1_2_1_49_1","unstructured":"M. Lichman. UCI machine learning repository 2013.  M. Lichman. UCI machine learning repository 2013."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589116"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007266"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0424-7"},{"key":"e_1_2_1_53_1","unstructured":"S. Madden M. J. Franklin J. M. Hellerstein and W. Hong. Tag: A tiny aggregation service for ad-hoc sensor networks. 2002.  S. Madden M. J. Franklin J. M. Hellerstein and W. Hong. Tag: A tiny aggregation service for ad-hoc sensor networks. 2002."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066191"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0030-1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420036114"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.526446"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2008.01.011"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3025453.3025456"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767884"},{"key":"e_1_2_1_62_1","first-page":"61","volume-title":"IJCAI Workshop on Machine Learning for Information Filtering","author":"Nigam K.","year":"1999"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2545664"},{"key":"e_1_2_1_64_1","unstructured":"W. H. Press. Numerical recipes 3rd edition: The art of scientific computing. Cambridge university press 2007.   W. H. Press. Numerical recipes 3rd edition: The art of scientific computing . Cambridge university press 2007."},{"key":"e_1_2_1_65_1","first-page":"275","volume-title":"NSDI","author":"Rabkin A.","year":"2014"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mcm.2005.07.004"},{"key":"e_1_2_1_67_1","unstructured":"N. Ray. The art of approximating distributions: Histograms and quantiles at scale. http:\/\/druid.io\/blog\/2013\/09\/12\/the-art-of-approximating-distributions.html 2013.  N. Ray. The art of approximating distributions: Histograms and quantiles at scale. http:\/\/druid.io\/blog\/2013\/09\/12\/the-art-of-approximating-distributions.html 2013."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2146382.2146386"},{"key":"e_1_2_1_69_1","first-page":"307","volume-title":"VLDB","author":"Sarawagi S.","year":"2000"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312231"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.56.4822"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.84"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831371"},{"key":"e_1_2_1_75_1","first-page":"511","volume-title":"CVPR","volume":"1","author":"Viola P."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465312"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064051"},{"key":"e_1_2_1_79_1","volume-title":"Springer","author":"Wasserman L.","year":"2010"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.186"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498291"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595631"},{"key":"e_1_2_1_83_1","first-page":"2","volume-title":"NSDI","author":"Zaharia M.","year":"2012"},{"key":"e_1_2_1_84_1","unstructured":"Z. Zhuang. An experimental study of distributed quantile estimation. ArXiv abs\/1508.05710 2015.  Z. Zhuang. An experimental study of distributed quantile estimation. ArXiv abs\/1508.05710 2015."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3236187.3236212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:43:43Z","timestamp":1672220623000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3236187.3236212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":84,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.14778\/3236187.3236212"],"URL":"https:\/\/doi.org\/10.14778\/3236187.3236212","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}