{"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":1775638455662,"version":"3.50.1"},"reference-count":28,"publisher":"MDPI AG","issue":"24","license":[{"start":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T00:00:00Z","timestamp":1670457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF CAREER","award":["1652257"],"award-info":[{"award-number":["1652257"]}]},{"name":"NSF CAREER","award":["2107239"],"award-info":[{"award-number":["2107239"]}]},{"name":"NSF award","award":["1652257"],"award-info":[{"award-number":["1652257"]}]},{"name":"NSF award","award":["2107239"],"award-info":[{"award-number":["2107239"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Approximating quantiles and distributions over streaming data has been studied for roughly two decades now. Recently, Karnin, Lang, and Liberty proposed the first asymptotically optimal algorithm for doing so. This manuscript complements their theoretical result by providing a practical variants of their algorithm with improved constants. For a given sketch size, our techniques provably reduce the upper bound on the sketch error by a factor of two. These improvements are verified experimentally. Our modified quantile sketch improves the latency as well by reducing the worst-case update time from O(1\u03b5) down to O(log1\u03b5).<\/jats:p>","DOI":"10.3390\/s22249612","type":"journal-article","created":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T03:59:46Z","timestamp":1670558386000},"page":"9612","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Streaming Quantiles Algorithms with Small Space and Update Time"],"prefix":"10.3390","volume":"22","author":[{"given":"Nikita","family":"Ivkin","sequence":"first","affiliation":[{"name":"Amazon, New York, NY 10001, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edo","family":"Liberty","sequence":"additional","affiliation":[{"name":"Pinecone, San Mateo, CA 94402, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Lang","sequence":"additional","affiliation":[{"name":"Yahoo Research, Sunnyvale, CA 94089, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zohar","family":"Karnin","sequence":"additional","affiliation":[{"name":"Amazon, New York, NY 10001, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Braverman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University, Houston, TX 77005, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., and Price, T.G. (June, January 30). Access path selection in a relational database management system. Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, MA, USA.","DOI":"10.1145\/582096.582099"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/235968.233342","article-title":"Improved histograms for selectivity estimation of range predicates","volume":"25","author":"Poosala","year":"1996","journal-title":"ACM Sigmod Rec."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Li, Z., Li, M., Wang, J., and Cao, Z. (2011, January 10\u201315). Ubiquitous data collection for mobile users in wireless sensor networks. Proceedings of the INFOCOM, 2011 Proceedings IEEE, Shanghai, China.","DOI":"10.1109\/INFCOM.2011.5935040"},{"key":"ref_4","first-page":"277","article-title":"Interpreting the data: Parallel analysis with Sawzall","volume":"13","author":"Pike","year":"2005","journal-title":"Sci. Program."},{"key":"ref_5","unstructured":"DeWitt, D.J., Naughton, J.F., and Schneider, D.A. (1991, January 4\u20136). Parallel sorting on a shared-nothing architecture using probabilistic splitting. Proceedings of the Parallel and Distributed Information Systems, First International Conference on IEEE, Miami Beach, FL, USA."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Chen, T., and Guestrin, C. (2016, January 13\u201317). Xgboost: A scalable tree boosting system. Proceedings of the 22nd ACM Sigkdd International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.","DOI":"10.1145\/2939672.2939785"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Liu, Z., Manousis, A., Vorsanger, G., Sekar, V., and Braverman, V. (2016, January 22\u201326). One sketch to rule them all: Rethinking network flow monitoring with univmon. Proceedings of the 2016 ACM SIGCOMM Conference, Florianopolis, Brazil.","DOI":"10.1145\/2934872.2934906"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Greenwald, M.B., and Khanna, S. (2004, January 14\u201316). Power-conserving computation of order-statistics over sensor networks. Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Paris, France.","DOI":"10.1145\/1055558.1055597"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Shrivastava, N., Buragohain, C., Agrawal, D., and Suri, S. (2004, January 3\u20135). Medians and beyond: New aggregation techniques for sensor networks. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, MD, USA.","DOI":"10.1145\/1031495.1031524"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Cormode, G., Garofalakis, M., Muthukrishnan, S., and Rastogi, R. (2005, January 14\u201316). Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, MD, USA.","DOI":"10.1145\/1066157.1066161"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/s00453-011-9584-4","article-title":"Optimal tracking of distributed heavy hitters and quantiles","volume":"65","author":"Yi","year":"2013","journal-title":"Algorithmica"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/2500128","article-title":"Mergeable summaries","volume":"38","author":"Agarwal","year":"2013","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Karnin, Z., Lang, K., and Liberty, E. (2016, January 9\u201311). Optimal quantile approximation in streams. Proceedings of the Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on IEEE, New Brunswick, NJ, USA.","DOI":"10.1109\/FOCS.2016.17"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Manku, G.S., Rajagopalan, S., and Lindsay, B.G. (1998, January 2\u20134). Approximate medians and other quantiles in one pass and with limited memory. Proceedings of the ACM SIGMOD Record, Seattle, WA, USA.","DOI":"10.1145\/276305.276342"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/304181.304204","article-title":"Random sampling techniques for space efficient online computation of order statistics of large datasets","volume":"28","author":"Manku","year":"1999","journal-title":"ACM SIGMOD Rec."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Wang, L., Luo, G., Yi, K., and Cormode, G. (2013, January 22\u201327). Quantiles over data streams: An experimental study. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, NY, USA.","DOI":"10.1145\/2463676.2465312"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1145\/376284.375670","article-title":"Space-efficient online computation of quantile summaries","volume":"30","author":"Greenwald","year":"2001","journal-title":"ACM SIGMOD Rec."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Greenwald, M.B., and Khanna, S. (2016). Quantiles and equi-depth histograms over streams. Data Stream Management, Springer.","DOI":"10.1007\/978-3-540-28608-0_3"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Arasu, A., and Manku, G.S. (2004, January 14\u201316). Approximate counts and quantiles over sliding windows. Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Paris, France.","DOI":"10.1145\/1055558.1055598"},{"key":"ref_20","unstructured":"Lin, X., Lu, H., Xu, J., and Yu, J.X. (2004, January 2). Continuously maintaining quantile summaries of the most recent n elements over a data stream. Proceedings of the Data Engineering, 2004 Proceedings, 20th International Conference on IEEE, Boston, MA, USA."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","article-title":"Selection and sorting with limited storage","volume":"12","author":"Munro","year":"1980","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","unstructured":"Felber, D., and Ostrovsky, R. (2015, January 24\u201326). A randomized online quantile summary in O (1\/epsilon* log (1\/epsilon)) words. Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Princeton, NJ, USA."},{"key":"ref_23","unstructured":"Dunning, T., and Ertl, O. (2019). Computing extremely accurate quantiles using t-digests. arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Gan, E., Ding, J., Tai, K.S., Sharan, V., and Bailis, P. (2018). Moment-based quantile sketches for efficient high cardinality aggregation queries. arXiv.","DOI":"10.14778\/3236187.3236212"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Masson, C., Rim, J.E., and Lee, H.K. (2019). DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees. arXiv.","DOI":"10.14778\/3352063.3352135"},{"key":"ref_26","unstructured":"(2020, February 19). Anonymized Internet Traces 2015. Available online: https:\/\/catalog.caida.org\/dataset\/passive_2015_pcap."},{"key":"ref_27","unstructured":"(2020, February 19). Page View Statistics for Wikimedia Projects. Available online: https:\/\/dumps.wikimedia.org\/other\/pagecounts-raw\/."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Huang, Z., Wang, L., Yi, K., and Liu, Y. (2011, January 12\u201316). Sampling based algorithms for quantile computation in sensor networks. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Athens, Greece.","DOI":"10.1145\/1989323.1989401"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/24\/9612\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:36:37Z","timestamp":1760146597000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/24\/9612"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,8]]},"references-count":28,"journal-issue":{"issue":"24","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["s22249612"],"URL":"https:\/\/doi.org\/10.3390\/s22249612","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,8]]}}}