3 ms·

http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf http://infolab.stanford.edu/~datar/courses/cs361a/papers/qua... I've found Greenwald-Kha

• 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.