Sequential fixed-point quantile estimation

摘要

Disclosed are method and apparatus for calculating a quantile estimate of a data stream. A quantile estimate is calculated iteratively by calculating a first quantile estimate and then calculating a second quantile estimate by adding a first update increment to the first estimate. A first observation sample is acquired. A first quantile estimate and a first standard deviation estimate are set to the sample quantile and the sample standard deviation of the first observation sample. A second observation sample is then acquired. A second standard deviation estimate is calculated based at least in part on the first standard deviation estimate and the sample standard deviation of the second observation sample. A first update increment is calculated based at least in part on the second observation sample and based at least in part on the product of the second standard deviation estimate times a log odds ratio function.