Когда память дороже точности: приближённые структуры данных

Введение

Когда мы решаем задачи на алгоритмических собеседованиях, от нас ждут правильного ответа — ответа, который пройдёт все тесты и корректную асимптотическую оценку. Обычно если решение требует \(O(n)\) дополнительной памяти — этого достаточно.

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

В этой статье мы разберём самые популярные и полезные из них: HyperLogLog — для оценки кардинальности, Фильтр Блума и Cuckoo Filter — для проверки принадлежности ко множеству, а также Count-Min Sketch — для расчёта частот появления элемента во множестве. Все эти алгориты потребляют \(O(1)\) памяти и позволяют настраивать точнсть ответов.

HyperLogLog

Предположим, нам нужно посчитать количество активных пользователей за определённый промежуток времени (DAU/MAU/WAU). Для этого мы сделаем запрос в БД следующего вида: SELECT COUNT(DISTINCT user_id) FROM events WHERE date=…. У этого запроса есть недостаток — для него нам нужно выделить память порядка \(O(n)\), а это сильно нагружает БД.

Рассмотрим другую задачу: мы занимаемся фича инжинирингом, и хотим узнать кардинальность категориального признака. Чтобы либо отбросить его, либо выбрать способ его кодирования. Поскольку данных у нас много, каждый раз нам придётся выделять \(O(n)\) памяти.

Для решения подобных проблем существует алгоритм HyperLogLog. Он используется в Redis и в большинстве ПО Apache, а также в расширениях для Postgres, Clickhouse, Trino и BigQuerry.

Алгоритм

Алгоритм используется для приближённой оценки количества уникальных элементов во множестве. Его временная сложность — O(n). Он использует фиксированное количество памяти.

1. Создаём массив \(M\) из \(m=2^p\) регистров, где \(p\) — параметр точности. Мы берём несколько регистров, поскольку они сглаживают дисперсию и не позволяют нам случайно завысить или занизить оценку.
2. Вычисляем хэш для каждого элемента. Хэш должен быть равномерным. В Redis, например, используют MurmurHash.
   • Первые \(p\) бит хэша используются как индекс счетчика (\(i\)) — номер корзины на картинке ниже.
   • В остальных битах считаем число нулей до первого значащего числа (leading zeros). Обновляем нужный регистр \(M_i=max(M_i,leading\_zeros )\), то есть просто вычисляем максимум. Формально мы могли бы считать единицы вместо нулей, и ничего не поменялось бы. Но нули считаются быстрее — для этого часто есть встроенные функции, например, __builtin_clz.
3. Вычисляем число уникальных элементов. \(E=a_mm^2(\sum^m_i2^{-M[i]})^{-1}\) , где \(a_m\) — константа нормализации, значения которой можно посмотреть в таблице ниже. Она была подобрана так, чтобы оценка максимально приближалась к истинному значению.

Количество регистров (m)	\(a_m\)
16	0.673
32	0.697
64	0.709
128	0.7213 / (1 + 1.079/m)

Значения \(a_m\) можно посчитать аналитически, но на практике обычно вычисляются через моделирование: генерируются случайные множества различных размеров и вычисляются \(a_m\), минимизирующие ошибку.

Идея алгоритма

Хэш-функция равномерная, значит, вероятность встретить k нулей в начале: \(P(k)=2^{−k}\). Это говорит о том, что уникальных элементов хотя бы \(2^k\). Далее мы считаем гармоническое среднее оценок по всем регистрам и умножаем его на константу \(a_m\) и на \(m\) для нормализации и масштабирования, получаем итоговую оценку.

Коррекция ошибок

Если у нас маленькое число уникальных элементов — многие регистры становятся равными нулю, и прямая формула завышает ошибку. На практике в таком случае берут порог в \(\frac{5}{2}m\) и используют Linear Counting.

Если V = количество нулевых регистров, то

\(E=m*ln(\frac{m}{V})\),

А если число уникальных элементов слишком велико — значения \(M_i\) становятся близки к пределу разрядности регистра (\(E>{\frac{2^{32}}{30}}\)). Значит, вероятность коллизий становится слишком большой, и формула недооценивает количество элементов. Тогда используется Large range correction:

\(E=−2^{32}ln(1−\frac{E}{2^{32}})\).

Union

Если нам нужно получить приближённую оценку числа уникальных элементов во множестве \(C\), состоящем из двух множеств \(A\) и \(B\) — мы можем посчитать \(HyperLogLog(A)\) и \(HyperLogLog(B)\), взять регистры, соответствующие множествам, и пересчитать новые регистры для \(M_{C_i} =max(M_{A_i},M_{B_i})\). И далее по ним посчитать число уникальных элементов.

С помощью этой функции можно даже посчитать Jaccard similarity.

Точность алгоритма

Стандартная ошибка алгоритма: \(RSE = \frac{1.04}{\sqrt{m}}\) . Это значит, что всреднем оценка будет отличаться на \(\frac{1.04}{\sqrt{m}}\). Например, в имплементации hyperloglog в Redis ошибка около 0.81%, и объём используемой памяти всего 12KB, значит, там используется 16384 регистра.

Фильтр Блума

Фильтр Блума — простая, но эффективная структура, позволяющая сказать, есть ли элемент во множестве. Если она говорит, что элемента «нет», значит, его точно нет (отсутствие ложноотрицательных ответов). Но она может сказать и «да» на элемент, которого нет (присутствие ложноположительных элементов).

Это может быть полезно при обучении на потоках данных для отбрасывания повторяющихся элементов.

Алгоритм используется в Redis и во многих других БД, в том числе для ускорения поиска. С его помощью можно сразу определять отсутствие ключа в БД и не обращаться к памяти.

Алгоритм

Инициализация

1. Создаём битовый массив \(M\) длиной \(m\) и заполняем его нулями.
2. Выбираем \(k\) независимых хэш-функций, которые возвращают число от \(0\) до \(m-1\).

Операция добавления элемента x

1. Считаем все хэши \(h_i=hash_i(x)\).
2. Для всех хэшей \(M[h_i]=1\).

Операция проверки на вхождение элемента x

1. Считаем все хэши \(h_i=hash_i(x)\).
2. Если существует \(M[h_i]=0\), значит, элемент точно отсутствует во множестве, в противном случае он, возможно, в нём был.

Операция объединения и пересечения

Для объединения двух фильтров достаточно посчитать побитовое OR — для битовых массивов, а для пересечения — побитовое AND.

Точность алгоритма

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

Тогда \(P(M[i]≠0) =1-\frac{1}{m}\).

Значит, если все хэш-функции независимы — при вставке элемента вероятность отсутствия установки бита в 1 ни одной хэш-функцией равна:

\((1-\frac{1}{m})^k\).

При вставке \(n\) элементов вероятность, что бит останется нулем, равна:

\(P_0=(1-\frac{1}{m})^{kn}\).

Теперь при проверке элемента, которого нет во множестве, вероятность ложноположительного срабатывания равна:

\(p_{false\_positive}=(1-P_0)^k=(1-(1-\frac{1}{m})^{kn})^k\).

Считаем m большим и получаем из формулы с помощью второго замечательного предела:

\(p_{false\_positive}=(1-e^{{kn}/{m}})^k\) — вероятность ложноположительного срабатывания.

Идея алгоритма

Алгоритм переводит множество в битовый вектор с помощью хэширования. При добавлении элементов, соответствующих ему, биты устанавливаются в \(1\).

Если при проверки принадлежности элемента множеству хотя бы один из битов равен \(0\), значит, этот элемент никогда не добавлялся.

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

Подбор параметров

Если ожидаемое количество элементов равно \(n\), а требуемая \(p_{false\_positive} = p\), тогда мы можем посчитать m и k по формулам:

\(m=\frac{nln(p)}{ln^2(2)}\),

\(k=ln(2)\frac{m}{n}\).

Например, если у нас 1000000 объектов, и нужная вероятность равна 1 %, то

\(m=9585058бит≈1.2мегабайт\),

\(k≈7\).

Cuckoo Filter

Этот алгоритм похож на фильтр Блума — он тоже позволяет сказать, есть ли элемент во множестве. При этом, если он говорит, что элемента «нет», значит, его точно нет (отсутствие ложноотрицательных ответов). Но он может сказать и «да» на элемент, которого нет (присутствие ложноположительных элементов). Он поддерживает удаление и быстрее выполняет поиск.

Алгоритм

Инициализация

1. Создаём таблицу \(M\) из \(m\) корзинок (по сути set).
2. Каждый бакет содержит \(b\) слотов для хранения fingerprint (короткий хэш) длиной \(s\) бит.

Операция добавления элемента x

1. Вычисляем fingerprint \(f=fingerprint(x)\).
2. Вычисляем хэш \(h=hash(x)\).
3. Вычисляем первый индекс \(i_1=hash(x)\).
4. Если \(M[i_1]\) имеет свободный слот — добавляем в него fingerprint и заканчиваем процедуру вставки.
5. Вычисляем второй индекс \(i_2 = i_1 ⊕ h(f)\).
6. Если \(M[i_2]\) имеет свободный слот — добавляем в него fingerprint и заканчиваем процедуру вставки.
7. В противном случае запускаем процедуру разрешения коллизии.

Разрешение коллизии

1. Выбираем случайный элемент \(e\) из \(M[i_1]\). Напомним, что \(e\) — это fingerprint.
2. Вставляем на его место \(f\).
3. Считаем \(\hat{i}_2=i_1⊕ h(e)\).
4. Если \(M[\hat{i}_2]\) имеет свободный слот — добавляем, иначе повторяем операцию разрешения коллизий уже для \(e\).

На практике количество попыток разрешения коллизий ограничивается сверху, и при превышении лимита таблица считается заполненной.

Удаление элемента x

Для удаления элемента достаточно посчитать \(i_1\) и \(i_2\) и удалить элемент из одного бакета.

Поиск элемента x

Для поиска элемента мы проверяем, есть ли он в \(M[i_1]\) или \(M[i_2]\). Если да — говорим, что элемент есть во множестве.

Обычно для экономии времени вместо двух хэш-функций (\(fingerprint\) и \(hash\)) берётся одна длинная хэш-функция и разбивается на два куска, один из которых \(fingerprint\), другой — \(hash\).

Идея алгоритма

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

Однако возможны ложные срабатывания: фильтр может сказать, что элемент есть, хотя его не добавляли (когда разные элементы занимают одни слоты).

Cuckoo Filter на русском — «кукушкин фильтр». Название связано с поведением кукушки: она откладывает своё яйцо в чужое гнездо, выбрасывая чужое яйцо. Также и фильтр: если место для нового элемента занято, один из существующих «отпечатков» перемещается в другое место, освобождая место для нового. Правда, природа более жестока, чем алгоритмы: кукушка выбрасывает яйца на землю, а алгоритм «переселяет» элемент, и он не уничтожается.

Точность алгоритма и подбор параметров

Чем больше слотов в бакете, тем меньше мы будем вызывать дорогую операцию разрешения коллизий, но будем использовать больше памяти. Обычно значения b берут от 2 до 4.

Вероятность ложноположительного срабатывания зависит от размера фингерпринта и количества слотов в бакете:

\(p_{false\_positive}\approx2\frac{b}{2^s}\).

Чтобы выбрать количество бакетов, можно воспользоваться формулой: \(m=n*\frac{s}{\alpha}\), где \(n\) — ожидаемое число элементов, а \(\alpha\) — максимальная степень заполненности таблицы. Чем выше \(\alpha\), тем меньше лишней памяти мы будем использовать, но чаще получать коллизии.

Важно отметить: alpha должна быть обязательно меньше 100%. На практике же рекомендуется брать \(\alpha<=90\%\).

Давайте посчитаем размер фильтра при \(n=1000000\) и точнстью \(1\%\). Пусть \(b=4\), \(\alpha=0.9\).

\(s=log_2(2b/p)\approx10\).

\(m\approx277778\).

И умножим число всех слотов на размер слота \((277778*4)*10\approx1.3МБ\).

Сравнение с фильтром Блума

	Фильтр Блума	Cuckoo Filter
Удаление	В базовой версии не поддерживается, а модификация использует больше памяти	Поддерживается
Поиск элемента	Зависит от числа хэш-функций	Всегда считает только 2 хэш-функции, значит, быстрее
Вставка (время)	Зависит от числа хэш-функций	Использует в среднем 2 хэш-функции, но при коллизии сильно замедляется и из-за этого становится непредсказуемым
Процесс заполнения	Увеличивается вероятность ложноположительного срабатывания	С замедленной вставкой может переполниться, но точность постоянная
Слложность реализации	Простая	Сложная

Для большинства задач фильтр Блума подходит лучше из-за того, что он более предсказуемый и простой. Но если вам нужны удаления и низкий FPR — можно попробовать Cuckoo Filter.

Count-Min Sketch

Предположим, нам нужно узнавать, сколько раз элемент множества был добавлен в него. Если данных немного — можно выделить словарь и посчитать в нём. Но если элементов много — это слишком накладно. Алгоритм Count-Min Sketch позволяет аппроксимировать частоты, используя фиксированный объём памяти.

Алгоритм всегда завышает оценку. Его можно использовать, например, в NLP для подсчёта частоты n-грамм, а также в системах ранжирования и рекомендаций.

Алгоритм, как и предыдущие, есть в Redis и в ПО Apache, в BigQuery и ClickHouse.

Алгоритм

Инициализация

1. Создаём матрицу \(M\)счётчиков размером \((d,w)\), инициализированные нулями.
2. Выбираем \(d\) независимых хэш-функций.

Операция добавления элемента x

1. Для каждой строки считаем значение хэш-функции \(j=hash_i(x)\%w\).
2. Для каждой строки инкрементируем счётчик \(M[i][j]\).

Оценка частоты x

1. Для каждой строки считаем j и получаем \(M[i][j]\).
2. Берём минимум по всем полученным значениям.

Мы берём минимум — это уменьшит переоценку, так как хэши могут накладывать чужие элементы из-за коллизий.

Идея алгоритма

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

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

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

Модификация для TOP-K

Алгоритм можно легко модифицировать, чтобы решать задачу TOP-K — поиска \(K\) чаще встречающихся элементов.

Для этого необходимо выделить Min Heap, в котором мы будем хранить максимум \(K\) элементов. Для каждого нового элемента, после добавления в Count-Min Sketch, мы будем оценивать его частоту.

Если куча не заполнена — просто добавляем его. Если куча заполнена, и его частота больше частоты вершины в heap, — удаляем вершину и добавляем новый элемент.

Переоценка

Как мы говорили ранее, алгоритм всегда завышает оценку. Более формально это выглядит так:

\(Error≤\epsilon*N\) с вероятностью \(p≤\sigma\).

Параметры d и w напрямую связаны с \(\epsilon\) и \(\sigma\):

\(w=\frac{e}{\epsilon}\) , где \(e\) — число эйлера,

\(d=ln(\frac{1}{\sigma})\).

Например, при ошибке в 1% с вероятностью 99% нам потребуется использовать \(w=272\), \(d=5\). На это потребуется около 5 килобайт памяти, если хранить счётчики в int32.

Давайте рассмотрим пример, когда нам нужно, чтобы с вероятностью 99% ошибка не превышала 100 для миллиона элементов.

Тогда нам понадобится \(w=27180\) и \(d=5\), что займёт около 500 килобайт.

Заключение

Итак, в статье мы рассмотрели 4 вероятностных алгоритма: HyperLogLog, Bloom Filter, Cuckoo Filter и Count-Min Sketch.

1. HyperLogLog оценивает число уникальных элементов в потоках, используя константное пространство.
2. Bloom Filter позволяет быстро проверять наличие элемента во множестве с небольшой вероятностью ложного срабатывания.
3. Cuckoo Filter расширяет возможности Bloom Filter, поддерживая удаление элементов, но является менее предсказуемым.
4. Count-Min Sketch приблизительно считает частоты элементов множества и позволяет получить TOP-K элементов при простой модификации.

Эти алгоритмы зачастую уже реализованы в базах данных, а также в аналитических и стриминговых платформах. Но если вы хотите попробовать их на python — можно воспользоваться следующими библиотеками.

Библиотека	Алгоритмы
pybloom	Bloom Filter
cuckoopy	Cuckoo Filter
datasketch	HyperLogLog, Count-Min Sketch

И удачи в реализации — делитесь вашими кейсами или вопросами в комментариях! 😊