{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:53Z","timestamp":1781326733552,"version":"3.54.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"Ministry of Education of Czech Republic","award":["LL2406"],"award-info":[{"award-number":["LL2406"]}]},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["24-10306S"],"award-info":[{"award-number":["24-10306S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Grantov\u00e1 Agentura, Univerzita Karlova","award":["UNCE 24\/SCI\/008"],"award-info":[{"award-number":["UNCE 24\/SCI\/008"]}]},{"DOI":"10.13039\/100008398","name":"VILLUM Foundation","doi-asserted-by":"crossref","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100008306","name":"University of Wroc\u0142aw","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008306","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007397","name":"Charles University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100020975","name":"BARC, University of Copenhagen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100020975","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ministry of Education and Science of Bulgaria"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    Space-efficient streaming estimation of quantiles in massive datasets is a fundamental problem with numerous applications in data monitoring and analysis. While theoretical research led to optimal algorithms, such as the Greenwald-Khanna algorithm or the KLL sketch, practitioners often use other sketches that perform significantly better in practice but lack theoretical guarantees. Most notably, the widely used\n                    <jats:italic toggle=\"yes\">t<\/jats:italic>\n                    -digest has unbounded worst-case error. In this paper, we seek to get the best of both worlds. We present a new quantile summary, SplineSketch, for numeric data, offering near-optimal theoretical guarantees, namely uniformly bounded rank error, and outperforming\n                    <jats:italic toggle=\"yes\">t<\/jats:italic>\n                    -digest by a factor of 2-20 on a range of synthetic and real-world datasets. To achieve such performance, we develop a novel approach that maintains a dynamic subdivision of the input range into buckets while fitting the input distribution using monotone cubic spline interpolation.\n                  <\/jats:p>","DOI":"10.1145\/3769827","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["SplineSketch: Even More Accurate Quantiles with Error Guarantees"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1808-8330","authenticated-orcid":false,"given":"Aleksander","family":"\u0141ukasiewicz","sequence":"first","affiliation":[{"name":"Computer Science Institute, Charles University, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2046-1627","authenticated-orcid":false,"given":"Jakub","family":"T\u011btek","sequence":"additional","affiliation":[{"name":"INSAIT, University of Sofia \"St. Kliment Ohridski\", Sofia, Bulgaria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1169-7934","authenticated-orcid":false,"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[{"name":"Computer Science Institute, Charles University, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Elastic Docs - Percentiles. URL https:\/\/www.elastic.co\/docs\/reference\/aggregations\/search-aggregations-metricspercentile-aggregation. Accessed: 2025-10-13."},{"key":"e_1_2_1_2_1","unstructured":"TigerData Documentation - Tdigest(). URL https:\/\/docs.tigerdata.com\/api\/latest\/hyperfunctions\/percentileapproximation\/tdigest\/. Accessed: 2025-10-13."},{"key":"e_1_2_1_3_1","unstructured":"Apache Dubbo Documentation - metrics 2024. URL https:\/\/dubbo.apache.org\/en\/overview\/mannual\/java-sdk\/ reference-manual\/merics\/meter\/. Accessed: 2025-10-13."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.19"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.277655.123"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2024.109054"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/NOMS56928.2023.10154315"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3516431.3516433"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387650"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108769938"},{"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.1145\/3447548.3467152"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617891"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00364"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpa.2020.100049"},{"key":"e_1_2_1_17_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. URL http:\/\/arxiv.org\/abs\/1902.04023."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3015599"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1201\/9780203748725"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.775"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0905021"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0717021"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236212"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651610"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.115"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599505"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00156"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.24432\/C58K54"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.17"},{"key":"e_1_2_1_32_1","volume-title":"The UCI Machine Learning Repository. https:\/\/archive.ics.uci.edu","author":"Kelly Markelle","year":"2023","unstructured":"Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. The UCI Machine Learning Repository. https:\/\/archive.ics.uci.edu, 2023."},{"key":"e_1_2_1_33_1","volume-title":"NeurIPS Workshop on Machine Learning for Systems","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. SOSD: A benchmark for learned indexes. In NeurIPS Workshop on Machine Learning for Systems, 2019."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0424-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304204"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352135"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442337"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595629"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70504-8_12"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2021.18"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3736227.3736238"},{"key":"e_1_2_1_46_1","volume-title":"ICML'20","author":"Rothchild Daniel","year":"2020","unstructured":"Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication-efficient federated learning with sketching. In ICML'20, 2020. Paper link."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977714.8"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588937"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098144"},{"key":"e_1_2_1_51_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Smith Adam D.","year":"2020","unstructured":"Adam D. Smith, Shuang Song, and Abhradeep Thakurta. The Flajolet-Martin sketch itself preserves differential privacy: Private counting with minimal space. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/e3019767b1b23f82883c9850356b71d6-Abstract.html."},{"key":"e_1_2_1_52_1","volume-title":"How NOT to measure latency. Talk","author":"Tene Gil","year":"2015","unstructured":"Gil Tene. How NOT to measure latency. Talk available at https:\/\/www.youtube.com\/watch?v=lJ8ydIuPFeU, 2015."},{"key":"e_1_2_1_53_1","volume-title":"UCI Machine Learning Repository","author":"Whiteson Daniel","year":"2016","unstructured":"Daniel Whiteson. HEPMASS. UCI Machine Learning Repository, 2016."},{"key":"e_1_2_1_54_1","volume-title":"Lecture notes on splines. https:\/\/services.math.duke.edu\/~jtwong\/math563-2020\/lectures\/Lec1b-splines.pdf","author":"Wong Jeffrey","year":"2020","unstructured":"Jeffrey Wong. Lecture notes on splines. https:\/\/services.math.duke.edu\/~jtwong\/math563-2020\/lectures\/Lec1b-splines.pdf, 2020. Accessed: 2024-10-09."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321601"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769827","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:54:07Z","timestamp":1781326447000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769827"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":55,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769827"],"URL":"https:\/\/doi.org\/10.1145\/3769827","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}