{"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":1775638458455,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":24,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,20]],"date-time":"2021-06-20T00:00:00Z","timestamp":1624147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1918989, CCF-1845125"],"award-info":[{"award-number":["CCF-1918989, CCF-1845125"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,20]]},"DOI":"10.1145\/3452021.3458323","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T14:21:58Z","timestamp":1624026118000},"page":"96-108","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Relative Error Streaming Quantiles"],"prefix":"10.1145","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zohar","family":"Karnin","sequence":"additional","affiliation":[{"name":"Amazon, , CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edo","family":"Liberty","sequence":"additional","affiliation":[{"name":"Pinecone, San Mateo, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Thaler","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington, D.C., DC, 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,6,20]]},"reference":[{"key":"e_1_3_2_2_1_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_2_1","volume-title":"Proc. 7th Intl. Conf. Management of Data (COMAD-95)","author":"Agrawal Rakesh","year":"1995","unstructured":"Rakesh Agrawal and Arun Swami . A one-pass space-efficient algorithm for finding quantiles . In Proc. 7th Intl. Conf. Management of Data (COMAD-95) , Pune, India , 1995 . Rakesh Agrawal and Arun Swami. A one-pass space-efficient algorithm for finding quantiles. In Proc. 7th Intl. Conf. Management of Data (COMAD-95), Pune, India, 1995."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.55"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142389"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387650"},{"key":"e_1_3_2_2_7_1","volume-title":"Computing extremely accurate quantiles using t-digests. CoRR, abs\/1902.04023","author":"Dunning Ted","year":"2019","unstructured":"Ted Dunning and Otmar Ertl . Computing extremely accurate quantiles using t-digests. CoRR, abs\/1902.04023 , 2019 . Ted Dunning and Otmar Ertl. Computing extremely accurate quantiles using t-digests. CoRR, abs\/1902.04023, 2019."},{"key":"e_1_3_2_2_8_1","first-page":"775","volume-title":"Algorithms and Techniques (APPROX\/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Felber David","year":"2015","unstructured":"David Felber and Rafail Ostrovsky . A randomized online quantile summary in O(1\/epsilon * log(1\/epsilon)) words. In Approximation, Randomization, and Combinatorial Optimization . Algorithms and Techniques (APPROX\/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 775 -- 785 , Dagstuhl, Germany , 2015 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. David Felber and Rafail Ostrovsky. A randomized online quantile summary in O(1\/epsilon * log(1\/epsilon)) words. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pages 775--785, Dagstuhl, Germany, 2015. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_9_1","volume-title":"A nearly optimal and deterministic summary structure for update data streams. arXiv preprint cs\/0701020","author":"Ganguly Sumit","year":"2007","unstructured":"Sumit Ganguly . A nearly optimal and deterministic summary structure for update data streams. arXiv preprint cs\/0701020 , 2007 . Sumit Ganguly. A nearly optimal and deterministic summary structure for update data streams. arXiv preprint cs\/0701020, 2007."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_3_2_2_11_1","first-page":"253","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '03","author":"Gupta Anupam","year":"2003","unstructured":"Anupam Gupta and Francis X. Zane . Counting inversions in lists . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '03 , pages 253 -- 254 , Philadelphia, PA, USA , 2003 . Society for Industrial and Applied Mathematics. Anupam Gupta and Francis X. Zane. Counting inversions in lists. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '03, pages 253--254, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.17"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0424-7"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276342"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304204"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352135"},{"key":"e_1_3_2_2_17_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_18_1","volume-title":"A minimum storage algorithm for computing the median","author":"Pohl Ira","year":"1969","unstructured":"Ira Pohl . A minimum storage algorithm for computing the median . IBM TJ Watson Research Center , 1969 . Ira Pohl. A minimum storage algorithm for computing the median. IBM TJ Watson Research Center, 1969."},{"issue":"4","key":"e_1_3_2_2_19_1","first-page":"5","article-title":"Approximate query answering using histograms","volume":"22","author":"Poosala Viswanath","year":"1999","unstructured":"Viswanath Poosala , Venkatesh Ganti , and Yannis E. Ioannidis . Approximate query answering using histograms . IEEE Data Eng. Bull. , 22 ( 4 ): 5 -- 14 , 1999 . Viswanath Poosala, Venkatesh Ganti, and Yannis E. Ioannidis. Approximate query answering using histograms. IEEE Data Eng. Bull., 22(4):5--14, 1999.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_2_2_20_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_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_3_2_2_22_1","volume-title":"How NOT to measure latency. https:\/\/www.youtube.com\/watch?v=lJ8ydIuPFeU","author":"Tene Gil","year":"2015","unstructured":"Gil Tene . How NOT to measure latency. https:\/\/www.youtube.com\/watch?v=lJ8ydIuPFeU , 2015 . Gil Tene. How NOT to measure latency. https:\/\/www.youtube.com\/watch?v=lJ8ydIuPFeU, 2015."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321601"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.145"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452021.3458323","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3452021.3458323","content-type":"text\/html","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3452021.3458323","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3452021.3458323","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:00Z","timestamp":1750197780000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452021.3458323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,20]]},"references-count":24,"alternative-id":["10.1145\/3452021.3458323","10.1145\/3452021"],"URL":"https:\/\/doi.org\/10.1145\/3452021.3458323","relation":{},"subject":[],"published":{"date-parts":[[2021,6,20]]},"assertion":[{"value":"2021-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}