{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:32:06Z","timestamp":1790749926628,"version":"4.1.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:p>\n            Recently the long standing problem of optimal construction of quantile sketches was resolved by\n            <jats:bold>K<\/jats:bold>\n            arnin,\n            <jats:bold>L<\/jats:bold>\n            ang, and\n            <jats:bold>L<\/jats:bold>\n            iberty using the KLL sketch (FOCS 2016). The algorithm for KLL is restricted to online insert operations and no delete operations. For many real-world applications, it is necessary to support delete operations. When the data set is updated dynamically, i.e., when data elements are inserted and deleted, the quantile sketch should reflect the changes. In this paper, we propose\n            <jats:italic>KLL<\/jats:italic>\n            <jats:sup>\u00b1<\/jats:sup>\n            , the first quantile approximation algorithm to operate in the\n            <jats:italic>bounded deletion<\/jats:italic>\n            model to account for both inserts and deletes in a given data stream. KLL\n            <jats:sup>\u00b1<\/jats:sup>\n            extends the functionality of KLL sketches to support arbitrary updates with small space overhead. The space bound for KLL\n            <jats:sup>\u00b1<\/jats:sup>\n            is [EQUATION], where \u2208 and \u03b4 are constants that determine precision and failure probability, and \u03b1 bounds the number of deletions with respect to insert operations. The experimental evaluation of KLL\n            <jats:sup>\u00b1<\/jats:sup>\n            highlights that with minimal space overhead, KLL\n            <jats:sup>\u00b1<\/jats:sup>\n            achieves comparable accuracy in quantile approximation to KLL.\n          <\/jats:p>","DOI":"10.14778\/3450980.3450990","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T16:17:16Z","timestamp":1618244236000},"page":"1215-1227","source":"Crossref","is-referenced-by-count":32,"title":["KLL\n            <sup>\u00b1<\/sup>\n            approximate quantile sketches over dynamic datasets"],"prefix":"10.14778","volume":"14","author":[{"given":"Fuheng","family":"Zhao","sequence":"first","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sujaya","family":"Maiyya","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"Wiener","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divyakant","family":"Agrawal","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amr El","family":"Abbadi","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_5_1","first-page":"421","article-title":"Sulla determinazione empirica delle leggi di probabilita","volume":"4","author":"Cantelli Francesco Paolo","year":"1933","journal-title":"Giorn. Ist. Ital. Attuari"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2974919"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007575"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","volume-title":"Small Summaries for Big Data","author":"Cormode Graham","DOI":"10.1017\/9781108769938"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Philippe Flajolet \u00c9ric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.  Philippe Flajolet \u00c9ric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287409"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_1_14_1","volume-title":"Data Stream Management","author":"Greenwald Michael B"},{"key":"e_1_2_1_15_1","unstructured":"Xiaojia Guo Kenneth C Lichtendahl and Yael Grushka-Cockayne. 2018. Quantile Forecasts of Product Life Cycles Using Exponential Smoothing. Harvard Business School.  Xiaojia Guo Kenneth C Lichtendahl and Yael Grushka-Cockayne. 2018. Quantile Forecasts of Product Life Cycles Using Exponential Smoothing. Harvard Business School."},{"key":"e_1_2_1_16_1","volume-title":"The Collected Works of Wassily Hoeffding","author":"Hoeffding Wassily"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007413"},{"key":"e_1_2_1_18_1","volume-title":"Streaming Quantiles Algorithms with Small Space and Update Time. arXiv preprint arXiv:1907.00236","author":"Ivkin Nikita","year":"2019"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196986"},{"key":"e_1_2_1_20_1","volume-title":"Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science focs)","author":"Karnin Zohar"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276342"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304204"},{"key":"e_1_2_1_23_1","unstructured":"Domas Mituzas. 2013. Page view statistics for Wikimedia projects.  Domas Mituzas. 2013. Page view statistics for Wikimedia projects."},{"key":"e_1_2_1_24_1","volume-title":"Selection and sorting with limited storage. Theoretical computer science 12, 3","author":"Ian Munro J","year":"1980"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233342"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/645922.673321"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465312"},{"key":"e_1_2_1_29_1","volume-title":"Human behavior and the principle of least effort: An introduction to human ecology","author":"Zipf George Kingsley"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3450980.3450990","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:14:12Z","timestamp":1672222452000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3450980.3450990"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3]]},"references-count":28,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["10.14778\/3450980.3450990"],"URL":"https:\/\/doi.org\/10.14778\/3450980.3450990","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,3]]}}}