12 ms·

P² quantile estimator – estimating the median without storing values

tadkar 6y ago
Related to this, one of my favourite articles [1] suggests that it’s sufficient to only use one or two pieces of memory to get good estimates. Here’s a pretty amazing result from the paper. To estimate the median (loosely) on a stream, first set the median estimate m to 0 prior to seeing any data. Then as you observe the stream, increase the median estimate m by 1 if the current element s is bigger than m. Do nothing if the current element is the same as m. Decrease the estimate by 1 if the element is less than m. Then (given the right conditions) this process converges to the median. You can even extend this to quantiles by flipping a biased coin and then updating based on the result of the flip as well as the element comparison. The unfortunately now deceased neustar research blog had an interactive widget as well an outstanding write up[2] [1]https://arxiv.org/abs/1407.1121 https://arxiv.org/abs/1407.1121 [2] http://content.research.neustar.biz/blog/frugal.html http://content.research.neustar.biz/blog/frugal.html
- stellalo 6y ago
  That is essentially an online subgradient descent, with fixed stepsize 1, for minimizing the L1 loss.
  - tadkar 6y ago
    And would the 2 memory algorithm be equivalent to a gradient descent with momentum? I used to know what a sub gradient was, but I think there must be something more to the ideas in the paper because I’m struggling to see the analogy between gradient descent where you take steps probabilistically and the algorithm described. Perhaps I need to think about how you could potentially recast the quantile estimation problem as an optimisation problem and then apply what is effectively the machinery developed the train neural nets. Very interesting connection!
    - stellalo 6y ago
      Recasting quantile estimation as an optimization problem is trivial: the q-quantile minimizes the “pinball” loss (see first eqn in http://statweb.stanford.edu/~owen/courses/305a/lec18.pdf http://statweb.stanford.edu/~owen/courses/305a/lec18.pdf) with parameter q. What they do in the paper is to take subgradient steps with respect to the latest observation (just think about subgradients as gradients, since the loss function is everywhere differentiable except for one point)
      - zaroth 6y ago
        I hate it when the complexity of the lingo dramatically exceeds the complexity of the algorithm. Language shouldn’t be the barrier to understanding. This seems to be particularly true in computer learning. We’re taking about a conditional step function here, right?
        eru 6y ago
        The lingo is complex here, because it's general enough to be used for much more complicated cases. Think of it as a 'hello world' program. The typically 'hello world' program in eg Java teaches you more about the lingo of Java than about solving the problem of putting 'hello world' on the screen. (Of course, there are still plenty of bad reasons to describe simple things in complex lingo. But the above is one good reason.)
    - stellalo 6y ago
      Actually, it looks like in the paper something else is going on other than subgradient steps: there is some more randomization going on, that can prevent some steps from being taken. So yeah, there is a connection with online subgradient, but also more to it :-)
      - tadkar 6y ago
        Thanks for the loss function reference! I wonder if there’s something waiting to be discovered here about doing gradient descent but only taking steps with some probability. Definitely something to think about, I can’t imagine this idea hasn’t been explored before. Thanks a lot for the insightful comments, I’ve definitely seen that work in a very new light after knowing about it for years!!
  - srean 6y ago
    Yes indeed. I was quite startled when I saw that article published as I had been using this very method for years. Once you make the connection that quantiles (and not just a median) are the minimum of a suitably chosen loss function the rest is very straightforward. Then there is expectiles too.
    - bollu 6y ago
      Can you offer an ELIUndergrad of what an expectile is and where I can read more about them?
      - DavidSJ 6y ago
        The introduction here appears to explain: https://projecteuclid.org/download/pdfview_1/euclid.ejs/1473187646 https://projecteuclid.org/download/pdfview_1/euclid.ejs/1473... Starting from the observation that the expectation of X is the constant c which minimizes the squared loss E[(X - c)^2], we can now generalize expectation by generalizing the loss function we aim to minimize. They do this by asymmetrically weighting over- or under-estimates, unlike the squared loss which is symmetric. This apparently has nice properties which the paper goes into.
      - srean 6y ago
        I think everyone has left the building. Just in case you are still here let me try. BTW am a fan of your popular math stuff. TLDR expectiles are to mean what quantiles are to median. A longer explanation follows. Mean can be looked upon as a location that minimizes a scheme of penalizing your 'prediction' of (many instances of) a random quantity. You can assume that the instances will be revealed after you have made the prediction. If your prediction is over/larger by e you will be penalized by e^2. If your prediction is lower by e then also the penalty is e^2. This makes mean symmetric. It punishes overestimates the same way as underestimates. Now if you were to be punished by absolute value |e| as opposed to e^2 then median would be your best prediction. Lets denote the error by e+ if the error is an over-estimate and -e- if its under. Both e+ and e- are non-negative. Now if the penalties were to be * e+ + a e- * that would have led to the different quantiles depending on the values of a > 0. Note a \neq 1 introduces the asymmetry. If you were to do introduce a similar asymmetric treatment of e+^2 and e-^2 that would have given rise to expectiles.
- zorgmonkey 6y ago
  Wayback Machine to the rescue yet again https://web.archive.org/web/20140327021232/http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-day-frugal-streaming/ https://web.archive.org/web/20140327021232/http://blog.aggre...
- hnracer 6y ago
  This is cool. What if the median is something like 0.03 and we know the order of magnitude. Would it be better to increment/decrement by 0.01 instead of 1? Also, can we initiate the filter to a sensible nonzero value instead of zero to speed up convergence and start off with a sensible estimate? I'm guessing the answer to both questions is yes.
- mehrdadn 6y ago
  This is a horrible algorithm... just imagine trying to find the median of {100, 101, 102, 103, 104}... your estimate would be 5 which is ridiculous. At the very least, you probably don't want your estimate to be in {-1, 0, +1} after seeing one element -- you want it to be that element instead. The conditions required for this to converge are incredibly strict - it's cool from a theoretical standpoint regarding the memory usage, but I wouldn't use it as anything in practice.
  - fwip 6y ago
    If you're trying to reduce the memory usage of calculating the median, you're not motivated by 5 element streams. Further, I don't think "number of items > k*median" is a particularly grueling criterion for this algorithm (where k is some constant based on the delta). Here is the first paragraph of the Introduction, for your reference: > Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. A typical application is in IP packet analysis systems such as Gigascope [8] where an example of a query is to find the median packet (or flow) size for IP streams from some given IP address. Since IP addresses send millions of packets in reasonable time windows, it is prohibitive to store all packet or flow sizes and estimate the median size. Another application is in social networking sites such as Facebook or Twitter where there are rapid updates from users, and one is interested in median time between successive updates from a user. In yet another example, search engines can model their search traffic and for each search term, want to estimate the median time between successive instances of that search. You can also read the paper to see how they implement Frugal-2U, which has better convergence characteristics for twice the memory. They even address your specific complaint: "Note that Frugal-1U and Frugal-2U algorithms are initialized by 0, but in practice they can be initialized by the first stream item to reduce the time needed to converge to true quantiles."
  - p1necone 6y ago
    I think the intent is to calculate medians on longer running streams of data than that. Why would you even use this algorithm for 5 values?
    - 6y ago
- diroussel 6y ago
  You can compute a sliding window average with the same amount of storage, and greater accuracy.
  - nitrogen 6y ago
    This is definitely not my field, but a sliding window requires N values to be stored (the window size, so you can subtract each element that ages out of the window from the running sum), while this appears to require only 1 value to be stored.
zjs 6y ago
I always appreciate alternatives to using an arithmetic mean.
superyesh 6y ago
Great article! One of my favorite data-structures lately is the https://github.com/tdunning/t-digest https://github.com/tdunning/t-digest. Would be great to see how it compares and what additional accuracy we get but storing some of the data.
convolvatron 6y ago
http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf http://infolab.stanford.edu/~datar/courses/cs361a/papers/qua... I've found Greenwald-Khanna to be a lot more accurate, and also quite suitable for turning into a visual PDF representation
- ignoramous 6y ago
  The P2 quantile estimator is pretty cheap to compute (in terms of CPU cycles). How does Greenwald-Khanna compare in terms of that?
  - convolvatron 6y ago
    it is a bit more expensive. you need to keep a tree of all the samples. the size of the tree is proportional to a given error bound which it maintains, so that's cool. there is a compression pass that you can run whenever you want that collapses subtrees, so you can tune that for a little time/memory tradeoff. the best part though is that they are composable. you can take two GK representations and merge them. and you can operate on them (truncate, convolve, scalar transforms) which makes them really good summaries for query optimizers.
_delirium 6y ago
I don't know much about quantile estimation, so possibly dumb question: why, in the experiments plotted here, does every estimator on every tested distribution underestimate the true median? I expected some errors, but not all systematically in the same direction.
yandie 6y ago
Have you done a comparison with https://datasketches.apache.org/'s https://datasketches.apache.org/'s KLL algorithm?
- ignoramous 6y ago
  Fixed link: https://datasketches.apache.org/docs/Quantiles/KLLSketch.html https://datasketches.apache.org/docs/Quantiles/KLLSketch.htm...
CamperBob2 6y ago
Interesting problem. Access to the last n values isn't usually a problem in my own statistical applications, since they are fully RAM-resident to begin with, but it's annoying to have to sort N recent values to find the median in an N-wide window. Anyone aware of good shortcuts for that?
codezero 6y ago
One of my favorite problems is solving median based on a stream of data that you can replay, but only using, something like 3 variables of the same type of the data (which I think needs to be integer) from the book Numerical Recipes in FORTRAN. It’s to optimize finding the median from a tape drive in the 70s, but the technique is pretty cute. You make a guess at the median, then basically sum how many are over, and under that value, then guess again until you have an even split. It’s also a problem I like to use to nerd snipe people, because why not. Check my work, because it’s been a long time since I worked with FORTRAN and I could have just remembered incorrectly :) https://github.com/jonlighthall/nrf77/blob/master/mdian2.f https://github.com/jonlighthall/nrf77/blob/master/mdian2.f
mike_steph 6y ago
Hi all, in case interesting/useful: some research I've been involved in takes a different approach to online quantile estimation (our work is based on Hermite series estimators) and compares favorably to online quantile estimation approaches based on stochastic approximation for example. We've recently released the code: https://github.com/MikeJaredS/hermiter https://github.com/MikeJaredS/hermiter I've done some comparisons versus the P^2 algorithm (using the OnlineStats implementation in Julia) and the Hermite series based algorithm appears to have comparable accuracy in the tests conducted. The Hermite based approach has the advantage that it estimates the full quantile function though, so arbitrary quantiles can be obtained at any point in time.

Related to this, one of my favourite articles [1] suggests that it’s sufficient to only use one or two pieces of memory to get good estimates. Here’s a pretty amazing result from the paper. To estimate the median (loosely) on a stream, first set the median estimate m to 0 prior to seeing any data. Then as you observe the stream, increase the median estimate m by 1 if the current element s is bigger than m. Do nothing if the current element is the same as m. Decrease the estimate by 1 if the element is less than m. Then (given the right conditions) this process converges to the median. You can even extend this to quantiles by flipping a biased coin and then updating based on the result of the flip as well as the element comparison. The unfortunately now deceased neustar research blog had an interactive widget as well an outstanding write up[2] [1]https://arxiv.org/abs/1407.1121 https://arxiv.org/abs/1407.1121 [2] http://content.research.neustar.biz/blog/frugal.html http://content.research.neustar.biz/blog/frugal.html

stellalo 6y ago
That is essentially an online subgradient descent, with fixed stepsize 1, for minimizing the L1 loss.
- tadkar 6y ago
  And would the 2 memory algorithm be equivalent to a gradient descent with momentum? I used to know what a sub gradient was, but I think there must be something more to the ideas in the paper because I’m struggling to see the analogy between gradient descent where you take steps probabilistically and the algorithm described. Perhaps I need to think about how you could potentially recast the quantile estimation problem as an optimisation problem and then apply what is effectively the machinery developed the train neural nets. Very interesting connection!
  - stellalo 6y ago
    Recasting quantile estimation as an optimization problem is trivial: the q-quantile minimizes the “pinball” loss (see first eqn in http://statweb.stanford.edu/~owen/courses/305a/lec18.pdf http://statweb.stanford.edu/~owen/courses/305a/lec18.pdf) with parameter q. What they do in the paper is to take subgradient steps with respect to the latest observation (just think about subgradients as gradients, since the loss function is everywhere differentiable except for one point)
    - zaroth 6y ago
      I hate it when the complexity of the lingo dramatically exceeds the complexity of the algorithm. Language shouldn’t be the barrier to understanding. This seems to be particularly true in computer learning. We’re taking about a conditional step function here, right?
      - eru 6y ago
        The lingo is complex here, because it's general enough to be used for much more complicated cases. Think of it as a 'hello world' program. The typically 'hello world' program in eg Java teaches you more about the lingo of Java than about solving the problem of putting 'hello world' on the screen. (Of course, there are still plenty of bad reasons to describe simple things in complex lingo. But the above is one good reason.)
  - stellalo 6y ago
    Actually, it looks like in the paper something else is going on other than subgradient steps: there is some more randomization going on, that can prevent some steps from being taken. So yeah, there is a connection with online subgradient, but also more to it :-)
    - tadkar 6y ago
      Thanks for the loss function reference! I wonder if there’s something waiting to be discovered here about doing gradient descent but only taking steps with some probability. Definitely something to think about, I can’t imagine this idea hasn’t been explored before. Thanks a lot for the insightful comments, I’ve definitely seen that work in a very new light after knowing about it for years!!
- srean 6y ago
  Yes indeed. I was quite startled when I saw that article published as I had been using this very method for years. Once you make the connection that quantiles (and not just a median) are the minimum of a suitably chosen loss function the rest is very straightforward. Then there is expectiles too.
  - bollu 6y ago
    Can you offer an ELIUndergrad of what an expectile is and where I can read more about them?
    - DavidSJ 6y ago
      The introduction here appears to explain: https://projecteuclid.org/download/pdfview_1/euclid.ejs/1473187646 https://projecteuclid.org/download/pdfview_1/euclid.ejs/1473... Starting from the observation that the expectation of X is the constant c which minimizes the squared loss E[(X - c)^2], we can now generalize expectation by generalizing the loss function we aim to minimize. They do this by asymmetrically weighting over- or under-estimates, unlike the squared loss which is symmetric. This apparently has nice properties which the paper goes into.
    - srean 6y ago
      I think everyone has left the building. Just in case you are still here let me try. BTW am a fan of your popular math stuff. TLDR expectiles are to mean what quantiles are to median. A longer explanation follows. Mean can be looked upon as a location that minimizes a scheme of penalizing your 'prediction' of (many instances of) a random quantity. You can assume that the instances will be revealed after you have made the prediction. If your prediction is over/larger by e you will be penalized by e^2. If your prediction is lower by e then also the penalty is e^2. This makes mean symmetric. It punishes overestimates the same way as underestimates. Now if you were to be punished by absolute value |e| as opposed to e^2 then median would be your best prediction. Lets denote the error by e+ if the error is an over-estimate and -e- if its under. Both e+ and e- are non-negative. Now if the penalties were to be * e+ + a e- * that would have led to the different quantiles depending on the values of a > 0. Note a \neq 1 introduces the asymmetry. If you were to do introduce a similar asymmetric treatment of e+^2 and e-^2 that would have given rise to expectiles.
zorgmonkey 6y ago
Wayback Machine to the rescue yet again https://web.archive.org/web/20140327021232/http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-day-frugal-streaming/ https://web.archive.org/web/20140327021232/http://blog.aggre...
hnracer 6y ago
This is cool. What if the median is something like 0.03 and we know the order of magnitude. Would it be better to increment/decrement by 0.01 instead of 1? Also, can we initiate the filter to a sensible nonzero value instead of zero to speed up convergence and start off with a sensible estimate? I'm guessing the answer to both questions is yes.
mehrdadn 6y ago
This is a horrible algorithm... just imagine trying to find the median of {100, 101, 102, 103, 104}... your estimate would be 5 which is ridiculous. At the very least, you probably don't want your estimate to be in {-1, 0, +1} after seeing one element -- you want it to be that element instead. The conditions required for this to converge are incredibly strict - it's cool from a theoretical standpoint regarding the memory usage, but I wouldn't use it as anything in practice.
- fwip 6y ago
  If you're trying to reduce the memory usage of calculating the median, you're not motivated by 5 element streams. Further, I don't think "number of items > k*median" is a particularly grueling criterion for this algorithm (where k is some constant based on the delta). Here is the first paragraph of the Introduction, for your reference: > Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. A typical application is in IP packet analysis systems such as Gigascope [8] where an example of a query is to find the median packet (or flow) size for IP streams from some given IP address. Since IP addresses send millions of packets in reasonable time windows, it is prohibitive to store all packet or flow sizes and estimate the median size. Another application is in social networking sites such as Facebook or Twitter where there are rapid updates from users, and one is interested in median time between successive updates from a user. In yet another example, search engines can model their search traffic and for each search term, want to estimate the median time between successive instances of that search. You can also read the paper to see how they implement Frugal-2U, which has better convergence characteristics for twice the memory. They even address your specific complaint: "Note that Frugal-1U and Frugal-2U algorithms are initialized by 0, but in practice they can be initialized by the first stream item to reduce the time needed to converge to true quantiles."
- p1necone 6y ago
  I think the intent is to calculate medians on longer running streams of data than that. Why would you even use this algorithm for 5 values?
  - 6y ago
diroussel 6y ago
You can compute a sliding window average with the same amount of storage, and greater accuracy.
- nitrogen 6y ago
  This is definitely not my field, but a sliding window requires N values to be stored (the window size, so you can subtract each element that ages out of the window from the running sum), while this appears to require only 1 value to be stored.

zjs 6y ago

I always appreciate alternatives to using an arithmetic mean.

superyesh 6y ago

Great article! One of my favorite data-structures lately is the https://github.com/tdunning/t-digest https://github.com/tdunning/t-digest. Would be great to see how it compares and what additional accuracy we get but storing some of the data.

convolvatron 6y ago

http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf http://infolab.stanford.edu/~datar/courses/cs361a/papers/qua... I've found Greenwald-Khanna to be a lot more accurate, and also quite suitable for turning into a visual PDF representation

ignoramous 6y ago
The P2 quantile estimator is pretty cheap to compute (in terms of CPU cycles). How does Greenwald-Khanna compare in terms of that?
- convolvatron 6y ago
  it is a bit more expensive. you need to keep a tree of all the samples. the size of the tree is proportional to a given error bound which it maintains, so that's cool. there is a compression pass that you can run whenever you want that collapses subtrees, so you can tune that for a little time/memory tradeoff. the best part though is that they are composable. you can take two GK representations and merge them. and you can operate on them (truncate, convolve, scalar transforms) which makes them really good summaries for query optimizers.

_delirium 6y ago

I don't know much about quantile estimation, so possibly dumb question: why, in the experiments plotted here, does every estimator on every tested distribution underestimate the true median? I expected some errors, but not all systematically in the same direction.

yandie 6y ago

Have you done a comparison with https://datasketches.apache.org/'s https://datasketches.apache.org/'s KLL algorithm?

ignoramous 6y ago
Fixed link: https://datasketches.apache.org/docs/Quantiles/KLLSketch.html https://datasketches.apache.org/docs/Quantiles/KLLSketch.htm...

CamperBob2 6y ago

Interesting problem. Access to the last n values isn't usually a problem in my own statistical applications, since they are fully RAM-resident to begin with, but it's annoying to have to sort N recent values to find the median in an N-wide window. Anyone aware of good shortcuts for that?

codezero 6y ago

One of my favorite problems is solving median based on a stream of data that you can replay, but only using, something like 3 variables of the same type of the data (which I think needs to be integer) from the book Numerical Recipes in FORTRAN. It’s to optimize finding the median from a tape drive in the 70s, but the technique is pretty cute. You make a guess at the median, then basically sum how many are over, and under that value, then guess again until you have an even split. It’s also a problem I like to use to nerd snipe people, because why not. Check my work, because it’s been a long time since I worked with FORTRAN and I could have just remembered incorrectly :) https://github.com/jonlighthall/nrf77/blob/master/mdian2.f https://github.com/jonlighthall/nrf77/blob/master/mdian2.f

mike_steph 6y ago

Hi all, in case interesting/useful: some research I've been involved in takes a different approach to online quantile estimation (our work is based on Hermite series estimators) and compares favorably to online quantile estimation approaches based on stochastic approximation for example. We've recently released the code: https://github.com/MikeJaredS/hermiter https://github.com/MikeJaredS/hermiter I've done some comparisons versus the P^2 algorithm (using the OnlineStats implementation in Julia) and the Hermite series based algorithm appears to have comparable accuracy in the tests conducted. The Hermite based approach has the advantage that it estimates the full quantile function though, so arbitrary quantiles can be obtained at any point in time.