{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T14:54:37Z","timestamp":1777128877340,"version":"3.51.4"},"reference-count":26,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T00:00:00Z","timestamp":1726185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>In this paper, we deal with the problem of monitoring network latency. Indeed, latency is a key network metric related to both network performance and quality of service, since it directly impacts on the overall user\u2019s experience. High latency leads to unacceptably slow response times of network services, and may increase network congestion and reduce the throughput, in turn disrupting communications and the user\u2019s experience. A common approach to monitoring network latency takes into account the frequently skewed distribution of latency values, and therefore specific quantiles are monitored, such as the 95th, 98th, and 99th percentiles. We present a comparative analysis of the speed of convergence of the sequential FRUGAL-1U, FRUGAL-2U, and EASYQUANTILE algorithms and the design and analysis of parallel, message-passing-based versions of these algorithms that can be used for monitoring network latency quickly and accurately. Distributed versions are also discussed. Extensive experimental results are provided and discussed as well.<\/jats:p>","DOI":"10.3390\/fi16090335","type":"journal-article","created":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T11:29:59Z","timestamp":1726226999000},"page":"335","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parallel and Distributed Frugal Tracking of a Quantile"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6408-1335","authenticated-orcid":false,"given":"Italo","family":"Epicoco","sequence":"first","affiliation":[{"name":"Department of Engineering for Innovation, University of Salento, 73100 Lecce, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4201-1504","authenticated-orcid":false,"given":"Marco","family":"Pulimeno","sequence":"additional","affiliation":[{"name":"Department of Engineering for Innovation, University of Salento, 73100 Lecce, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1118-7109","authenticated-orcid":false,"given":"Massimo","family":"Cafaro","sequence":"additional","affiliation":[{"name":"Department of Engineering for Innovation, University of Salento, 73100 Lecce, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,9,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"van der Spek, E., G\u00f6bel, S., Do, E.Y.L., Clua, E., and Baalsrud Hauge, J. (2019). Effects of End-to-end Latency on User Experience and Performance in Immersive Virtual Reality Applications. Proceedings of the Entertainment Computing and Serious Games, Springer International Publishing.","DOI":"10.1007\/978-3-030-34644-7"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Arapakis, I., Park, S., and Pielot, M. (2021, January 14\u201319). Impact of Response Latency on User Behaviour in Mobile Web Search. Proceedings of the 2021 Conference on Human Information Interaction and Retrieval, New York, NY, USA. CHIIR \u201921.","DOI":"10.1145\/3406522.3446038"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Jeffay, K., Stoica, I., and Wehrle, K. (2003). Using Latency Quantiles to Engineer QoS Guarantees for Web Services. Proceedings of the Quality of Service\u2014IWQoS 2003, Springer Berlin Heidelberg.","DOI":"10.1007\/3-540-44884-5"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1145\/3147.3165","article-title":"Random Sampling with a Reservoir","volume":"11","author":"Vitter","year":"1985","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"34585","DOI":"10.1109\/ACCESS.2020.2974919","article-title":"A survey of approximate quantile computation on large-scale data","volume":"8","author":"Chen","year":"2020","journal-title":"IEEE Access"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/s00778-016-0424-7","article-title":"Quantiles over Data Streams: Experimental Comparisons, New Analyses, and Further Improvements","volume":"25","author":"Luo","year":"2016","journal-title":"VLDB J."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Buragohain, C., and Suri, S. (2009). Quantiles on Streams. Encyclopedia of Database Systems, Springer.","DOI":"10.1007\/978-0-387-39940-9_290"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2195","DOI":"10.14778\/3352063.3352135","article-title":"DDSketch: A Fast and Fully-mergeable Quantile Sketch with Relative-error Guarantees","volume":"12","author":"Masson","year":"2019","journal-title":"Proc. VLDB Endow."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"147604","DOI":"10.1109\/ACCESS.2020.3015599","article-title":"UDDSketch: Accurate Tracking of Quantiles in Data Streams","volume":"8","author":"Epicoco","year":"2020","journal-title":"IEEE Access"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.inffus.2022.08.005","article-title":"Data stream fusion for accurate quantile tracking and analysis","volume":"89","author":"Cafaro","year":"2023","journal-title":"Inf. Fusion"},{"key":"ref_11","unstructured":"Cormode, G., Korn, F., Muthukrishnan, S., Muthukrishnan, S., and Srivastava, D. (2005, January 5\u20138). Effective Computation of Biased Quantiles over Data Streams. Proceedings of the 21st International Conference on Data Engineering, Washington, DC, USA. ICDE \u201905."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1647","DOI":"10.14778\/3236187.3236212","article-title":"Moment-based Quantile Sketches for Efficient High Cardinality Aggregation Queries","volume":"11","author":"Gan","year":"2018","journal-title":"Proc. VLDB Endow."},{"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 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, USA.","DOI":"10.1109\/FOCS.2016.17"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1145\/276305.276342","article-title":"Approximate Medians and Other Quantiles in One Pass and with Limited Memory","volume":"27","author":"Manku","year":"1998","journal-title":"SIGMOD Rec."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Greenwald, M., and Khanna, S. (2001, January 21\u201324). Space\u2014Efficient online computation of quantile summaries. Proceedings of the SIGMOD \u201901: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, Santa Barbara, CA, USA.","DOI":"10.1145\/375663.375670"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Govindaraju, N.K., Raghuvanshi, N., and Manocha, D. (2005, January 14\u201316). Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors. Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, MD, USA. SIGMOD \u201905.","DOI":"10.1145\/1066157.1066227"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"100049","DOI":"10.1016\/j.simpa.2020.100049","article-title":"The T-Dig. Effic. Estim. Distrib","volume":"7","author":"Dunning","year":"2021","journal-title":"Softw. Impacts"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Cormode, G., Karnin, Z., Liberty, E., Thaler, J., and Vesel\u00fd, P. (2021, January 20\u201325). Relative Error Streaming Quantiles. Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, New York, NY, USA. PODS\u201921.","DOI":"10.1145\/3452021.3458323"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1215","DOI":"10.14778\/3450980.3450990","article-title":"KLL\u00b1 approximate quantile sketches over dynamic datasets","volume":"14","author":"Zhao","year":"2021","journal-title":"Proc. VLDB Endow."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2500128","article-title":"Mergeable summaries","volume":"38","author":"Agarwal","year":"2013","journal-title":"ACM Trans. Database Syst."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., and Viola, A. (2013). Frugal Streaming for Estimating Quantiles. Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, Springer.","DOI":"10.1007\/978-3-642-40273-9"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Wang, B., Chen, R., and Tang, L. (2023, January 29\u201330). EasyQuantile: Efficient Quantile Tracking in the Data Plane. Proceedings of the 7th Asia-Pacific Workshop on Networking, New York, NY, USA. APNET \u201923.","DOI":"10.1145\/3600061.3600084"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Cafaro, M., Epicoco, I., and Pulimeno, M. (2024, January 3\u20137). Parallel and Distributed Frugal Tracking of a Quantile. Proceedings of the Seventh International Workshop on Systems and Network Telemetry and Analytics, New York, NY, USA. SNTA \u201924.","DOI":"10.1145\/3660320.3660332"},{"key":"ref_24","unstructured":"Grama, A., Karypis, G., Kumar, V., and Gupta, A. (2003). Introduction to Parallel Computing, Addison-Wesley Professional. [2nd ed.]."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/88.242438","article-title":"Isoefficiency: Measuring the Scalability of Parallel Algorithms and Architectures","volume":"1","author":"Grama","year":"1993","journal-title":"IEEE Parallel Distrib. Technol."},{"key":"ref_26","unstructured":"Quinn, M.J. (2003). Parallel Programming in C with MPI and OpenMP, McGraw-Hill."}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/16\/9\/335\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:55:58Z","timestamp":1760111758000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/16\/9\/335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,13]]},"references-count":26,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2024,9]]}},"alternative-id":["fi16090335"],"URL":"https:\/\/doi.org\/10.3390\/fi16090335","relation":{},"ISSN":["1999-5903"],"issn-type":[{"value":"1999-5903","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,13]]}}}