As you know, I experimented with t-digest for exactly this case. I ran several tests comparing the t-digest percentiles with those calculated using the canonical method. I found most often that t-digest was about 1 - 3 milliseconds off from the canonically computed value. That having been said, I think this is important enough that I should re-run those tests and record the values. Then we can have a more informative discussion. I will post my results here, hopefully over the weekend.