Вероятностные структуры данных

Probabilistic Data Structures - структуры данных, которые используют вероятностные методы для предоставления приближенных или вероятностных ответов на определенные запросы. Они часто применяются в случаях, когда точные ответы требуют большого объема памяти или вычислительных ресурсов, а приближенные ответы являются приемлемыми.

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

Примеры вероятностных структур данных включают вероятностные фильтры Блума (Bloom Filters), статистические счетчики (Count-Min Sketch), скетчи Худжа-Мунгера (HyperLogLog), вероятностные деревья и другие. Эти структуры данных обладают особенностью уменьшения потребления памяти, но могут допускать некоторую погрешность в результатах операций.

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

Фильтр Блума

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

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

По сравнению с хеш-таблицами фильтр Блума может обходиться на несколько порядков меньшими объёмами памяти, жертвуя детерминизмом. Обычно он используется для уменьшения числа запросов к несуществующим данным в структуре данных с более дорогостоящим доступом (например, расположенной на жестком диске или в сетевой базе данных), то есть для «фильтрации» запросов к ней.

Как фильтр это делает? Как я уже говорил, идея до гениальности проста. Заводится массив битов фиксированного размера m и набор из k различных хеш-функций, выдающих значения от 0 до m - 1. При необходимости добавить элемент к множеству, для элемента считается значение каждой хеш-функции и в массиве устанавливаются биты с соответствующими индексами.

Для проверки принадлежности, как вы уже догадались, достаточно посчитать значения хеш-функций для потенциального члена и убедиться, что все соответствующие биты установлены в единицу — это и будет ответом «возможно». Если же хотя бы один бит не равен единице, значит множество этого элемента не содержит — ответ «нет», элемент отфильтрован.

Примеры практических применений:

• Прокси-сервер Squid использует фильтры Блума для опции cache digests.
• Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.
• Компьютерные программы для проверки орфографии.

Count-Min Sketch

Статистические счетчики предоставляют приближенные оценки частоты элементов в потоке данных. Они используются для подсчета частоты элементов в больших объемах данных с ограниченными ресурсами. Count-Min Sketch использует несколько хэш-функций и массив счетчиков для суммирования и оценки частоты элементов

LogLog

Вероятностная структура данных, используемая для подсчета уникальных элементов в больших объемах данных. Она основана на технике хеширования и приближенно оценивает количество уникальных элементов, используя малое количество памяти. LogLog достигает высокой точности подсчета при малом использовании памяти.

LogLog - это алгоритм, используемый для оценки кардинальности (числа уникальных элементов) в наборе данных. Он основан на использовании хеш-функций и логарифмической шкалы. LogLog разбивает множество данных на несколько подмножеств и вычисляет максимальное количество ведущих нулей в хэш-значениях элементов каждого подмножества. Затем он комбинирует эти значения для получения оценки кардинальности. LogLog обеспечивает хорошую точность оценки, но требует больше памяти с увеличением размера данных.

HyperLogLog

HyperLogLog: является улучшенной версией LogLog и использует тот же базовый принцип для оценки кардинальности. Однако HLL включает дополнительные оптимизации, которые позволяют более эффективно использовать память и предоставлять более точные оценки в больших наборах данных. Вместо простого подсчета максимального количества ведущих нулей, HLL использует специальные функции хэширования (гиперлогарифмические хэши) и аппроксимацию среднего значения для повышения точности оценки кардинальности. HLL позволяет оценивать кардинальность с небольшой погрешностью при значительно меньшем использовании памяти по сравнению с LogLog.

Использование LogLog и HyperLogLog позволяет эффективно оценить количество уникальных элементов в больших объемах данных, что полезно в различных сценариях, таких как подсчет уникальных пользователей, подсчет уникальных IP-адресов и других аналитических задачах, где точное подсчет количество не требуется, а важна скорость и эффективность использования памяти.

MinHash

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

MinHash преобразует каждое множество в сигнатуру, представляющую его характеристики. Сигнатура формируется путем хеширования элементов множества с использованием случайных перестановок. Для каждого хэша выбирается минимальное значение из всех элементов множества. Таким образом, сигнатура состоит из минимальных хэшей, которые представляют собой уникальные черты множества.

Сравнение двух сигнатур MinHash позволяет оценить схожесть множеств, приближенно определить пересечение элементов и вычислить коэффициент Жаккара (отношение пересечения к объединению множеств). Чем меньше значение коэффициента Жаккара, тем менее схожи множества.

MinHash широко применяется в различных задачах, таких как поиск дубликатов, рекомендательные системы, анализ текстов и множество других, где требуется быстрая оценка схожести множеств при эффективном использовании памяти и вычислительных ресурсов.