Эффективный (постоянное пространство или сублинейное пространство) способ узнать мощность ((пересекаются B) объединение C) пересекаются D)?

Question

В настоящее время я использую гиперлоглог для оценки количества множеств (число уникальных предметов)

Довольно просто вычислить количество элементов для объединения двух наборов и количество элементов для пересечения двух наборов (|A intersect B| = |A| + |B| - |A union B|)

Но я не смог найти способ объединить операторы объединения и пересечения (примечание: метод позволяет вычислить только количество элементов, а не гиперлоглог пересечения, то есть можнополучить новый гиперлог с помощью A union B, но не A intersect B).

Существуют ли альтернативные алгоритмы, которые могут оценить мощность результата объединения в цепочку и пересечения?

Answer 1

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

|((A n B) u C) n D| =
|(A n B) u C| + |D| - |(A n B) u C u D| =
|(A u C) n (B u C)| + |D| - |(A u C u D) n (B u C u D)| =
|A u C| + |B u C| - |A u B u C| + |D| - |A u C u D| - |B u C u D| + |A u B u C u D|

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