Parallel and Distributed Frugal Tracking of a Quantile
Pages 1 - 6
Abstract
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's 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's 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 parallel, message-passing based version of the Frugal algorithm that can be used for monitoring network latency quickly and accurately. A distributed version is also discussed.
References
[1]
Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, and Ke Yi. 2013. Mergeable summaries. ACM Trans. Database Syst. 38, 4, Article 26 (dec 2013), 28 pages.
[2]
Chiranjeeb Buragohain and Subhash Suri. 2009. Quantiles on Streams. Springer US, Boston, MA, 2235--2240.
[3]
Massimo Cafaro, Catiuscia Melle, Italo Epicoco, and Marco Pulimeno. 2023. Data stream fusion for accurate quantile tracking and analysis. Information Fusion 89 (2023), 155--165.
[4]
Zhiwei Chen and Aoqian Zhang. 2020. A survey of approximate quantile computation on large-scale data. IEEE Access 8 (2020), 34585--34597.
[5]
Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, and Pavel Veselý. 2021. Relative Error Streaming Quantiles. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Virtual Event, China) (PODS'21). Association for Computing Machinery, New York, NY, USA, 96--108.
[6]
Graham Cormode, Flip Korn, S. Muthukrishnan, S. Muthukrishnan, and Divesh Srivastava. 2005. Effective Computation of Biased Quantiles over Data Streams. In Proceedings of the 21st International Conference on Data Engineering (ICDE '05). IEEE Computer Society, Washington, DC, USA, 20--31.
[7]
Ted Dunning. 2021. The t-digest: Efficient estimates of distributions. Software Impacts 7 (2021), 100049.
[8]
I. Epicoco, C. Melle, M. Cafaro, M. Pulimeno, and G. Morleo. 2020. UDDSketch: Accurate Tracking of Quantiles in Data Streams. IEEE Access 8(2020), 147604--147617.
[9]
Ulrich Fiedler and Bernhard Plattner. 2003. Using Latency Quantiles to Engineer QoS Guarantees for Web Services. In Quality of Service --- IWQoS 2003, Kevin Jeffay, Ion Stoica, and Klaus Wehrle (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 345--362.
[10]
Edward Gan, Jialin Ding, Kai Sheng Tai, Vatsal Sharan, and Peter Bailis. 2018. Moment-based Quantile Sketches for Efficient High Cardinality Aggregation Queries. Proc. VLDB Endow. 11, 11 July 2018), 1647--1660.
[11]
Naga K. Govindaraju, Nikunj Raghuvanshi, and Dinesh Manocha. 2005. Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data (Baltimore, Maryland) (SIGMOD '05). ACM, 611--622.
[12]
Ananth Grama, Anshul Gupta, and Vipin Kumar. 1993. Isoefficiency: Measuring the Scalability of Parallel Algorithms and Architectures. IEEE Parallel and Distributed Technology 1, 3 (1993), 12--21.
[13]
Ananth Grama, George Karypis, Vipin Kumar, and Anshul Gupta. 2003. Introduction to Parallel Computing (2nd Edition).
[14]
Michael Greenwald and Sanjeev Khanna. 2001. Space-efficient online computation of quantile summaries. In SIGMOD '01: Proceedings of the 2001 ACM SIGMOD international conference on Management of data (Santa Barbara, California, United States). ACM, 58--66.
[15]
Z. Karnin, K. Lang, and E. Liberty. 2016. Optimal Quantile Approximation in Streams. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 71--78.
[16]
Ge Luo, Lu Wang, Ke Yi, and Graham Cormode. 2016. Quantiles over Data Streams: Experimental Comparisons, New Analyses, and Further Improvements. The VLDB Journal 25, 4 (2016), 449--472.
[17]
Ge Luo, Lu Wang, Ke Yi, and Graham Cormode. 2016. Quantiles over Data Streams: Experimental Comparisons, New Analyses, and Further Improvements. The VLDB Journal 25, 4 (aug 2016), 449--472.
[18]
Qiang Ma, S. Muthukrishnan, and Mark Sandler. 2013. Frugal Streaming for Estimating Quantiles. Springer Berlin Heidelberg, Berlin, Heidelberg, 77--96.
[19]
Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. 1998. Approximate Medians and Other Quantiles in One Pass and with Limited Memory. SIGMOD Rec. 27, 2 June 1998), 426--435.
[20]
Charles Masson, Jee E. Rim, and Homin K. Lee. 2019. DDSketch: A Fast and Fully-mergeable Quantile Sketch with Relative-error Guarantees. Proc. VLDB Endow. 12, 12 (Aug. 2019), 2195--2205.
[21]
Michael J. Quinn. 2003. Parallel Programming in C with MPI and OpenMP. McGraw-Hill.
[22]
Jeffrey S. Vitter. 1985. Random Sampling with a Reservoir. ACM Trans. Math. Softw. 11, 1 (mar 1985), 37--57.
[23]
Fuheng Zhao, Sujaya Maiyya, Ryan Wiener, Divyakant Agrawal, and Amr El Abbadi. 2021. KLL± approximate quantile sketches over dynamic datasets. Proc. VLDB Endow. 14, 7 (mar 2021), 1215--1227.
Index Terms
- Parallel and Distributed Frugal Tracking of a Quantile
Recommendations
A multi-level parallelization concept for high-fidelity multi-block solvers
SC '97: Proceedings of the 1997 ACM/IEEE conference on SupercomputingThe integration of high-fidelity Computational Fluid Dynamics (CFD) analysis tools with the industrial design process benefits greatly from the robust implementations that are transportable across a wide range of computer architectures. In the present ...
Parallel processing for image and video processing: Issues and challenges
Some meaningful hints about parallelization problems in image processing and analysis are discussed. The issues of the operation of various architectures used to solve vision problems, from the pipeline of dedicated operators to general purpose MIMD ...
Modeling of Loss Processes Arising from Packet Flows at Bottleneck Links
MMB & DFT 2014: Proceedings of the 17th International GI/ITG Conference on Measurement, Modelling, and Evaluation of Computing Systems and Dependability and Fault Tolerance - Volume 8376Packet video and voice are the dominant traffic sources in today's Internet. Numerous studies have dealt with the influence of packet loss on video and voice quality. We elaborate on the root causes of packet loss in the Internet and show by statistical ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
43 pages
ISBN:9798400706486
DOI:10.1145/3660320
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 06 September 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SNTA '24
Sponsor:
SNTA '24: Seventh International Workshop on Systems and Network Telemetry and Analytics
June 3 - 7, 2024
Pisa, Italy
Acceptance Rates
Overall Acceptance Rate 22 of 106 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 29Total Downloads
- Downloads (Last 12 months)29
- Downloads (Last 6 weeks)5
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in