Percentiles aggregation

[jpountz]

A percentiles aggregation would allow to compute (approximate) values of arbitrary percentiles based on the t-digest algorithm. Computing exact percentiles is not reasonably feasible as it would require shards to stream all values to the node that coordinates search execution, which could be gigabytes on a high-cardinality field. On the other hand, t-digest allows to trade accuracy for memory by trying to summarize the set of values that have been accumulated with interesting properties/features:

• compression is configurable, meaning that if you can configure it to have better accuracy at the cost of a higher memory usage,
• accuracy is excellent for extreme percentiles,
• percentiles are going to be accurate if few values were accumulated.

Example:

{
    "aggs" : {
        "load_time_outlier" : {
            "percentiles" : {
                "field" : "load_time",
                "percents" : [95, 99, 99.9] 
            }
        }
    }
}

[lukas-vlcek]

Beautiful!

[otisg]

Out of curiosity, why did you choose t-digest and not QDigest? Did you do extensive comparison and concluded that t-digest has both lower memory footprint, speed, and accuracy?

[jpountz]

The two main reasons why we did not consider q-digest are that it does not work with doubles and looked less accurate than t-digest. The t-digest paper also gives interesting explanations why t-digest performs better than q-digest.

[otisg]

Thanks Adrien! Sounds like you didn't actually run comparison tests, right? (not "blaming", just trying to understand). @tdunning may have more speed improvements in t-digest, a little bird told me...