3 ms·
Online (i.e. single pass) estimation of quantiles is a well-studied subject – doing some literature research would have gone a long way here. Back in 2004, this
by StefanKarpinski 12y ago
Online (i.e. single pass) estimation of quantiles is a well-studied subject – doing some literature research would have gone a long way here. Back in 2004, this was the best paper I found:
http://ftp10.us.freebsd.org/users/azhang/disc/SIGMOD/pdf-files/058/303-space.pdf http://ftp10.us.freebsd.org/users/azhang/disc/SIGMOD/pdf-fil...
The technique is efficient, straightforward and has provable error bounds. It was published in 2001, so it would also be worth looking at subsequent papers that have cited it for further improvements:
http://scholar.google.com/scholar?cites=6184540005789557130&as_sdt=5,33&sciodt=0,33&hl=en http://scholar.google.com/scholar?cites=6184540005789557130&...
- infinite8s 12y agoI've found that people in industry are often unaware of recent discoveries in academia (even if they themselves were once academics). Unfortunately most of the top journals of interest to datascientists are locked behind a paywall, but sometimes Google Scholar is able to find a free copy scraped from some academic's personal site (the "All N versions" link is usually helpful unless the paper was published in an ACM or IEEE journal - those guys seem to hunt down carelessly posted papers on people's private sites).