Ich stehe vor einem Problem, bei dem ich die Schnittmengen zwischen allen Paaren in einer Sammlung von Mengen berechnen muss. Keine der Mengen ist kleiner als eine kleine Konstante k und ich interessiere mich nur dafür, ob zwei Mengen eine Schnittmenge haben, die größer ist als k -1 Elemente oder nicht. Ich benötige weder die tatsächlichen Schnittpunkte noch die genaue Größe, sólo ob sie größer ist als k -1 oder nicht. Gibt es einen cleveren Trick für die Vorverarbeitung oder einen sauberen Algorithmus für die Mengenüberschneidung, den ich verwenden könnte, um die Dinge zu beschleunigen?
Weitere Informationen, die für die Beantwortung der Frage nützlich sein können:
- Die Mengen stellen maximale Cliquen in einem großen, ungerichteten, spärlichen Graphen dar. Die Anzahl der Gruppen kann in der Größenordnung von Zehntausenden oder mehr liegen, aber die meisten Gruppen sind wahrscheinlich klein.
- El
Sets sind bereits sortiertDie Mitglieder jeder Gruppe sind in aufsteigender Reihenfolge. Im Grunde handelt es sich um sortierte Listen - ich erhalte sie auf diese Weise von einer zugrunde liegenden Bibliothek für die maximale Cliquensuche. - Es ist nichts über die Verteilung der Elemente in den Mengen bekannt (d. h. ob sie in engen Klumpen vorliegen oder nicht).
- Die meisten der Mengenschnittpunkte werden wahrscheinlich leer sein, so dass die ideale Lösung eine clevere Datenstruktur wäre, die mir hilft, die Anzahl der Mengenschnittpunkte, die ich machen muss, zu reduzieren.
