Объяснение алгоритма эскиза графа

Ответ 1

Этот потоковый алгоритм создает следующую структуру.

• Найдите рандомизированный алгоритм потоковой передачи, выход которого (как случайная величина) имеет желаемое ожидание, но обычно имеет высокую дисперсию (т.е. шум).

• Чтобы уменьшить дисперсию/шум, параллельно запускайте несколько независимых копий и объедините их выходы.

Обычно 1 более интересен, чем 2. Этот алгоритм 2 действительно несколько нестандартен, но я буду говорить только о 1.

Предположим, что мы обрабатываем ввод

a b c a b a .

С тремя счетчиками нет необходимости в хеше.

a: 3, b: 2, c: 1

Предположим, однако, что мы имеем только один. Существует восемь возможных функций h : {a, b, c} -> {+1, -1}. Вот таблица результатов.

 h  |
abc |  X = counter
----+--------------
+++ | +3 +2 +1 =  6
++- | +3 +2 -1 =  4
+-- | +3 -2 -1 =  0
+-+ | +3 -2 +1 =  2
--+ | -3 -2 +1 = -4
--- | -3 -2 -1 = -6
-+- | -3 +2 -1 = -2
-++ | -3 +2 +1 =  0

Теперь мы можем вычислить ожидания

            (6 + 4 + 0 + 2) - (-4 + -6 + -2 + 0)
E[h(a) X] = ------------------------------------ = 24/8 = 3
                             8

            (6 + 4 + -2 + 0) - (0 + 2 + -4 + -6)
E[h(b) X] = ------------------------------------ = 16/8 = 2
                             8

            (6 + 2 + -4 + 0) - (4 + 0 + -6 + -2)
E[h(c) X] = ------------------------------------ =  8/8 = 1 .
                             8

Что здесь происходит? Для a, скажем, мы можем разложить X = Y + Z, где Y - изменение суммы для a s, а Z - сумма для не a s. По линейности ожидания имеем

E[h(a) X] = E[h(a) Y] + E[h(a) Z] .

E[h(a) Y] представляет собой сумму с термином для каждого вхождения a, то есть h(a)^2 = 1, поэтому E[h(a) Y] - количество вхождений a. Другой член E[h(a) Z] равен нулю; даже при заданном h(a), каждое другое значение хэша одинаково вероятно плюс или минус один, и поэтому вносит нуль в ожидании.

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

abc

+++
+--
-+-
--+

Я оставлю вам новые расчеты.

Ответ 2

Набросок эскиза вероятностная структура данных, которая позволяет ответить на следующий вопрос:

Чтение потока элементов a1, a2, a3, ..., an, где может быть много повторяющихся элементов, в любое время он даст вам ответ на следующий вопрос: сколько элементов ai вы видели до сих пор.

Вы можете четко получить точное значение каждый раз, просто сохраняя хеш, где ваши ключи являются ai, а значения - это количество элементов, которые вы видели до сих пор. Это быстрый O(1) add, O(1) check, и он дает вам точное количество. Единственная проблема, которая занимает пространство O(n), где n - количество различных элементов (помните, что размер каждого элемента имеет большую разницу, потому что он принимает way more space to store this big string as a key, чем просто this.

Итак, как граф эскиз поможет вам? Как и во всех вероятностных структурах данных, вы жертвуете определенностью в пространстве. Графический эскиз позволяет выбрать 2 параметра: точность результатов и эпсилон; и вероятность плохой оценки & delta;.

Для этого вы выбираете семейство пары независимых хэш-функций. Эти сложные слова означают, что они не сталкиваются часто (на самом деле, если оба хэша отображают значения в пространстве [0, m], вероятность столкновения приблизительно равна 1/m^2). Каждая из этих хэш-функций отображает значения в пространство [0, w]. Итак, вы создаете матрицу d * w.

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

Insomniac хорошо объяснил идею (вычисление ожидаемого значения) для эскиза счетчика, поэтому я просто скажу, что с count-min все еще проще. Вы просто вычисляете х хеш значения, которое хотите получить, и возвращаете наименьшее из них. Удивительно, но это обеспечивает высокую точность и гарантию вероятности, которую вы можете найти здесь.

Увеличение диапазона хеш-функций, увеличение точности результатов, увеличение количества хэшей снижает вероятность плохой оценки: & Эпсилон; = e/w и & delta; = 1/e ^ d. Еще одна интересная вещь заключается в том, что значение всегда завышено (если вы нашли значение, оно, скорее всего, больше реального значения, но, конечно, не меньше).