I think the missing citation here (alluded to in TFA) is the stronger guarantee (avoids latency spike) Hood & Melville’s Real-time queue operations in pure LISP (1981) or the follow-up in Tarjan’s quite famous textbook Data Structures and Network Algorithms 1983 (a little past the article’s 1970s and not “obscure” at all). I was amused that all 3 are "Robert"s.
For the more general case of efficient non-aggregative (i.e. histogram/full distro-sensitive) incremental/online (i.e. push & pop) quantiles/etc., the fastest algos I know are in https://github.com/c-blake/adix/ , specifically adix/bist.nim (or /lmbist.nim or /embist.nim or etc.) (though I cannot find any citation pointing that out). They do have limited “resolution” (i.e. quantization error might be 3…6 significant figures depending upon CPU cache budgets), but in my experience that is already far more accurate than statistics are stable.
I think the missing citation here (alluded to in TFA) is the stronger guarantee (avoids latency spike) Hood & Melville’s Real-time queue operations in pure LISP (1981) or the follow-up in Tarjan’s quite famous textbook Data Structures and Network Algorithms 1983 (a little past the article’s 1970s and not “obscure” at all). I was amused that all 3 are "Robert"s.
For the more general case of efficient non-aggregative (i.e. histogram/full distro-sensitive) incremental/online (i.e. push & pop) quantiles/etc., the fastest algos I know are in https://github.com/c-blake/adix/ , specifically adix/bist.nim (or
/lmbist.nimor/embist.nimor etc.) (though I cannot find any citation pointing that out). They do have limited “resolution” (i.e. quantization error might be 3…6 significant figures depending upon CPU cache budgets), but in my experience that is already far more accurate than statistics are stable.score 4 · canonical