Вероятностные структуры данных и алгоритмы

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

Фильтр Блума

Фильтры Блума (Bloom filters) — это компактные структуры данных, предназначенные для оценки мощности множества, а также для определения, содержат ли они определенный элемент, с высокой степенью вероятности. Фильтры Блума работают путем сопоставления добавленного элемента с одним или несколькими битами в битовой карте. Когда элемент добавляется в фильтр Блума, эти биты (в идеале только один бит) устанавливаются на значение 1.

Это означает, что n-битовый вход может быть сжат до одного бита. Хотя с помощью фильтров Блума можно сэкономить огромное количество памяти, компромисс заключается в том, что при определении, был ли добавлен данный элемент, имеется небольшая вероятность ложных срабатываний, потому что один входной элемент может потенциально сопоставляться с несколькими битами.

Как используются фильтры Блума в |product name|

Непрерывные представления, содержащие предложение SELECT DISTINCT (...), используют фильтры Блума, чтобы определить, является ли данное выражение уникальным, и, следовательно, включать ли его в непрерывный результат или нет. Это позволяет таким непрерывным представлениям использовать постоянный объем памяти при определении уникальности для бесконечного потока выражений с высокой степенью точности.

Пользователи также могут создавать свои собственные фильтры Блума и управлять ими с помощью встроенных функций |product name|.

Count-Min Sketch

Count-min sketch — это структура данных, аналогичная фильтру Блума, с основным отличием в том, что Count-min sketch оценивает частоту каждого элемента, добавленного в него, в то время как фильтр Блума только записывает, был ли добавлен данный элемент или нет.

В настоящее время ни одна функция Tantor PipelineDB не использует внутри структуру Count-min sketch, хотя пользователи могут свободно создавать свои собственные структуры данных Count-min sketch и управлять ими с помощью встроенных функций |product name|, которые их поддерживают.

Top-K

Filtered-Space Saving (FSS) — это комбинация структуры данных и алгоритма, полезная для точной оценки наиболее часто встречающихся значений top k, появляющихся в потоке, при использовании постоянного, минимального объема памяти. Очевидный подход к вычислению top-k — просто хранить таблицу значений и соответствующих частот, что не очень практично для потоков.

Вместо этого FSS хеширует входные значения в бакеты, где каждый бакет содержит уже добавленные значения. Если входящий элемент уже существует в определенном бакете, его частота увеличивается. Если элемент не существует, он будет добавлен, при удовлетворении определенных настраиваемых условий.

В настоящее время ни одна функция Tantor PipelineDB не использует неявно FSS. Тип FSS и связанные с ним функции доступны через различные встроенных функций |product name| и фильтры Блума, которые их поддерживают.

HyperLogLog

HyperLogLog — это комбинация структуры данных и алгоритма, которая, подобно фильтрам Блума, предназначена для оценки мощности множеств с очень высокой точностью. С точки зрения функциональности HyperLogLog поддерживает только добавление элементов и оценку мощности множества всех добавленных элементов. Проверка принадлежности конкретных элементов не поддерживается, в отличие от фильтров Блума. Однако эта комбинация значительно более эффективна с точки зрения использования памяти, чем фильтры Блума.

HyperLogLog работает путем разделения входного потока добавленных элементов и сохранения максимального количества начальных нулей, которые были обнаружены в каждом разделе. Поскольку элементы равномерно хешируются перед проверкой количества начальных нулей, общая идея заключается в том, что чем больше начальных нулей обнаружено, тем выше вероятность того, что было добавлено много уникальных элементов. Исходя из опыта, эта оценка оказывается очень точной — реализация HyperLogLog в Tantor PipelineDB проходит с погрешностью всего около 0,81% (это около 8 ошибок на 1 000 операций).

Как используется HyperLogLog в |product name|

Непрерывные представления, содержащие предложение COUNT(DISTINCT ...), используют HyperLogLog для точной оценки количества прочитанных уникальных выражений, используя постоянный объем памяти для бесконечного потока выражений. Агрегатная функция с гипотетическим набором dense_rank также использует HyperLogLog для точной оценки количества уникальных выражений более низкого ранга, которые были прочитаны, чтобы определить ранг гипотетического значения.

Пользователи также могут создавать свои собственные структуры данных HyperLogLog и управлять ими с помощью встроенных функций |product name|, которые их поддерживают.

T-Digest

T-Digest — это структура данных, которая позволяет проводить очень точные оценки статистики на основе ранга, таких как процентили и медианы, используя только постоянный объем памяти. Эффективность использования памяти за счет небольшой погрешности делает T-Digest оптимальным инструментом для вычислений на основе ранга в потоках, которые обычно требуют, чтобы входные данные были конечными и упорядоченными для идеальной точности. T-Digest по сути является адаптивной гистограммой, которая интеллектуально корректирует свои бакеты и частоты при добавлении к ней элементов.

Как T-Digest используется в |product name|

Агрегатная функция percentile_cont внутри использует T-Digest при работе с потоком. Пользователи также могут создавать собственные структуры данных T-Digest и управлять ими с помощью встроенных функций |product name|, которые их поддерживают.