Schneller Approximationsalgorithmus für die Kardinalität von Schnittmengen

Question

Ich habe einen Pool setzt (mit der Größe von Pool n), mit allen Sets nicht in den RAM passen. Ich kann nur einen kleinen Bruchteil, sagen wir 1-5% aller Sätze in RAM.

Das Problem ist gegeben Abfrage gesetzt Q Ich muß mit dem größten Mächtigkeit von intersect Top-k-Sätze zurück mit Q.

1. Unter der Annahme, Q in aus dem gleichen Pool von Sätzen.
2. Für allgemeine Q.

k klein ist, in Hunderten, während n in Hunderten von Millionen. Gesamtzahl der Bezirkselemente in allen Sätzen auch in Hunderten von Millionen.

• Es gibt viele probabilistische Datenstrukturen, KMV, MinHash und es ist Varianten, die man soll ich verwenden?
• Kann ich HyperLogLog für meine Aufgabe ändern?
• Welche dieser Strukturen können zu einer Art Index zusammengefügt werden?

Ich habe einige Experimente durchgeführt, die Sets als Bloom-Filter darstellen. Da die Größe der Sets sehr unterschiedlich ist, muss ich sehr große bloomfilters verwenden, was ineffizient ist (bloomfiltes benötigt 5x Speicherplatz des ursprünglichen Datasets). Adaptive bloomfiters von https://github.com/jaybaird/python-bloomfilter erzeugen nur 3-5x Kompression des Datensatzes, so dass dies immer noch ziemlich undurchführbar ist.

Answer 1

Eigentlich habe ich die Lösung gefunden. Durch Multiplizieren von Hyperloglog und Minhash und Minhashern erzeugter Schnittpunkt könnte effizient mit LSH gespeichert werden.Mehr Details hier: http://infolab.stanford.edu/%7Eullman/mmds/ch3.pdf

Answer 2

K-Minimum Values Datenstruktur ist extrem speichereffizient. Im Gegensatz zu Bloom-Filtern bietet es keinen Mitgliedschaftstest, nur mengentheoretische Operationen und eine Kardinalitätsschätzung.

Könnte für Sie arbeiten, abhängig von den Kardinalitäten Ihrer Sets und Ihrer Fehlertoleranz.

Answer 3

Wenn Sie die Abfrage Q im Speicher als Hash-Tabelle speichern, müssen nicht alle anderen Sätze gleichzeitig im Speicher gehalten werden. Sie können die Kreuzungskardinalitäten für jedes Set nacheinander berechnen. Laden Sie einfach einen Satz in den Speicher, berechnen Sie die Kardinalität seines Schnittpunkts mit Q und entfernen Sie ihn schließlich wieder aus dem Speicher.

Answer 4

Speichern Sie alle Sätze zusammen in einem Bloom Filter mit Schlüsseln der Form (setId, value). Dies muss in der Lage sein, einen Satz der Größe der Vereinigung aller Ihrer Sätze zu handhaben, was Sie davon abhält, kleine Sätze in Bloomfiltern zu speichern, die für sehr große ausgewählt sind.

Zweitens könnten Sie für Ihren Zweck sehr große Fehlerraten akzeptieren, wodurch der Bloomfilter wieder schrumpft. Ein Bloom-Filter mit einer Fehlerrate von 1% benötigt 9.58505837736744 ... Bits pro Element. Ein Bloom-Filter mit einer Fehlerrate von 10% benötigt 4.79252918868372 Bits pro Element. Wenn Sie jedoch eine Fehlerrate von 10% haben, können Sie bei einem Satz mit 400 Elementen nach Korrektur auf erwartete Fehlalarme innerhalb von 3% der richtigen Antwort eine Antwort erhalten, die 95% der Zeit beträgt. Das kann akzeptabel sein, um die Filtergröße um den Faktor 2 zu reduzieren. (Je größer Q ist, desto kleiner ist der relative Fehler.)

Wenn zwischen diesen beiden Techniken ein Bloom-Filter immer noch viel zu groß ist, dann sollten Sie vielleicht Ihre Daten auf mehreren Rechnern suchen in der Verteilung von ...