Вычисление приблизительной популяции фильтра Блума

Question

С учетом фильтра Блума с размером N-битов и K хэш-функций, из которых установлены M-биты (где M <= N) фильтра. </p>

Можно ли приблизить количество элементоввставлен в фильтр Блума?

Простой пример

Я обдумывал следующий пример, предполагая, что BF состоит из 100 битов и 5 хеш-функций, где 10-биты установлены ...

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

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

Диапазон, по-видимому, равен [2,10], где значение about в этом диапазоне, вероятно, определяется ложноположительной вероятностью фильтра - я застрял в этой точке.

Answer 1

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

Тем не менее, если мы должны использовать фильтр Блума,давайте предположим, что хеш-функции являются случайными оракулами (все значения выбираются независимо или «действительно идеально», не путать с идеальным хешированием).Теперь у нас есть проблема с шарами и мусорными ведрами: учитывая, что в M из N мусорных ведрах есть шары, сколько шариков мы бросили?Пусть B будет количеством брошенных шаров;количество элементов равно B/K, так как для каждого элемента мы бросаем K шаров.

Стандартное приближение для процессов шаров и бинов состоит в том, чтобы моделировать каждый бин как независимый процесс Пуассона;время до того, как корзина становится занятой, распределяется по экспоненте.Если 1 будет временем, необходимым для броска всех шаров, то оценка максимального правдоподобия λ скорости этого экспоненциального распределения удовлетворяет Pr(Exponential[λ] < 1) = M/N, поэтому 1 - exp(-λ) = M/N и λ = -log(1 - M/N).Параметр λ сродни количеству шаров, поэтому оценка количества предметов составляет B ≈ -N log(1 - M/N)/K.

EDIT: есть N корзин, поэтому нам нужно умножить на N.

Answer 2

Запись в Википедии дает формулу для вероятности любого конкретного устанавливаемого бита, предполагая, что хэш-функции делают все случайным.Это 1 - (1-1/m)^kn.Поскольку в фильтре имеется m битов, это означает, что ожидаемое / среднее число установленных битов будет m(1-(1-1/m)^kn).Таким образом, вы могли бы придумать достаточно правдоподобное предположение для n, выбрав n, которое делает его равным фактически установленному количеству бит.было бы неплохо иметь представление о дисперсии числа установленных битов.Вы можете решить это точно, но это что-то вроде боли в шее.Вы можете использовать тот факт, что Var(X) = E(X^2) - E(X)^2.В этом случае E(X^2) зависит, главным образом, от вероятности того, что обе пары бит будут установлены, и вы можете решить эту проблему, рассматривая вероятность операторов типа «бит 0 установлен и бит 1 сброшен, и всеостальные биты очищены ", а" бит 0 очищен "и" все биты, кроме 0 и 1, очищены ".