Skip to main content
SpringerLink
Log in

Incremental quantile estimation

  • Original Paper
  • Published:
Evolving Systems Aims and scope Submit manuscript

Abstract

Quantiles play an important role in data analysis. On-line estimation of quantiles for streaming data—i.e.data arriving step by step over time—especially with devices with limited memory and computation capacity like electronic control units is not as simple as incremental or recursive estimation of characteristics like the mean (expected value) or the variance. In this paper, we propose an algorithm for incremental quantile estimation that overcomes restrictions of previously described techniques. We also develop a statistical test for our algorithm to detect changes, so that the on-line estimation of the quantiles can be carried out in an adaptive or evolving manner. Besides a statistical analysis of our algorithm, we also provide experimental results comparing our algorithm with a recursive quantile estimation technique which is restricted to continuous random variables.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. For a random variable X with cumulative distribution function F X , the q-quantile (q  ∈ (0,1)) is defined as \(\inf\{x \in {\mathbb{R}}\mid F_X(x) \geq q\}.\) If x q is the q-quantile of a continuous random variable, this implies P(X ≤ x q ) = q and P(X ≥ x q ) = 1 − q.

References

  • Aho AV, Ullman JD, Hopcroft JE (1987) Data structures and algorithms. Addison Wesley, Boston

  • Fisz M (1963) Probability theory and mathematical statistics. New York: Wiley

    MATH  Google Scholar 

  • Gelper S, Schettlinger K, Croux C, Gather U (2008) Robust online scale estimation in time series: a model-free approach. J Stat Plan Inference 139(2):335–349

    Article  MathSciNet  Google Scholar 

  • Grieszbach G, Schack B (1993) Adaptive quantile estimation and its application in analysis of biological signals. Biom J 35(2):166–179

    Article  Google Scholar 

  • Hayes M (1996) Statistical digital signal processing and modeling. Wiley, New York

    Google Scholar 

  • Holm S (1979) A simple sequentially rejective multiple test procedure. Scand J Stat 6:65–70

    MATH  MathSciNet  Google Scholar 

  • Mann H, Whitney D (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann Math Stat 18(1):50–60

    Article  MATH  MathSciNet  Google Scholar 

  • Möller E, Grieszbach G, Schack B, Witte H (2000) Statistical properties and control algorithms of recursive quantile estimators. Biom J 42(6):729–746

    Article  MATH  MathSciNet  Google Scholar 

  • Nevelson M, Chasminsky R (1972) Stochastic approximation and recurrent estimation. Verlag Nauka, Moskau

    Google Scholar 

  • Nunkesser R, Fried R, Schettlinger K, Gather U (2009) Online analysis of time series by the \({\mathcal{Q}}_n\) estimator. Comput Stat Data Anal 53(6):2354–2362

    Article  MATH  Google Scholar 

  • Pang S, Ozawa S, Kasabo N (2005) Incremental linear discriminant analysis for classification of data streams. IEEE Trans Syst Man Cybern B Cybern 35:905–914

    Article  Google Scholar 

  • Qiu G (1996) An improved recursive median filtering scheme for image processing. IEEE Trans Image Process 5(4):646–648

    Article  Google Scholar 

  • Shaffer JP (1995) Multiple hypothesis testing. Ann Rev Psych 46:561–584

    Article  Google Scholar 

  • Wilcoxon F (1945) Individual comparisons by ranking methods. Biometrics Bull 1:80–83

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Ostfalia University of Applied Sciences, Salzdahlumer Str. 46/48, 38302, Wolfenbuettel, Germany

    Katharina Tschumitschew

  2. Bioinformatics and Statistics, Helmholtz Centre for Infection Research, Inhoffenstrasse 7, 38124, Braunschweig, Germany

    Frank Klawonn

Authors
  1. Katharina Tschumitschew
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Frank Klawonn
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Katharina Tschumitschew.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tschumitschew, K., Klawonn, F. Incremental quantile estimation. Evolving Systems 1, 253–264 (2010). https://doi.org/10.1007/s12530-010-9017-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12530-010-9017-7

Keywords

Search

Navigation