超宽字RAM上的动态范围最小值查询

《Information and Computation》:Dynamic Range Minimum Queries on the Ultra-Wide Word RAM

【字体: 大 中 小 】 时间:2026年09月21日 来源:Information and Computation 1.4

编辑推荐:

  摘要译文: 研究人员考虑超宽字RAM(Ultra-Wide Word RAM, UWRAM)计算模型上的动态范围最小值问题。该模型扩展了经典的w位字RAM模型,增加了长度为w2位的特殊超宽字,支持标准算术与布尔运算,以及能够并行访问存

  
摘要译文:
研究人员考虑超宽字RAM(Ultra-Wide Word RAM, UWRAM)计算模型上的动态范围最小值问题。该模型扩展了经典的w位字RAM模型,增加了长度为w2位的特殊超宽字,支持标准算术与布尔运算,以及能够并行访问存储器中w个(非连续)位置的分散内存访问操作。超宽字RAM模型刻画(并理想化了)现代向量处理器体系结构。动态范围最小值问题的目标是在数组A(包含n个w位整数)上维护操作:范围最小值查询(给定索引i和j,返回子数组A[i..j]中的最小整数)和更新(给定索引i和整数α,令A[i] ← α)。研究人员的主要结果是一个数据结构,支持范围最小值查询和更新的时间复杂度为O(log log log n),并且在输入数组之外仅使用O(n/log n)字空间。该结果指数级地改进了现有技术的时间复杂度。研究结果基于一个简单的归约方法,将问题归约为对O(log n)字序列的前缀最小值计算,并结合一种新的并行递归实现方式。
论文解读:

1. 研究背景与问题

动态范围最小值问题(Dynamic Range Minimum Query, Dynamic RMQ)是经典的数据结构问题,要求维护一个长度为n的w位整数数组A,并支持两种操作:范围最小值查询rmq(i,j),返回子数组A[i..j]中的最小整数;以及更新update(i,α),将A[i]设置为α。在传统字RAM(word RAM)模型上,该问题已有紧密的时间界Θ(log n / log log n)。然而,现代硬件中向量处理器等并行架构不断发展,自然引发一个疑问:能否利用刻画现代硬件的计算模型显著改进这一界?超宽字RAM模型(UWRAM)由Farzan等人提出,在标准字RAM基础上增加长度为w2位的特殊超宽字,支持对超宽字的标准布尔和算术操作,以及可并行访问w个内存位置(不要求连续)的分散内存访问操作。该模型理想化了IBM Cell架构、Intel AVX向量扩展等现代向量处理特性。此前通过扩展现有UWRAM技术可立即得到O(log log n)时间的动态RMQ解,但研究人员的目标是指数级改进这一时间界。

2. 研究内容与结论

研究人员的核心贡献是:在UWRAM模型上构建一个数据结构,支持rmq和update操作均在O(log log log n)时间内完成,并且在输入数组之外仅使用O(n/log n)字空间,预处理时间为O(n)。这一结果将现有O(log log n)时间界指数级降低。技术路线基于一个称为范围最小值树(range minimum tree)的朴素线性空间对数时间解法。该树是输入数组上的平衡二叉树,原始遍历需O(log n)时间。研究人员在UWRAM上利用分散内存访问和超宽字上的前缀最小值计算,并行高效地生成操作所需的访问模式。关键在于将动态RMQ归约为对长度为O(log n)的单词序列的前缀最小值(prefix minimum, pmin)计算:若前缀最小值算法的时间为t(?),则可得到动态RMQ的O(t(log n))时间解。随后,研究人员设计了一个新的前缀最小值算法,在O(log log ?)时间内完成长度?=O(w)的序列的前缀最小值计算,从而得到最终结果。

3. 关键技术方法

研究人员采用的主要技术方法包括:(1)范围最小值树的UWRAM并行实现,通过路径序列、左/右序列和离路径序列表示查询与更新所需节点,结合分散读写和前缀最小值计算在常数条超宽字上并行处理;(2)标准间接寻址(indirection)技术:将数组划分为大小为log n的块,构造块最小值数组并递归应用数据结构,将附加空间从O(n log n)降至O(n)再降至O(n/log n);(3)隐式二叉堆布局:将范围最小值树以堆数组存储,通过二进制位运算直接计算节点序列和最低公共祖先深度;(4)新的递归并行前缀最小值算法:常数时间内计算长度为O(√w)的“短”序列的前缀最小值,再通过递归倍增块大小(b到b2),经过O(log log ?)轮得到一般长度序列的结果。样本队列来源方面,论文为纯理论研究,不涉及实验样本。

4. 研究结果

4.1 范围最小值树在UWRAM上的实现

研究人员首先展示了直接实现:存储输入数组A、范围最小值树T以及支持常数时间最低公共祖先查询的数据结构。对每个索引i存储路径序列、左路径序列、右路径序列和离路径序列,以及对应的深度序列。查询时通过LCA计算深度d,用掩码提取深度大于d+1的节点,再用分散读获取权重并求最小值。更新时读取离路径序列,计算其权重与α的前缀最小值,再分散写回路径节点。所有操作除(前缀)最小值计算外均为常数时间,因此总时间为O(1+t(log n)),但空间为O(n log n)。

4.2 空间归约至O(n)

通过一层间接寻址,将A划分为n/log n个大小为log n的块,存储每块最小值于块数组B,并在B上构建上述数据结构。查询分同块和跨块两种情况,同块直接读取块内局部范围并求最小值;跨块分解为左块、中块和右块三部分,中块用范围最小值树求最小。更新则修改对应块内值,重新计算块最小值,若改变则更新树。这使得空间和预处理时间降为O(n),时间仍为O(1+t(log n))。

4.3 空间进一步归约至O(n/log n)

研究人员引入隐式二叉堆布局,将范围最小值树存储在数组H[1..2n?1]中,叶子对应原数组,内部节点按堆序存放。查询和更新所需的路径序列可由叶子索引的二进制表示通过右移和位操作直接计算,而无需显式存储所有序列。为高效实现右移任意位数,研究人员设计辅助数组HA和HB,利用去除二进制表示尾部连续0或1的方式完成。计算LCA深度则通过两叶子索引的异或结果最高有效位获得。结合与4.2节相同的间接寻址,最终使附加空间降至O(n/log n)。

4.4 前缀最小值算法的常数时间短序列实现

针对长度?=O(√w)的单词序列,研究人员提出三步常数时间算法:第一步,通过构造两个长度为?2的单词序列并做逐分量比较,得到所有元素对之间的≤比较结果矩阵C;第二步,利用lclear操作将C中每行从右往左的连续1“涂抹”开,再与位置掩码M按位与,得到指示矩阵E,其中E?i,j?=1当且仅当X?i?是X?0..j?的前缀最小值;第三步,通过预定义的索引序列进行带掩码的提取和分散写,把每个X?i?写到其应当成为前缀最小值的位置。若存在重复元素,则通过将每个元素与位置序号组成两倍长度的复合字来打破平局。该算法可直接并行处理多个长度为b的块,得到b路前缀最小值常数时间算法。

4.5 一般长度序列的递归前缀最小值算法

对于长度?=O(w)的序列,研究人员从b=2开始,反复应用引理5:已知b路前缀最小值后,可常数时间计算b2路前缀最小值。具体步骤为:先计算各块最小值的b路前缀最小值B_b;然后将B_b中每个分量复制b次并左移b个字,与一个块内掩码M相或,得到包含每个块之前所有块最小值的序列;再与原始b路前缀最小值X_b逐分量取最小值,即生成b2路前缀最小值。由于b以平方速度增长,经过O(log log ?)轮达到b≥?,从而完整计算整个序列的前缀最小值。将该算法代入前述归约,即得到定理1的O(log log log n)时间界。

5. 总结与结论

讨论部分总结如下:研究结果在受限UWRAM模型上同样成立,但该时间界是否为该模型甚至更强的乘法UWRAM模型下的最优解仍是开放问题。动态RMQ的变体若允许修改底层数组本身的长度或结构,则现有技术难以直接扩展。此外,部分技术在当前处理器(如AVX-512)上可能具有实用性,但能否在实际实现中超越现有动态RMQ算法仍有待验证。研究结论为:研究人员在UWRAM模型上构建了一个O(n)空间的数据结构,支持动态范围最小值查询与更新操作均在O(log log log n)时间内完成,并在输入数组之外仅使用O(n/log n)字空间,从而指数级改进了此前O(log log n)的时间界。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号