{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:16:02Z","timestamp":1779174962266,"version":"3.51.4"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Junior Faculty Award","award":["AWD1007164"],"award-info":[{"award-number":["AWD1007164"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>Estimating the \u03b5-approximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream x_1,..., x_n from a universe \\mathcalU with total order, an additive-error quantile sketch \\mathcalM allows us to approximate the rank of any query y\\in \\mathcalU up to additive \u03b5 n error. In 2001, Greenwald and Khanna gave a deterministic algorithm (GK sketch) that solves the \u03b5-approximate quantiles estimation problem using O(\u03b5^-1 \u0142og(\u03b5 n)) space \\citegreenwald2001space ; recently, this algorithm was shown to be optimal by Cormode and Vesle\u00fd in 2020 \\citecormode2020tight. However, due to the intricacy of the GK sketch and its analysis, over-simplified versions of the algorithm are implemented in practical applications, often without any known theoretical guarantees. In fact, it has remained an open question whether the GK sketch can be simplified while maintaining the optimal space bound. In this paper, we resolve this open question by giving a simplified deterministic algorithm that stores at most (2 + o(1))\u03b5^-1 \u0142og (\u03b5 n) elements and solves the additive-error quantile estimation problem; as a side benefit, our algorithm achieves a smaller constant factor than the \\frac11 2 \u03b5^-1 \u0142og(\u03b5 n) space bound in the original GK sketch~\\citegreenwald2001space. Our algorithm features an easier analysis and still achieves the same optimal asymptotic space complexity as the original GK sketch. Lastly, our simplification enables an efficient data structure implementation, with a worst-case runtime of O(\u0142og(1\/\u03b5) + \u0142og \u0142og (\u03b5 n)) per-element for the ordinary \u03b5-approximate quantile estimation problem. Also, for the related \"weighted'' quantile estimation problem, we give efficient data structures for our simplified algorithm which guarantee a worst-case per-element runtime of O(\u0142og(1\/\u03b5) + \u0142og \u0142og (\u03b5 W_n\/w_\\textrmmin )), achieving an improvement over the previous upper bound of \\citeassadi2023generalizing.<\/jats:p>","DOI":"10.1145\/3651610","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-25","source":"Crossref","is-referenced-by-count":4,"title":["Simple &amp; Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-2731-6658","authenticated-orcid":false,"given":"Elena","family":"Gribelyuk","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8531-174X","authenticated-orcid":false,"given":"Pachara","family":"Sawettamalya","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5544-7517","authenticated-orcid":false,"given":"Hongxun","family":"Wu","sequence":"additional","affiliation":[{"name":"EECS, UC Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1450-1896","authenticated-orcid":false,"given":"Huacheng","family":"Yu","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. GKQuantiles Class - Micrometer Core 0.11.0.RELEASE Documentation. https:\/\/www.javadoc.io\/doc\/io. micrometer\/micrometer-core\/0.11.0.RELEASE\/io\/micrometer\/core\/instrument\/stats\/quantile\/GKQuantiles.html. Accessed: 2023--11--15."},{"key":"e_1_2_1_2_1","volume-title":"d.]. Problem 2: Quantiles - Open Problems in Sublinear Algorithms. https:\/\/sublinear.info\/index.php?title=Open_ Problems:2. Suggested by Graham Cormode","year":"2006","unstructured":"[n. d.]. Problem 2: Quantiles - Open Problems in Sublinear Algorithms. https:\/\/sublinear.info\/index.php?title=Open_ Problems:2. Suggested by Graham Cormode, Source: Kanpur 2006, Accessed: 2023--11--15."},{"key":"e_1_2_1_3_1","unstructured":"[n. d.]. quantiles Crate Documentation - Rust. https:\/\/docs.rs\/quantiles\/latest\/quantiles\/. Accessed: 2023--11--15."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451041"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742797"},{"key":"e_1_2_1_7_1","volume-title":"Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs. arXiv preprint arXiv:2303.06288","author":"Assadi Sepehr","year":"2023","unstructured":"Sepehr Assadi, Nirmit Joshi, Milind Prabhu, and Vihan Shah. 2023. Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs. arXiv preprint arXiv:2303.06288 (2023)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387658"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_10_1","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"Brodnik Andrej","unstructured":"Andrej Brodnik, Alejandro L\u00f3pez-Ortiz, Venkatesh Raman, and Alfredo Viola. 2013. Space-Efficient Data Structures, Streams, and Algorithms. Springer."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458323"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142389"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387650"},{"key":"e_1_2_1_15_1","volume-title":"Small summaries for big data","author":"Cormode Graham","unstructured":"Graham Cormode and Ke Yi. 2020. Small summaries for big data. Cambridge University Press."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a014"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITA.2012.6181772"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Gupta Anupam","unstructured":"Anupam Gupta and Francis X. Zane. 2003. Counting Inversions in Lists. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Maryland) (SODA '03). Society for Industrial and Applied Mathematics, USA, 253--254."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488624"},{"key":"e_1_2_1_21_1","volume-title":"breast 6, 1","author":"Ishwaran Hemant","year":"2023","unstructured":"Hemant Ishwaran, Udaya B Kogalur, and Maintainer Udaya B Kogalur. 2023. Package ?randomForestSRC'. breast 6, 1 (2023), 854."},{"key":"e_1_2_1_22_1","volume-title":"Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs)","author":"Karnin Zohar","unstructured":"Zohar Karnin, Kevin Lang, and Edo Liberty. 2016. Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs). IEEE, 71--78."},{"key":"e_1_2_1_23_1","volume-title":"Selection and sorting with limited storage. Theoretical computer science 12, 3","author":"Ian Munro J","year":"1980","unstructured":"J Ian Munro and Mike S Paterson. 1980. Selection and sorting with limited storage. Theoretical computer science 12, 3 (1980), 315--323."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_28"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321601"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.145"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651610","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651610","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:34Z","timestamp":1755898834000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651610"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651610"],"URL":"https:\/\/doi.org\/10.1145\/3651610","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}