2025-11-11T16:25:09.674123

Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge

Joshi

We present a merge-free algorithm for multi-way co-ranking, the problem of computing cut indices $i_1,\dots,i_m$ that partition each of the $m$ sorted sequences such that all prefix segments together contain exactly $K$ elements. Our method extends two-list co-ranking to arbitrary $m$, maintaining per-sequence bounds that converge to a consistent global frontier without performing any multi-way merge or value-space search. Rather, we apply binary search to \emph{index-space}. The algorithm runs in $O(\log(\sum_t n_t)\,\log m)$ time and $O(m)$ space, independent of $K$. We prove correctness via an exchange argument and discuss applications to distributed fractional knapsack, parallel merge partitioning, and multi-stream joins. Keywords: Co-ranking \sep partitioning \sep Merge-free algorithms \sep Index-space optimization \sep Selection and merging \sep Data structures

academic

Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge

Grundinformationen

Paper-ID: 2510.22882
Titel: Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge
Autor: Amit Joshi (Independent Researcher)
Klassifizierung: cs.DS (Datenstrukturen und Algorithmen)
Veröffentlichungsdatum: 27. Oktober 2025 (arXiv Preprint)
Paper-Link: https://arxiv.org/abs/2510.22882

Zusammenfassung

In diesem Papier wird ein Merge-freier Multi-Way-Co-Ranking-Algorithmus vorgestellt, um Schnittindizes $i_1,\dots,i_m$ zu berechnen, die $m$ sortierte Sequenzen so partitionieren, dass alle Präfixsegmente zusammen genau $K$ Elemente enthalten. Das Verfahren erweitert die Zwei-Listen-Co-Ranking-Methode von Siebert und Träff auf beliebige $m$ -Wege, erhält die Grenzen jeder Sequenz und konvergiert zu einer konsistenten globalen Front, ohne Multi-Way-Merge oder Werteraum-Suche durchzuführen. Der Algorithmus wendet binäre Suche im Indexraum an und erreicht eine Zeitkomplexität von $O(\log(\sum_t n_t)\log m)$ und Raumkomplexität von $O(m)$ , unabhängig von $K$ . Die Korrektheit wird durch Austauschargumente bewiesen und Anwendungen in verteiltem Fractional Knapsack, parallelem Merge-Partitioning und Multi-Stream-Joins werden diskutiert.

Forschungshintergrund und Motivation

Problemdefinition

Das Multi-Way-Co-Ranking-Problem ist wie folgt definiert: Gegeben sind $m$ in nicht-absteigender Reihenfolge sortierte Sequenzen $L_1, \ldots, L_m$ (mit Wiederholungen erlaubt), jeweils mit Länge $n_t$ , und ein globales Zielranking $K \in \{0, \ldots, N\}$ (wobei $N = \sum_t n_t$ ), müssen Schnittindizes $i_1, \ldots, i_m$ gefunden werden, so dass:

$\sum_{t=1}^m i_t = K \quad \text{und} \quad \max_t \ell_t \leq \min_t r_t$

wobei $\ell_t$ und $r_t$ jeweils die linken und rechten Grenzwerte darstellen.

Forschungsmotivation

Erweiterung klassischer Algorithmen: Bestehende Co-Ranking-Algorithmen konzentrieren sich hauptsächlich auf zwei Sequenzen und ermangeln effizienter Multi-Way-Erweiterungen
Vermeidung von Merge-Overhead: Traditionelle Methoden erfordern zunächst das Zusammenführen mehrerer Sequenzen vor der Auswahl, was erhebliche Kosten verursacht
Vorteile des Indexraums: Operationen im Indexraum statt im Werteraum vermeiden die Komplexität der Wertebereichssuche
Praktische Anforderungen: Verteilte Datenverarbeitung, parallele Verarbeitung und Datenbankabfragen erfordern effiziente Multi-Way-Partitionierungsalgorithmen

Einschränkungen bestehender Methoden

Siebert-Träff-Methode: Unterstützt nur Co-Ranking für zwei Sequenzen
Frederickson-Johnson-Methode: Operiert im Werteraum und erfordert globale Zähloperationen
Splitter-basierte Methoden: Erfordern vorheriges Zusammenführen oder Wertebereichssuche mit höherer Komplexität

Kernbeiträge

Algorithmusdesign: Vorstellung des ersten Merge-freien Multi-Way-Co-Ranking-Algorithmus, der die klassische Zwei-Wege-Methode auf beliebige $m$ -Wege erweitert
Theoretische Analyse: Beweis der Korrektheit des Algorithmus und der Zeitkomplexität $O(\log(\sum_t n_t)\log m)$
Datenstruktur-Innovation: Design von adressierbaren Heaps zur effizienten Wartung von Grenzwerten
Anwendungserweiterung: Demonstration des Algorithmuspotenzials in verteilter Optimierung, paralleler Verarbeitung und Datenbanksystemen

Methodische Details

Aufgabendefinition

Eingabe:

$m$ sortierte Sequenzen $L_1, \ldots, L_m$ mit Längen $n_1, \ldots, n_m$
Zielranking $K \in [0, N]$ , wobei $N = \sum_{t=1}^m n_t$

Ausgabe:

Schnittindex-Vektor $(i_1, \ldots, i_m)$ , der die Co-Ranking-Bedingungen erfüllt

Nebenbedingungen:

$\sum_{t=1}^m i_t = K$
$\max_t \ell_t \leq \min_t r_t$ (Co-Ranking-Bedingung)

Algorithmus-Architektur

Zentrale Datenstruktur: Index-Heap

Der Algorithmus verwaltet zwei Index-Heaps:

$H_L$ : Max-Heap, speichert Grenzwerte der linken Seite $(\ell_t, t)$ , gibt die Sequenz mit dem größten linken Grenzwert zurück (Spender)
$H_R$ : Min-Heap, speichert Grenzwerte der rechten Seite $(r_t, t)$ , gibt die Sequenz mit dem kleinsten rechten Grenzwert zurück (Empfänger)

Jeder Heap unterstützt update_key-Operationen in $O(\log m)$ und peek-Operationen in $O(1)$ .

Grenzwert-Verwaltung

Für jede Sequenz $t$ werden folgende Werte verwaltet:

Untere Grenze: $Lb[t] \leq i[t]$
Obere Grenze: $i[t] \leq Ub[t]$
Aktueller Index: $i[t]$

Iterationsstrategie

Der Algorithmus verwendet eine Spender-Empfänger-Greedy-Strategie:

Identifikation von Extremwerten:
- Spender $p = \arg\max_t \ell_t$ (größter linker Grenzwert)
- Empfänger $q = \arg\min_t r_t$ (kleinster rechter Grenzwert)

Berechnung der Transfermenge:

donor_slack = ⌈(i[p] - Lb[p])/2⌉
receiver_slack = ⌈(Ub[q] - i[q])/2⌉
Δ = min{donor_slack, receiver_slack}

Durchführung des Transfers:
- $i[p] \leftarrow i[p] - \Delta$
- $i[q] \leftarrow i[q] + \Delta$
- Grenzen aktualisieren: $Ub[p] \leftarrow i[p]$ , $Lb[q] \leftarrow i[q]$
Heap-Aktualisierung: Aktualisierung der Heap-Schlüsselwerte betroffener Sequenzen

Technische Innovationen

Indexraum-Operationen: Vollständige Arbeit im Indexraum, vermeidung von Wertebereichssuche und Merge-Operationen
Geometrische Konvergenz: Durch Halbierung des zulässigen Bereichs wird logarithmische Konvergenzgeschwindigkeit garantiert
Unausgeglichene Potentialfunktion: Definition von $\Phi(i) = \max_t \ell_t - \min_t r_t$ als Konvergenzkriterium
Deterministische Komplexität: Algorithmuskomplexität ist unabhängig vom Zielranking $K$

Theoretische Analyse

Korrektheitsbeweis

Lemma 1 (Optimalität lokaler Extremwerte)

Wenn $\Phi(i) > 0$ , seien $p = \arg\max_t \ell_t$ und $q = \arg\min_t r_t$ . Unter allen zulässigen infinitesimalen Transfers, die $\sum_t i_t = K$ beibehalten, realisiert das Paar $(p,q)$ die maximale nicht-steigende Änderung von $\Phi$ .

Beweisskizze: Die Verringerung von $i_p$ senkt $\ell_p$ (das lokale Maximum der linken Grenze), während die Erhöhung von $i_q$ $r_q$ erhöht (das lokale Minimum der rechten Grenze). Da $\ell_p \geq \ell_u$ und $r_q \leq r_v$ für alle $u,v$ gelten, erzeugt das Extremwertpaar $(p,q)$ die steilste Verringerung der Lücke $\max\ell - \min r$ .

Lemma 2 (Austauschbarkeit von Transferreihenfolgen)

Jede Folge von zulässigen Transfers, die $\Phi$ verringern, kann so umgeordnet werden, dass alle Extremwert- $(p,q)$ -Transfers vor allen Nicht-Extremwert-Transfers auftreten, ohne dass sich $\Phi$ in Zwischenschritten verschlechtert.

Theorem 1 (Konvergenz und Gültigkeit)

Algorithmus 2 terminiert mit einem gültigen Co-Ranking-Vektor $(i_1, \ldots, i_m)$ , der $\sum_t i_t = K$ und $\max_t \ell_t \leq \min_t r_t$ erfüllt.

Komplexitätsanalyse

Rundenanalyse

In jeder Runde wird der zulässige Abstand des Spenders oder Empfängers halbiert. Der Abstand $Ub[t] - Lb[t]$ jeder Sequenz wird höchstens $O(\log n_t)$ -mal verringert. Aggregiert über alle $m$ Sequenzen beträgt die Gesamtzahl der Runden:

$T = O\left(\log\left(\sum_{t=1}^m n_t\right)\right)$

Zeitkomplexität

Jede Runde führt eine konstante Anzahl von Index-Heap-Operationen durch ( $O(\log m)$ Zeit), daher beträgt die Gesamtzeitkomplexität:

$O\left(\log\left(\sum_t n_t\right) \cdot \log m\right)$

Raumkomplexität

Der Algorithmus benötigt nur Speicher für Indizes und Grenzinformationen der $m$ Sequenzen, daher beträgt die Raumkomplexität $O(m)$ .

Algorithmus-Implementierung

Kern-Algorithmus-Ablauf

def multi_way_corank(sequences, K):
    m = len(sequences)
    # Initialisierung von Grenzen und Indizes
    Lb = [0] * m
    Ub = [len(seq) for seq in sequences]
    i = water_fill_initialization(K, Ub)
    
    # Konstruktion von Index-Heaps
    HL = MaxHeap()  # Max-Heap für linke Grenzen
    HR = MinHeap()  # Min-Heap für rechte Grenzen
    
    for t in range(m):
        HL.insert(t, left_boundary(sequences[t], i[t]))
        HR.insert(t, right_boundary(sequences[t], i[t]))
    
    while True:
        # Spender und Empfänger abrufen
        max_left, p = HL.peek()
        min_right, q = HR.peek()
        
        # Terminierungsbedingung prüfen
        if max_left <= min_right:
            break
            
        # Transfermenge berechnen
        donor_slack = ceil((i[p] - Lb[p]) / 2)
        receiver_slack = ceil((Ub[q] - i[q]) / 2)
        delta = min(donor_slack, receiver_slack)
        
        # Transfer durchführen
        i[p] -= delta
        i[q] += delta
        
        # Grenzen aktualisieren
        Ub[p] = i[p]
        Lb[q] = i[q]
        
        # Heaps aktualisieren
        update_heaps(HL, HR, sequences, i, p, q)
    
    return i

Initialisierungsstrategie

Verwendung einer "Wasserfüll"-Strategie zur Initialisierung einer zulässigen Lösung:

def water_fill_initialization(K, capacities):
    i = [0] * len(capacities)
    need = K
    for t in range(len(capacities)):
        take = min(capacities[t], need)
        i[t] = take
        need -= take
        if need == 0:
            break
    return i

Anwendungsszenarien

1. Verteiltes Fractional-Knapsack-Problem

Bei Multi-Source-Fractional-Knapsack-Problemen, wenn Gegenstände nach Dichte sortiert über $m$ Shards verteilt sind, kann Co-Ranking verwendet werden, um die globale $K$ -Präfix-Partitionierung zu berechnen, ohne Quelldaten zusammenzuführen.

2. Paralleles $m$ -Wege-Merge-Partitioning

Zur Zuweisung disjunkter Präfixe an Prozessoren, ohne vorbereitendes Merge durchzuführen. Der Co-Ranking-Vektor bestimmt genaue Übergangspunkte, und Prozessoren führen dann nur lokales Merge für ihre Bereiche durch.

3. Multi-Stream-Join-Partitionierung

In Datenbank- oder Stream-Processing-Pipelines ist die Partitionierung der Join-Front beim globalen Ranking eine natürliche Anforderung. Diese Methode erzeugt Pro-Stream-Cursor, die mit der globalen Präfix konsistent sind.

Experimentelle Verifikation

Obwohl sich das Papier hauptsächlich auf theoretische Analyse konzentriert, stellt der Autor Implementierungscode zur Verifikation bereit. Die praktische Leistung des Algorithmus kann durch folgende Aspekte bewertet werden:

Theoretische Leistungsgarantien

Zeitkomplexität: $O(\log(\sum_t n_t) \log m)$
Raumkomplexität: $O(m)$
Unabhängigkeit: Komplexität ist unabhängig vom Zielranking $K$

Vergleich mit bestehenden Methoden

Gegenüber Merge-Methoden: Vermeidung von $O(N)$ Merge-Overhead
Gegenüber Werteraum-Methoden: Vermeidung globaler Zähloperationen
Gegenüber Frederickson-Johnson: Indexraum-Operationen sind effizienter

Schlussfolgerung und Diskussion

Hauptschlussfolgerungen

Erfolgreiche Erweiterung des Zwei-Wege-Co-Ranking auf Multi-Way-Fall unter Beibehaltung guter theoretischer Eigenschaften
Indexraum-Operationen vermeiden Wertebereichssuche und bieten deterministische Komplexitätsgarantien
Algorithmus ist einfach zu implementieren und hat gute praktische Anwendbarkeit

Einschränkungen

Annahmen: Erfordert, dass Eingabesequenzen bereits sortiert sind
Anwendungsbereich: Hauptsächlich für Szenarien geeignet, die genaue Partitionierung erfordern
Experimentelle Verifikation: Mangel an großflächiger experimenteller Verifikation der Leistung

Zukünftige Richtungen

Dynamische Sequenzen: Erweiterung zur Unterstützung dynamischer Sequenzaktualisierungen
Approximationsalgorithmen: Entwicklung schnellerer Approximationsversionen
Parallelisierung: Untersuchung von Parallelisierungsmöglichkeiten des Algorithmus
Praktische Anwendungen: Verifikation der Effektivität in mehr praktischen Systemen

Tiefgreifende Bewertung

Stärken

Theoretischer Beitrag: Erstmals effizienter Algorithmus für Multi-Way-Co-Ranking, füllt theoretische Lücke
Methodische Innovation: Neuartige Indexraum-Operationen vermeiden Einschränkungen traditioneller Methoden
Rigorose Analyse: Vollständige Korrektheitsbeweis und Komplexitätsanalyse
Praktischer Wert: Einfacher Algorithmus, leicht zu implementieren, klare Anwendungsszenarien

Mängel

Fehlende Experimente: Papier ermangelt experimenteller Verifikation, kann tatsächliche Leistung nicht bewerten
Begrenzte Vergleiche: Keine detaillierten Leistungsvergleiche mit bestehenden Methoden
Oberflächliche Anwendungen: Diskussion von Anwendungsszenarien ist relativ einfach, ermangelt tiefgreifender Analyse

Einflussfähigkeit

Akademischer Wert: Bietet theoretische Grundlagen für Multi-Way-Co-Ranking-Problem
Praktisches Potenzial: Hat Anwendungsperspektiven in verteilten Datenverarbeitungs- und parallelen Verarbeitungsbereichen
Reproduzierbarkeit: Autor stellt Implementierungscode bereit, erleichtert Verifikation und Erweiterung

Anwendbare Szenarien

Datenpartitionierung in verteilten Systemen
Lastausgleich in parallelen Algorithmen
Abfrageoptimierung in Datenbanksystemen
Multi-Stream-Merge in Stream-Processing-Systemen

Literaturverzeichnis

1 Greg N. Frederickson and Donald B. Johnson. Generalized selection and ranking. STOC 1980.

2 Christian Siebert. Perfectly load-balanced, stable, synchronization-free parallel merge. Parallel Processing Letters, 2014.

3 Christian Siebert. Simple in-place yet comparison-optimal mergesort, arXiv:2509.24540, 2025.

4 Christian Siebert and Felix Wolf. A scalable parallel sorting algorithm using exact splitting. RWTH Aachen University technical report, 2011.

Gesamtbewertung: Dies ist ein theoretisch starkes Algorithmuspaper, das das wichtige Problem des Multi-Way-Co-Ranking erfolgreich löst. Obwohl es an experimenteller Verifikation mangelt, ist die theoretische Analyse rigoros, die Methode innovativ und bietet wertvolle theoretische Werkzeuge für verwandte Bereiche.