Effizient Manipulieren Subsets von RDD der Schlüssel in Funken

Question

Ich habe eine RDD von (Schlüssel, Wert) Paare der Form

RDD[(
    scala.collection.immutable.Vector[(Byte, Byte)], 
    scala.collection.immutable.Vector[Int] 
)] 

wo key ist ein Vector[(Byte, Byte)] und valueVector[Int] ist.

Zum Beispiel kann der Inhalt der RDD wie folgt aussehen.

(Vector((3,3), (5,5)), Vector(1, 2)), 
(Vector((1,1), (2,2), (3,3),(4,4), (5,5)), Vector(1, 3, 4, 2)), 
(Vector((1,1), (2,3)), Vector(1, 4, 2)), 
(Vector((1,1), (2,2), (5,5)), Vector(3, 5)), 

Ich mag eine Manipulation an der RDD so daß in der resultierenden RDD tun, für jeden (Schlüssel, Wert) -Paare die folgende Bedingung erfüllt ist.

Wenn ein Schlüssel 'k1' dieser RDD eine Teilmenge des Schlüssels 'k2' dieser RDD ist, sollten die Werte von k1 so aktualisiert werden, dass sie auch k2-Werte enthalten, während die Werte von k2 gleich bleiben.

Das obige Beispiel RDD wird geworden,

(Vector((3,3), (5,5)), Vector(1, 2, 3, 4)), 
(Vector((1,1), (2,2), (3,3), (4,4), (5,5)), Vector(1, 3, 4, 2)) 
(Vector((1,1), (2,3)), Vector(1, 4, 2)) 
(Vector((1,1), (2,2), (5,5)), Vector(1, 2, 3, 4, 5)) 

Ich habe eine ähnliche Frage here gefragt. Die gelieferte Lösung ist unten angegeben (leicht modifiziert für mein Problem). Dies funktioniert bei großen Datenmengen sehr ineffizient.

val resultPre = rddIn 
    .flatMap { case (colMapkeys, rowIds) => 
    colMapkeys.subsets.tail.map(_ -> rowIds) 
    } 
    .reduceByKey(_ ++ _) 
    .join(rddIn map identity[(Seq[(Byte, Byte)], Vector[Int])]) 
    .map{ case (key, (v, _)) => (key, v) } 


implicit class SubSetsOps[T](val elems: Seq[T]) extends AnyVal { 
    def subsets: Vector[Seq[T]] = elems match { 
    case Seq() => Vector(elems) 
    case elem +: rest => { 
     val recur = rest.subsets 
     recur ++ recur.map(elem +: _) 
    } 
    } 
} 

alle Untergruppen der Schlüssel generieren und Filtern sie dann durch mit original RDD Tasten verbinden scheint wirkungslos zu sein.

Wie gehe ich effizient damit um?

Answer 1

Ich denke, Ihr Problem ist grundsätzlich schwer. Sie haben grundsätzlich zwei Möglichkeiten, dies zu tun:

1. alle Teilmenge Schlüssel generieren, die Wertelisten zusammenführen und die fina Liste für jede gegebene Teilmenge sammeln, dann kommen nur an bestehende Untergruppen. (Das ist was du machst).

2. Vergleichen Sie jeden Eintrag mit jedem anderen Eintrag, sehen Sie, ob ein Schlüssel eine Teilmenge des anderen ist, und führen Sie dann alle auf diese Weise erzeugten Teilmengen nach Schlüssel zusammen. Dies erzeugt keine falschen Schlüsselzwischenpermutationen.

Welches effizienter ist von der Art der Daten (Größe der Schlüssel Vektoren, Anzahl, wie oft sie Untergruppen voneinander sind, usw.) abhängt.

Die anderen Optimierungen, die Sie versuchen könnten, sind die Daten einfacher zu handhaben. Zum Beispiel könnten Sie Ihre inneren Koordinaten sicher zu Integer (sie sind nur Bytes) zuordnen. Sage (5,5) bis 5 * 1000 + 5 = 5005. Da der Ganzzahlvergleich einfacher und schneller ist als der Vergleich von Tupeln.

Abhängig davon, wie viel Sie die Domäne der Schlüssel verstehen. Wenn dieser Platz klein genug ist, könnten Sie versuchen, Ihre Schlüssel als Bitmaps oder ähnliches darzustellen. Diese Änderungen werden die Anzahl der Schlüssel, die Sie haben, nicht grundlegend ändern, aber Vergleiche und andere Operationen werden dadurch viel einfacher.