skip to main content
10.5555/1218112.1218501acmconferencesArticle/Chapter ViewAbstractPublication PageswscConference Proceedingsconference-collections
Article

Quantile estimation: a minimalist approach

Published: 03 December 2006 Publication History

Abstract

Managing telecommunication networks involves collecting and analyzing large amounts of statistical data. The standard approach to estimating quantiles involves capturing all the relevant data (what may require significant storage/processing capacities), and performing an off-line analysis (what may delay management actions). It is often essential to estimate quantiles as the data are collected, and to take management actions promptly. Towards this goal, we present a minimalist approach to sequentially estimating constant/changing over time quantiles. We follow prior work and devise a fixed-point algorithm, which does not estimate the unknown probability density function at the quantile. Instead, our algorithm uses the log-odds transformation of the observed fractions, and the exponentially smoothed estimates of the standard deviation to update the quantile estimate. For large data streams, this algorithm can significantly reduce the amount of collected data and the complexity of data analysis.

References

[1]
Chen, F., D. Lambert, and J. C. Pinheiro. 2000. Incremental Quantile Estimation for Massive Tracking. Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 516--522.]]
[2]
Chen, J. E., and D. W. Kelton. 2001. Quantile and Histogram Estimation. Proceedings of the Winter Simulation Conference, 451--459. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.]]
[3]
Chen, J. E. 2002. Two-Phase Quantile Estimation. Proceedings of the 2002 Winter Simulation Conference, 447--455. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.]]
[4]
Greenwald, M., and S. Khanna, S. 2001. Space-Efficient Online Computation of Quantile Summaries. Proceedings of the ACM SIGMOD Conference, 47--57.]]
[5]
Lee, J. R., D. McNickle, and K. Pawlikowski. 1998. Sequential Estimation of Quantiles. Technical Report TR-COSC 05/98. Department of Computer Science, University of Canterbury, Christchurch, New Zealand.]]
[6]
Manku, G. S., S. Rajagopalan, and B. G. Lindsay. 1998. Approximate Medians and other Quantiles in One Pass and with Limited Memory. In Proceedings of the ACM International Conference on Management of Data, 426--435.]]
[7]
Tierney, L. 1983. A space-efficient recursive procedure for estimating a quantile of an unknown distribution. SIAM Journal on Scientific and Statistical Computing. Vol. 4, Issue 4, 706--711.]]

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
WSC '06: Proceedings of the 38th conference on Winter simulation
December 2006
2429 pages
ISBN:1424405017

Sponsors

  • IIE: Institute of Industrial Engineers
  • ASA: American Statistical Association
  • IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
  • IEEE-CS\DATC: The IEEE Computer Society
  • SIGSIM: ACM Special Interest Group on Simulation and Modeling
  • NIST: National Institute of Standards and Technology
  • (SCS): The Society for Modeling and Simulation International
  • INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation

Publisher

Winter Simulation Conference

Publication History

Published: 03 December 2006

Check for updates

Qualifiers

  • Article

Conference

WSC06
Sponsor:
  • IIE
  • ASA
  • IEICE ESS
  • IEEE-CS\DATC
  • SIGSIM
  • NIST
  • (SCS)
  • INFORMS-CS
WSC06: Winter Simulation Conference 2006
December 3 - 6, 2006
California, Monterey

Acceptance Rates

WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;
Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 258
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 07 Mar 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media