Понимание структуры данных Count Sketch и связанных алгоритмов

Question

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

Бумага немного трудна для понимания для человека, который какое-то время был в стороне от более академических подходов, и предыдущий пост здесь действительно помог некоторым, по крайней мере для меня осталось еще немало вопросов.

Насколько я понимаю, структура Count Sketch похожа на фильтр Блума. Однако выбор хеш-функций меня смутил. Структура представляет собой таблицу N by M с N хэш-функциями, где M возможных значений определяет «корзину» для изменения, и еще одну хэш-функцию s для каждого N, которая «попарно независима»

Хэши должны быть выбраны из универсального семейства хэширования, скажем, что-то из h (x) = ((ax + b)% some_prime)% M?

И если да, то откуда хэши, которые возвращают +1 или -1, выбраны из? И какова причина того, чтобы вычитать одно из ведер?

Answer 1

Они вычитают из сегментов, чтобы сделать средний эффект сложений / вычитаний, вызванных другими вхождениями, равным 0. Если половину времени я добавляю счетчиком 'foo', а половину времени я вычитаю счет 'foo'затем, в ожидании, счет «foo» не влияет на оценку количества «бар».

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