Count sketch

Пусть у нас есть поток данных (stream) $s_1, s_2, s_3, \dotsc, s_i, \dotsc$ , при этом все данные — элементы какого-то универсума $\UUU$ . Мы хотим уметь считать, сколько раз элемент $x$ встретился в этом потоке к моменту времени $t$ , то есть уметь считать значение функции

f_t(x) = \sum\limits_{i=1}^t \indic(s_i = x)

Будем решать задачу для фиксированной временной границы $t$ .

Задача подсчета

Дан поток данных $S = s_1, s_2, s_3, \dotsc, s_{n-1}, s_n$ . Можно считать, что мы сделали временной срез при $t = n$ .

Нам нужно оценивать количество вхождений элемента $x$ в этот поток $S$ — значение функции $f(x)$ .

f(x) = \sum\limits_{i=1}^n \indic(s_i = x)

Но ответы на запросы лояльные. Мы даем ответ с точностью $\varepsilon$ , при этом позволяем себе ошибаться с вероятностью $\delta$ . Формально, $\prob \big( \hat f (x) \le f(x) + \varepsilon n \big) \ge 1 - \delta$ , где $\hat f (x)$ — предсказанное нами количество вхождений.

А ещё нам нужно уметь обновлять поток — добавлять и удалять элементы.

Count-Min sketch

Для решения задачи подсчета можно использовать структуру данных Count-Min sketch. Она применима только тогда, когда в поток элементы только добавляются.

Будем использовать хеширование.

Пусть $d = \lceil \ln 1/\delta \rceil$ — глубина aka количество хеш-функций, и $w = \lceil e/\varepsilon \rceil$ — размер хеш-пространства. Счётчики будем хранить в двумерном массиве $c \in \NN_0^{d \times w}$ высоты $d$ и ширины $w$ . Изначально массив $c$ проинициализирован нулями.

Создадим еще $d$ независимых хеш-функций $h_1, h_2, \dotsc, h_d \colon \UUU \surjto \{1, 2, \dotsb, w\}$ .

const real delta = 0.01
const real epsilon = 0.01

const int w = ceil(e / epsilon)
const int d = ceil(ln(1 / delta))

const array h[d]

array[int] c[d][w]

Обновление

При получении запроса на добавления в «счётчик» элемента $x$ мы для каждой строки $i$ массива $c$ увеличиваем значение соответствующего счётчика $h_i(x)$ на $1$ .

function add(self, element):
    for i = 0; i < d; i++:
        column = h[i](element)
        c[i][column] += 1

Оценка

Для получения оценки количества вхождений элемента $x$ в поток данных нам надо посчитать минимум по всем счётчикам, включающим в себя этот элемент:

\hat f (x) = \min\limits_{1 \;\! \le \;\! i \le d} c[i][h_i(i)]

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

Доказательство того, что структура работает, и работает хорошо.

Начнем с доказательства завышенности оценок. Для любой строки $i$ и любого элемента $x$

c[i][h_i(x)] = f(x) + \sum\limits_{\substack{y \;\! \neq \;\! x \\ h_i(y) = h_i(x)}} f(y) \ge f(x)

Хеш-функции $h_i$ «хорошие», то есть они свои входы равномерно распределяют по выходам.

Рассмотрим произвольную строку $i$ . Ошибка оценки $\Delta_i$ выражается как

\Delta_i = c[i][h_i(x)] - f(x) = \sum\limits_{\substack{y \;\! \neq \;\! x \\ h_i(y) = h_i(x)}} f(y)

Тогда математическое ожидание ошибки оценки

\expect \Delta_i = \sum\limits_{y \;\! \neq \;\! x} f(y) \cdot \prob \big( h_i(y) \neq h_i(x) \big) = \frac{n - f(x)}{w} \;\! \le \;\! \frac{n}{w}

Применим неравенство Маркова

\prob(\Delta_i \ge a) \le \frac{\expect \Delta_i}{a} \le \frac{n}{wa}

Выберем $a = \varepsilon n$ , тогда мы сможем получить оценку

\prob(\Delta_i \ge \varepsilon n) \le \frac{1}{w \varepsilon} \le \frac{1}{e}

Но это только для одной строки. А при получении оценки мы выбираем минимум, значит, общая ошибка превысит $\varepsilon n$ , только тогда, когда переоценку дадут все $d$ строк.

\prob \Bigg( \bigunion_{i=1}^d \{ \Delta_i \;\! \ge \;\! \varepsilon n \} \Bigg) \;\! \le \;\! \left( \frac{1}{e} \right)^d

Учитывая, что $(1/e)^d \le e^{-\ln 1/\delta} = \delta$ , получаем оценку

\prob (\hat f (x) > f(x) + \varepsilon n ) \le \delta