Фильтры Блума для определения того, какие наборы в семействе являются подмножествами данного набора.

Я пытаюсь использовать фильтр Блума, чтобы определить, какие наборы из семейства наборов A1, A2,..., Am являются подмножествами другого фиксированного набора Q. Я надеюсь, что кто-то может проверить правильность изложенного подхода или предложить какие-либо улучшения.

Пусть Q будет заданным набором целых чисел, содержащим от 1 до 10000 элементов из множества юниверсов U = {1,2,...,10000}.

Кроме того, пусть имеется семейство наборов A1, A2,...,Am, каждое из которых содержит от 1 до 3 элементов из одного набора юниверсов U. Размер m порядка 5000.

схема алгоритма:

Пусть имеется набор k хеш-функций. Для каждого элемента Q применяются хеш-функции и добавляются к набору битов размером n, обозначенному Q_b.

Кроме того, для каждого из наборов Ai, i = 1,...,m примените хеш-функции к каждому элементу Ai, создав набор битов (также размером n), обозначенный Ai_b.

Чтобы проверить, является ли Ai подмножеством Q, выполните логическое И над двумя наборами битов, Q_b & Ai_b, и проверьте, равен ли он набору битов Ai_b. То есть, если Q_b & Ai_b == Ai_b ложно, то мы знаем, что Ai не является подмножеством Q; если это правда, то мы не знаем наверняка (возможность ложного срабатывания) и нам нужно проверить данное Ai с помощью детерминированного подхода.

Мы надеемся, что фильтр сообщит нам о большинстве Ai, которых нет в Q, и мы сможем более тщательно проверить те, которые возвращают true.

Хороший ли это подход для решения моей проблемы?

(Дополнительные вопросы: насколько большим должно быть n? Какие хорошие хэш-функции можно использовать?)


algorithm hash bloom-filter
person jonem    schedule 20.11.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Если диапазон значений довольно мал (как в вашем примере), вы можете использовать простое детерминированное решение с линейной временной сложностью.

  1. Создадим массив was (с индексами от 1 до 10000, то есть по одной ячейке на каждый элемент универсального множества), изначально заполненный false значениями.

  2. Для каждого элемента q из Q мы устанавливаем was[q] = true.

  3. Теперь перебираем все наборы семейства. Для каждого набора A_i мы перебираем все элементы x набора и проверяем, верно ли was[x]. Если это не хотя бы один x, то A_i не является подмножеством Q. В противном случае это так.

Это решение явно правильное, поскольку оно проверяет, является ли одно множество подмножеством другого по определению. Это также довольно просто и детерминировано. Единственный потенциальный недостаток, который у него есть, заключается в том, что он требует вспомогательного массива из 10000 элементов, но он выглядит приемлемым для большинства практических целей (в любом случае фильтр Блума также потребует дополнительного места).

person kraskevich    schedule 20.11.2016
comment
Спасибо за комментарий. Для моей проблемы обычно есть только несколько Ai, которые на самом деле находятся в Q (порядка 10-30), сделает ли это фильтр Блума более желательным или детерминистический подход, который вы описали выше, по-прежнему будет работать лучше? - person jonem; 21.11.2016
comment
@jobnem Если с детерминированным подходом нет проблем, я бы все равно его использовал. У него есть еще одно преимущество: это просто. - person kraskevich; 21.11.2016

arrow_upward
1
arrow_downward

Пожалуйста, постарайтесь задать только один вопрос в своем вопросе.

Я обращусь к первому: «Это хороший подход к моей проблеме?», но не к последним двум: «Насколько большим должно быть n? Какие хорошие хеш-функции можно использовать?»

Вероятно, это не очень хороший подход.

Во-первых, Q крошечный; 10 000 элементов из {1,...,10k} означают, что Q можно хранить с набором битов в 10 КБ или около 1,2 кибибайта. Это очень, очень мало. Например, он меньше вашего вопроса, в котором используется почти 1,5 кибибайта.

Во-вторых, Ai содержит от одного до трех элементов, поэтому Ai_b, скорее всего, будет больше, чем Ai, если только вы не выбрали их настолько маленькими, что вероятность ложных срабатываний очень высока.

Наконец, вычисление хэш-функции не является бесплатным.

Вы можете сделать это намного проще, если вы проверите каждый элемент каждого Ai по набору битов, представляющему Q.

person jbapple    schedule 20.11.2016