T-Digist

Info

T-Digest (t-Digest) - это вероятностная структура данных, которая позволяет эффективно оценивать квантили распределения данных в потоковом режиме. Он был предложен в статье "A New Data Structure for Efficient Estimation of Quantiles in Streaming Data" (Новая структура данных для эффективного оценки квантилей в потоковых данных) авторами Ted Dunning и Otmar Ertl.

Основная идея T-Digest заключается в том, чтобы сохранять центроиды (средние значения) небольших групп чисел, которые мы называем кластерами. Каждый кластер представляет собой центроид и его вес (количество чисел в кластере). Когда мы добавляем новое число в набор данных, мы пытаемся найти кластер, который может его принять, обновив центроид и вес кластера. Если такого кластера нет, мы создаем новый.

Преимущества

1. Эффективное использование памяти, поскольку он хранит только центроиды и веса кластеров, а не все отдельные числа.

2. Высокая скорость обработки потоковых данных, поскольку добавление новых чисел и оценка квантилей выполняется за логарифмическое время.

3. Высокая точность оценки квантилей, которая может быть контролирована параметром сжатия.

Недостатки

1. Оценки квантилей могут быть неточными, если в наборе данных присутствуют выбросы.

2. T-Digest не поддерживает операции удаления чисел из набора данных.