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

基本信息

论文ID: 2510.22882
标题: Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge
作者: Amit Joshi (Independent Researcher)
分类: cs.DS (Data Structures and Algorithms)
发表时间: 2025年10月27日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.22882

摘要

本文提出了一种无合并的多路协同排名算法，用于计算切割索引 $i_1,\dots,i_m$ ，将 $m$ 个排序序列分割，使得所有前缀段总共包含恰好 $K$ 个元素。该方法将Siebert和Träff的双列表协同排名扩展到任意 $m$ 路，维护每个序列的边界并收敛到一致的全局前沿，无需执行多路合并或值空间搜索。算法在索引空间应用二分搜索，时间复杂度为 $O(\log(\sum_t n_t)\log m)$ ，空间复杂度为 $O(m)$ ，且独立于 $K$ 。通过交换论证证明了正确性，并讨论了在分布式分数背包、并行合并分区和多流连接中的应用。

研究背景与动机

问题定义

多路协同排名问题定义如下：给定 $m$ 个按非递减顺序排序的序列 $L_1, \ldots, L_m$ （允许重复），每个序列长度为 $n_t$ ，以及全局目标排名 $K \in \{0, \ldots, N\}$ （其中 $N = \sum_t n_t$ ），需要找到切割索引 $i_1, \ldots, i_m$ 使得：

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

其中 $\ell_t$ 和 $r_t$ 分别表示左边界值和右边界值。

研究动机

扩展经典算法：现有的协同排名算法主要针对两个序列，缺乏高效的多路扩展
避免合并开销：传统方法需要先合并多个序列再进行选择，开销较大
索引空间优势：在索引空间而非值空间操作，避免了值域搜索的复杂性
实际应用需求：分布式计算、并行处理和数据库查询中都需要高效的多路分区算法

现有方法局限性

Siebert-Träff方法：仅支持两个序列的协同排名
Frederickson-Johnson方法：在值空间操作，需要全局计数操作
基于分割器的方法：需要预先合并或值域搜索，复杂度较高

核心贡献

算法设计：提出了首个无合并的多路协同排名算法，将经典的双路方法扩展到任意 $m$ 路
理论分析：证明了算法的正确性和 $O(\log(\sum_t n_t)\log m)$ 时间复杂度
数据结构创新：设计了索引堆（addressable heaps）来高效维护边界值
应用拓展：展示了算法在分布式优化、并行处理和数据库系统中的应用潜力

方法详解

任务定义

输入：

$m$ 个排序序列 $L_1, \ldots, L_m$ ，长度分别为 $n_1, \ldots, n_m$
目标排名 $K \in [0, N]$ ，其中 $N = \sum_{t=1}^m n_t$

输出：

切割索引向量 $(i_1, \ldots, i_m)$ 满足协同排名条件

约束条件：

$\sum_{t=1}^m i_t = K$
$\max_t \ell_t \leq \min_t r_t$ （协同排名条件）

算法架构

核心数据结构：索引堆

算法维护两个索引堆：

$H_L$ ：最大堆，存储左边界值 $(\ell_t, t)$ ，返回最大左边界的序列（捐赠者）
$H_R$ ：最小堆，存储右边界值 $(r_t, t)$ ，返回最小右边界的序列（接收者）

每个堆支持 $O(\log m)$ 的update_key操作和 $O(1)$ 的peek操作。

边界管理

为每个序列 $t$ 维护：

下界： $Lb[t] \leq i[t]$
上界： $i[t] \leq Ub[t]$
当前索引： $i[t]$

迭代策略

算法采用捐赠者-接收者的贪心策略：

识别极值：
- 捐赠者 $p = \arg\max_t \ell_t$ （最大左边界）
- 接收者 $q = \arg\min_t r_t$ （最小右边界）

计算转移量：

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

执行转移：
- $i[p] \leftarrow i[p] - \Delta$
- $i[q] \leftarrow i[q] + \Delta$
- 更新边界： $Ub[p] \leftarrow i[p]$ ， $Lb[q] \leftarrow i[q]$
更新堆：刷新受影响序列的堆键值

技术创新点

索引空间操作：完全在索引空间工作，避免了值域搜索和合并操作
几何收敛：通过对半缩减可行域，保证了对数级别的收敛速度
不平衡势函数：定义 $\Phi(i) = \max_t \ell_t - \min_t r_t$ 作为收敛判据
确定性复杂度：算法复杂度独立于目标排名 $K$

理论分析

正确性证明

引理1（局部极值最优性）

如果 $\Phi(i) > 0$ ，设 $p = \arg\max_t \ell_t$ 和 $q = \arg\min_t r_t$ 。在所有保持 $\sum_t i_t = K$ 的可行无穷小转移中， $(p,q)$ 对实现了 $\Phi$ 的最大非递增变化。

证明思路：减少 $i_p$ 会降低 $\ell_p$ （左边界的局部最大值），增加 $i_q$ 会提高 $r_q$ （右边界的局部最小值）。由于 $\ell_p \geq \ell_u$ 且 $r_q \leq r_v$ 对所有 $u,v$ 成立，极值对 $(p,q)$ 产生最陡的间隙 $\max\ell - \min r$ 减少。

引理2（转移顺序交换性）

任何减少 $\Phi$ 的可行转移序列都可以重新排序，使得所有极值 $(p,q)$ 转移发生在任何非极值转移之前，且不会恶化任何中间步骤的 $\Phi$ 。

定理1（收敛性和有效性）

算法2以有效的协同排名向量 $(i_1, \ldots, i_m)$ 终止，满足 $\sum_t i_t = K$ 和 $\max_t \ell_t \leq \min_t r_t$ 。

复杂度分析

轮次分析

每轮中，捐赠者或接收者的可行距离被对半缩减。每个序列的距离 $Ub[t] - Lb[t]$ 最多缩减 $O(\log n_t)$ 次。聚合所有 $m$ 个序列，总轮次数为：

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

时间复杂度

每轮执行常数次索引堆操作（ $O(\log m)$ 时间），总时间复杂度为：

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

空间复杂度

算法只需存储 $m$ 个序列的索引和边界信息，空间复杂度为 $O(m)$ 。

算法实现

核心算法流程

def multi_way_corank(sequences, K):
    m = len(sequences)
    # 初始化边界和索引
    Lb = [0] * m
    Ub = [len(seq) for seq in sequences]
    i = water_fill_initialization(K, Ub)
    
    # 构建索引堆
    HL = MaxHeap()  # 左边界最大堆
    HR = MinHeap()  # 右边界最小堆
    
    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:
        # 获取捐赠者和接收者
        max_left, p = HL.peek()
        min_right, q = HR.peek()
        
        # 检查终止条件
        if max_left <= min_right:
            break
            
        # 计算转移量
        donor_slack = ceil((i[p] - Lb[p]) / 2)
        receiver_slack = ceil((Ub[q] - i[q]) / 2)
        delta = min(donor_slack, receiver_slack)
        
        # 执行转移
        i[p] -= delta
        i[q] += delta
        
        # 更新边界
        Ub[p] = i[p]
        Lb[q] = i[q]
        
        # 更新堆
        update_heaps(HL, HR, sequences, i, p, q)
    
    return i

初始化策略

采用"水填充"策略初始化可行解：

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