wir stehen derzeit vor einem interessanten Problem. Wir möchten schätzen die Kardinalität eines Satzes ohne die Notwendigkeit, jedes einzelne Element zu speichern (in der Regel Bitmaps/Bitsets sind ein netter Ansatz). Ein sehr netter Algorithmus ist der sogenannte HyperLogLog-Random-Algorithmus (mehr dazu hier http://antirez.com/news/75).Kardinalitätsannäherung für logische Mengenoperationen - (das "HyperLogLog" für AND/OR/XOR)
Das Problem hierbei ist, dass Sie nur Sätze wie UNIONs, es ist so verschmelzen können im Grunde eine OR Kombination.
Eigentlich wollen wir nicht nur Sets mit ODER kombinieren, sondern auch mit AND. Wir wollen diese Operationen sogar kombinieren.
Beispiel: set1 UND (set2 OR set3) OR (set4 UND set5)
Jeder Satz eine Mächtigkeit im Bereich von Millionen hat. Jeder Wert hat eine Größe von 128 Bit.
Jeder Satz kann in irgendeiner Weise, z.B. "HLL, Bloom Filter, eine einfache Liste oder eine Kombination von diesen". Der Algorithmus muss in der kürzestmöglichen Zeit unter Verwendung eines realisierbaren Platzes ausgeführt werden.
Irgendwelche Ideen?
Müssen die Sets nur durch diese Strukturen repräsentiert werden oder können zusätzliche Strukturen verwendet werden? Ich meine, wenn Sie HLLs mit MinHashes mischen, können Sie die Kardinalität von gesetzten Kreuzungen ziemlich einfach abschätzen. –