{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:18Z","timestamp":1775638458495,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T00:00:00Z","timestamp":1628899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC-2014-CoG 647557"],"award-info":[{"award-number":["ERC-2014-CoG 647557"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007543","name":"Grantov\u00e1 Agentura, Univerzita Karlova","doi-asserted-by":"publisher","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}],"id":[{"id":"10.13039\/100007543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-27871X"],"award-info":[{"award-number":["19-27871X"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,8,14]]},"DOI":"10.1145\/3447548.3467152","type":"proceedings-article","created":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T06:13:10Z","timestamp":1628748790000},"page":"2722-2731","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Theory meets Practice at the Median: A Worst Case Comparison of Relative Error Quantile Algorithms"],"prefix":"10.1145","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhinav","family":"Mishra","sequence":"additional","affiliation":[{"name":"Splunk, , CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Ross","sequence":"additional","affiliation":[{"name":"Splunk, , CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Rep"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,14]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Apache DataSketches: KLL sketch vs t-digest. https:\/\/datasketches.apache.org\/docs\/QuantilesStudies\/KllSketchVsTDigest.html. Acessed: 2021-01--27.  Apache DataSketches: KLL sketch vs t-digest. https:\/\/datasketches.apache.org\/docs\/QuantilesStudies\/KllSketchVsTDigest.html. Acessed: 2021-01--27."},{"key":"e_1_3_2_2_2_1","unstructured":"Apache DataSketches: Quantiles and ranks definitions. https:\/\/datasketches.apache.org\/docs\/Quantiles\/Definitions.html. Acessed: 2021-05--24.  Apache DataSketches: Quantiles and ranks definitions. https:\/\/datasketches.apache.org\/docs\/Quantiles\/Definitions.html. Acessed: 2021-05--24."},{"key":"e_1_3_2_2_3_1","volume-title":"Mergeable summaries. ACM Transactions on Database Systems (TODS), 38(4):26","author":"Agarwal Pankaj K","year":"2013","unstructured":"Pankaj K Agarwal , Graham Cormode , Zengfeng Huang , Jeff M Phillips , Zhewei Wei , and Ke Yi . Mergeable summaries. ACM Transactions on Database Systems (TODS), 38(4):26 , 2013 . Pankaj K Agarwal, Graham Cormode, Zengfeng Huang, Jeff M Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. ACM Transactions on Database Systems (TODS), 38(4):26, 2013."},{"key":"e_1_3_2_2_4_1","volume-title":"ACM Symposium on Principles of Database Systems, 2021","author":"Cormode Graham","year":"2004","unstructured":"Graham Cormode , Zohar Karnin , Edo Liberty , Justin Thaler , and Pavel Vesel\u00fd . Relative error streaming quantiles . In ACM Symposium on Principles of Database Systems, 2021 . arXiv preprint arXiv: 2004 .01668. Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, and Pavel Vesel\u00fd. Relative error streaming quantiles. In ACM Symposium on Principles of Database Systems, 2021. arXiv preprint arXiv:2004.01668."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387650"},{"key":"e_1_3_2_2_6_1","volume-title":"Conservation of the t -digest scale invariant. arXiv preprint arXiv:1903.09919","author":"Dunning Ted","year":"2019","unstructured":"Ted Dunning . Conservation of the t -digest scale invariant. arXiv preprint arXiv:1903.09919 , 2019 . Ted Dunning. Conservation of the t -digest scale invariant. arXiv preprint arXiv:1903.09919, 2019."},{"key":"e_1_3_2_2_7_1","volume-title":"The size of a t -digest. arXiv preprint arXiv:1903.09921","author":"Dunning Ted","year":"2019","unstructured":"Ted Dunning . The size of a t -digest. arXiv preprint arXiv:1903.09921 , 2019 . Ted Dunning. The size of a t -digest. arXiv preprint arXiv:1903.09921, 2019."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpa.2020.100049"},{"key":"e_1_3_2_2_9_1","volume-title":"Computing extremely accurate quantiles using t-digests. arXiv preprint arXiv:1902.04023","author":"Dunning Ted","year":"2019","unstructured":"Ted Dunning and Otmar Ertl . Computing extremely accurate quantiles using t-digests. arXiv preprint arXiv:1902.04023 , 2019 . Ted Dunning and Otmar Ertl. Computing extremely accurate quantiles using t-digests. arXiv preprint arXiv:1902.04023, 2019."},{"key":"e_1_3_2_2_10_1","first-page":"775","volume-title":"APPROX\/RANDOM","author":"Felber David","year":"2015","unstructured":"David Felber and Rafail Ostrovsky . A randomized online quantile summary in O(1\/\u03b5 * \u0142og(1\/\u03b5)) words . In APPROX\/RANDOM , pages 775 -- 785 , 2015 . David Felber and Rafail Ostrovsky. A randomized online quantile summary in O(1\/\u03b5 * \u0142og(1\/\u03b5)) words. In APPROX\/RANDOM, pages 775--785, 2015."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236212"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_3_2_2_13_1","first-page":"253","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms","author":"Gupta Anupam","year":"2003","unstructured":"Anupam Gupta and Francis X. Zane . Counting inversions in lists . In Proceedings of ACM-SIAM Symposium on Discrete Algorithms , pages 253 -- 254 , 2003 . Anupam Gupta and Francis X. Zane. Counting inversions in lists. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pages 253--254, 2003."},{"key":"e_1_3_2_2_14_1","first-page":"89","volume-title":"Frontiers in Algorithmics","author":"Regant Y.","year":"2010","unstructured":"Regant Y. S. Hung and Hing-Fung Ting. An \u00f8mega(frac1\u03b5 \u0142og frac1\u03b5) space lower bound for finding \u03b5-approximate quantiles in a data stream . In Frontiers in Algorithmics , volume 6213 , pages 89 -- 100 . Springer , 2010 . Regant Y. S. Hung and Hing-Fung Ting. An \u00f8mega(frac1\u03b5 \u0142og frac1\u03b5) space lower bound for finding \u03b5-approximate quantiles in a data stream. In Frontiers in Algorithmics, volume 6213, pages 89--100. Springer, 2010."},{"key":"e_1_3_2_2_15_1","volume-title":"Streaming quantiles algorithms with small space and update time. arXiv preprint arXiv:1907.00236","author":"Ivkin Nikita","year":"2019","unstructured":"Nikita Ivkin , Edo Liberty , Kevin Lang , Zohar Karnin , and Vladimir Braverman . Streaming quantiles algorithms with small space and update time. arXiv preprint arXiv:1907.00236 , 2019 . Nikita Ivkin, Edo Liberty, Kevin Lang, Zohar Karnin, and Vladimir Braverman. Streaming quantiles algorithms with small space and update time. arXiv preprint arXiv:1907.00236, 2019."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.17"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0424-7"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276342"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304204"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352135"},{"key":"e_1_3_2_2_22_1","volume-title":"Selection and sorting with limited storage. Theoretical computer science, 12(3):315--323","author":"Ian Munro J","year":"1980","unstructured":"J Ian Munro and Michael S Paterson . Selection and sorting with limited storage. Theoretical computer science, 12(3):315--323 , 1980 . J Ian Munro and Michael S Paterson. Selection and sorting with limited storage. Theoretical computer science, 12(3):315--323, 1980."},{"key":"e_1_3_2_2_23_1","volume-title":"DataSketches: A library of stochastic streaming algorithms. Open source software: https:\/\/datasketches.apache.org\/","author":"Rhodes Lee","year":"2013","unstructured":"Lee Rhodes , Kevin Lang , Alexander Saydakov , Edo Liberty , and Justin Thaler . DataSketches: A library of stochastic streaming algorithms. Open source software: https:\/\/datasketches.apache.org\/ , 2013 . Lee Rhodes, Kevin Lang, Alexander Saydakov, Edo Liberty, and Justin Thaler. DataSketches: A library of stochastic streaming algorithms. Open source software: https:\/\/datasketches.apache.org\/, 2013."},{"key":"e_1_3_2_2_24_1","unstructured":"Joseph Ross. Asymmetric scale functions for t -digests. Journal of Statistical Computation and Simulation to appear. arXiv preprint arXiv:2005.09599.  Joseph Ross. Asymmetric scale functions for t -digests. Journal of Statistical Computation and Simulation to appear. arXiv preprint arXiv:2005.09599."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.145"}],"event":{"name":"KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Virtual Event Singapore","acronym":"KDD '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467152","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447548.3467152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:27Z","timestamp":1750191507000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,14]]},"references-count":25,"alternative-id":["10.1145\/3447548.3467152","10.1145\/3447548"],"URL":"https:\/\/doi.org\/10.1145\/3447548.3467152","relation":{},"subject":[],"published":{"date-parts":[[2021,8,14]]},"assertion":[{"value":"2021-08-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}