Аппроксимация количества элементов для операций логического множества - ("HyperLogLog" для AND/OR/XOR)

Question

В настоящее время мы сталкиваемся с интересной проблемой. Мы хотели бы оценить мощность набора без необходимости хранить каждый отдельный элемент (как правило, битовые карты / битовые наборы - хороший подход). Очень хорошим алгоритмом является так называемый рандомизированный алгоритм HyperLogLog (подробнее здесь http://antirez.com/news/75).

Проблема здесь в том, что вы можете объединять наборы как UNION, так что в основном это комбинация ИЛИ.

На самом деле мы хотим не только комбинировать множества с OR, но также и с AND. Мы даже хотим объединить эти операции.

Пример: набор1 И (набор2 ИЛИ набор3) ИЛИ (набор4 И набор5)

Каждый набор может иметь мощность в диапазоне миллионов. Каждое значение имеет размер 128 бит.

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

Есть идеи?

Answer 1

Эта проблема является предметом https://pdfs.semanticscholar.org/5da8/bf81712187712aed159aed62e38fb012872e.pdf. Их рекомендуется использовать фильтры Блума.

Фильтр Блума для объединения - это побитовое ИЛИ фильтров Блума. Фильтр Блума для пересечения является побитовым И фильтров Блума. Таким образом, вы можете легко сгенерировать фильтр Блума той операции, которую вы хотите.

Их теорема 1 позволяет оценить размер набора по тому, сколько битов установлено в его фильтре Блума.