Ein Online-Algorithmus zum Auffinden der Pareto-Grenzelemente

Ich suche nach einem Online-Algorithmus, der einen Strom von Elementen aufnimmt und die Elemente an der Pareto-Grenze beibehält (z. B. alle nicht dominierten Elemente).

Zum Beispiel. Angesichts der folgenden Eingaben würde sich der beibehaltene Pareto-Grenzsatz wie folgt entwickeln:

• (3,7)
  • Element einfügen b / c es ist das erste Element
  • Pareto-Set enthält jetzt {(3,7)}
• (7,3)
  • Element einfügen b / c es wird im ersten nicht dominiert
  • Pareto-Set enthält jetzt {(3,7), (7,3)}
• (8,4)
  • Element einfügen b / c es ist nicht dominiert; entfernen, (7,3)was es in beiden Dimensionen dominiert
  • Pareto-Set enthält jetzt {(3,7), (8,4)}
• (1,1)
  • Nicht einfügen, da es in beiden Dimensionen dominiert
  • Pareto-Set enthält jetzt {(3,7), (8,4)}
• (9,9)
  • Element einfügen b / c es ist nicht dominiert; Entfernen Sie alle anderen Elemente, da diese in beiden Dimensionen dominieren
  • Pareto-Set enthält jetzt {(9,9)}

In meinem Beispiel verwende ich 2-Tupel, suche aber nach einem Algorithmus, der N-Tupel für "kleine" N verarbeiten kann (z. B. <10).

Die naive Lösung besteht darin, jedes Element mit allen Elementen zu vergleichen, die sich derzeit in der Menge befinden. In der Praxis ist der naive Ansatz möglicherweise nicht so schlecht (z. B. sub$O(n^2)$) weil Elemente regelmäßig vom Vergleichssatz ausgeschlossen werden. Aber ich habe mich gefragt, ob es dafür einen bekannten effizienten Algorithmus gibt. Ich interessiere mich für Effizienz im Speicher und für Rechenkomplexität. (Ha! Und tatsächlich suche ich nach einer Reihe von Algorithmen, die hinsichtlich Speicher und Rechenkomplexität paretooptimal sind.)

Meine derzeitige Anwendung besteht darin, ein Lucene - Suchdokument zu erstellen Collector, das nicht die relevantesten Dokumente sammelt (der typische Anwendungsfall für eine Suchmaschine), sondern die Pareto-optimalen Dokumente entlang bestimmter Dimensionen sammelt.

In zwei Dimensionen kann jedes Update in durchgeführt werden $O(\lg n)$Zeit unter Verwendung einer ausgeglichenen binären Baumdatenstruktur. Aber wenn Sie in einem hochdimensionalen Raum arbeiten, kenne ich keine effiziente Lösung.

Lassen Sie mich einen effizienten Algorithmus für den 2D-Fall beschreiben. Lassen$F$bezeichnen die Menge der Punkte in der Pareto-Grenze. Geschäft$F$ in einem ausgeglichenen Binärbaum mit dem $x$-Koordinate jedes Punktes als Schlüssel. Beachten Sie dies beim Sortieren$F$ durch Erhöhen $x$-Koordinate, sie werden auch durch Verringern sortiert $y$-Koordinate.

Nun ein neuer Punkt gegeben $(x_q,y_q)$können Sie effizient überprüfen, ob es von einem Element von Pareto dominiert wird $F$. Finden Sie das erste Element von$F$ rechts von $(x_q,y_q)$ (dh das Element $(x,y) \in F$ so dass $x \ge x_q$ und $x$ist minimal); dann prüfen, ob es dominiert$(x_q,y_q)$.

Auch einen neuen Punkt gegeben $(x_q,y_q)$können Sie effizient feststellen, ob es ein Element von Pareto dominiert $F$. Insbesondere finden Sie Indizes$i,j$ so dass die Punkte $(x_i,y_i),(x_{i+1},y_{i+1}),\dots,(x_j,y_j)$ von $F$ sind alle Pareto-dominiert von $(x_q,y_q)$ (unter der Annahme, dass die Punkte von $F$ wurden bestellt von $x$-koordinierte, pareto-dominierte Punkte werden in einem aufeinanderfolgenden Intervall sein). Hier ist wie. Finden Sie das erste Element von$F$ auf der linken Seite von $(x_q,y_q)$ (dh das Element $(x_j,y_j) \in F$ so dass $x_j \le x_q$ und $x_j$ ist so groß wie möglich) und prüfen Sie, ob $(x_q,y_q)$dominiert es. Wenn ja, finden Sie den kleinsten Index$i$ so dass $i<j$ (damit $x_i<x_j$) und $y_i \le y_q$. Beide Schritte können in ausgeführt werden$O(\lg n)$Zeit. (Finden$i$ kann in gemacht werden $O(\lg n)$ Zeit, indem der Baum als Verzweigung auf dem Baum behandelt wird $y$-Koordinate von Punkten, und ausnutzen der Tatsache, dass die Punkte von $F$ werden nach abnehmend sortiert $y$-Koordinate.)

Nun sagen wir uns, was wir tun sollen. Wenn$(x_q,y_q)$ wird von einem Punkt von dominiert $F$, dann füge es nicht hinzu $F$;; du bist fertig. Alternativ, wenn$(x_q,y_q)$ Punkte dominieren $i..j$ von $F$, dann müssen Sie diese Punkte aus löschen $F$ und hinzufügen $(x_q,y_q)$ in $F$. Dies kann in erfolgen$O(\lg n)$ Zeit, indem festgestellt wird, dass jedes Intervall aufeinanderfolgender Indizes als Vereinigung von ausgedrückt werden kann $O(\lg n)$ Teilbäume des Binärbaums (grob gesagt arbeiten Sie mit den Geschwistern der Knoten entlang des Pfades von $i$ zur Wurzel, und das gleiche für den Weg von $j$zur Wurzel); Sie können jeden Teilbaum in löschen$O(1)$Zeit. Auf diese Weise können wir eine ganze Reihe aufeinanderfolgender Punkte in löschen$F$ im $O(\lg n)$Zeit, egal wie groß die Reichweite ist. Weitere Informationen finden Sie unter Löschen eines aufeinanderfolgenden Blattbereichs aus einem Binärbaum .

All dies kann in getan werden $O(\lg n)$ Zeit unter Verwendung einer ausgeglichenen binären Baumdatenstruktur.

Dies funktioniert in 2 Dimensionen (dh 2-Tupel). In höheren Dimensionen wird das Problem viel schwieriger. Verweise auf die Literatur mit Techniken für höhere Dimensionen finden Sie unter So finden Sie eine Teilmenge potenziell maximaler Vektoren (von Zahlen) in einer Menge von Vektoren ; Ich befürchte jedoch, dass in hohen Dimensionen alle bekannten Algorithmen wahrscheinlich ziemlich langsam sind (sie haben einen ähnlichen Faktor)$O((\lg n)^{d-1})$ wo $d$ ist die Anzahl der Dimensionen).