{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:15Z","timestamp":1775638455393,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":21,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,14]],"date-time":"2020-06-14T00:00:00Z","timestamp":1592092800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","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\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,14]]},"DOI":"10.1145\/3375395.3387650","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T15:10:29Z","timestamp":1590765029000},"page":"81-93","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["A Tight Lower Bound for Comparison-Based Quantile Summaries"],"prefix":"10.1145","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,14]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"https:\/\/sublinear.info\/2","author":"Quantiles Problem","year":"2006","unstructured":"Problem 2: Quantiles . https:\/\/sublinear.info\/2 , 2006 . Accessed : 2019--12--10. Problem 2: Quantiles. https:\/\/sublinear.info\/2, 2006. Accessed: 2019--12--10."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.55"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142389"},{"key":"e_1_3_2_1_5_1","first-page":"775","volume-title":"Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX\/RANDOM)","author":"Felber David","year":"2015","unstructured":"David Felber and Rafail Ostrovsky . A randomized online quantile summary in O(1\/\u03b5 * log(1\/\u03b5)) words . In Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX\/RANDOM) , volume 40 , pages 775 -- 785 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , 2015 . David Felber and Rafail Ostrovsky. A randomized online quantile summary in O(1\/\u03b5 * log(1\/\u03b5)) words. In Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX\/RANDOM), volume 40, pages 775--785. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2015."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_3_2_1_7_1","first-page":"45","volume-title":"Greenwald and Sanjeev Khanna. Quantiles and Equi-depth Histograms over Streams","author":"Michael","year":"2016","unstructured":"Michael B. Greenwald and Sanjeev Khanna. Quantiles and Equi-depth Histograms over Streams , pages 45 -- 86 . Springer Berlin Heidelberg , 2016 . Michael B. Greenwald and Sanjeev Khanna. Quantiles and Equi-depth Histograms over Streams, pages 45--86. Springer Berlin Heidelberg, 2016."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/07069328x"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644150"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-642-14553-7_11","volume-title":"Frontiers in Algorithmics","author":"Hung Regant Y. S.","year":"2010","unstructured":"Regant Y. S. Hung and Hingfung F. Ting . An \u03a9(1\/\u03b5 log frac1varepsilon)$ space lower bound for finding \u03b5-approximate quantiles in a data stream . In Frontiers in Algorithmics , pages 89 -- 100 . Springer Berlin Heidelberg , 2010 . Regant Y. S. Hung and Hingfung F. Ting. An \u03a9(1\/\u03b5 log frac1varepsilon)$ space lower bound for finding \u03b5-approximate quantiles in a data stream. In Frontiers in Algorithmics, pages 89--100. Springer Berlin Heidelberg, 2010."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.17"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363746"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0424-7"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276342"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304204"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.39"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463719"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.145"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321601"}],"event":{"name":"SIGMOD\/PODS '20: International Conference on Management of Data","location":"Portland OR USA","acronym":"SIGMOD\/PODS '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387650","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375395.3387650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:48Z","timestamp":1750199568000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,14]]},"references-count":21,"alternative-id":["10.1145\/3375395.3387650","10.1145\/3375395"],"URL":"https:\/\/doi.org\/10.1145\/3375395.3387650","relation":{},"subject":[],"published":{"date-parts":[[2020,6,14]]},"assertion":[{"value":"2020-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}