ACM通信

研究突出了

通过网络编码的外部内存整数排序的下界

Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, Elaine Shi
ACM通信，2020年10月，第63卷第10期，第97-105页
10.1145 / 3416268
评论

在实践中，对极大的数据集进行排序是一项经常发生的任务。这些数据集通常比计算机的主存储器大得多;因此，首先由Aggarwal和Vitter提出的外部内存排序算法经常被使用。基于比较的外部内存排序的复杂性已经被理解了几十年;然而，如果我们假设要排序的键是整数，情况仍然难以捉摸。在内部存储器中，可以对一组nΘ(lgn)位元O（n)时间使用经典的基数排序算法;然而，在外部内存中，没有比简单的基于比较的整数排序算法更快的算法了。这样的算法是否存在，一直是外部存储器算法中30多年来悬而未决的核心问题。

在这篇论文中，我们提出了一个紧整数的外部内存排序复杂度的条件下界。我们的下界是基于Li和Li在网络编码中的一个著名猜想，他们猜想网络编码不能帮助任何超出无向图中标准多商品流量的东西。

此前唯一将李氏猜想和李氏猜想与算法的下界联系起来的工作是由阿德勒等人完成的。Adler等人确实得到了相对简单的下界无视算法(内存访问模式是固定的，与输入数据无关)。不幸的是，遗忘是一个很强的限制，特别是对于整数排序:我们表明Li和Li猜想意味着Ω(nlgn)内部内存的下界无视当键为Θ(lgn)位。这与经典的(非无关的)基数排序算法形成鲜明对比。事实上，超越遗忘是非常重要的;为了获得内存整数排序的紧下界，我们需要引入一些各自感兴趣的新方法和涉及的技术。

回到顶部

1.简介

排序是最基本的算法基元之一，从计算时代开始就引起了广泛的关注。针对这一问题设计了许多经典算法，如归并排序、冒泡排序、插入排序等。由于对超大数据进行排序已经成为许多应用程序的必要条件，设计更高效的大数据集排序算法一直是人们关注的焦点²这些数据集通常比计算机的主存要大得多，性能瓶颈从执行的CPU指令的数量变为访问速度较慢的二级存储的数量。在这种外部内存设置中，通常使用外部内存模型来分析算法的性能。外部内存算法被设计为最小化的数量输入/输出(I / O)s在内部内存和外部内存(例如，硬盘驱动器和云存储)之间，我们通过算法执行的I/ o数量来衡量算法的复杂性。

形式上，外部内存模型由一个可以保存的主内存组成米的话语w每(位)内存共有米＝兆瓦位)，和一个无限(随机访问)磁盘分区成块B连续的单词w每个(块共有的)位b＝Bw位)。外部内存算法的输入最初存储在磁盘上，并假定其远远大于米．然后，算法可以将块读入内存或将块写入磁盘。我们把这两个操作统称为I/O。算法的复杂度仅通过它产生的I/ o的数量来衡量。

阿加瓦尔和维特²考虑了外部存储器模型中的排序问题。对经典的归并排序算法进行一个简单的修改，生成一个基于比较的排序算法O（(n / B)格林_{M / B}（n / B))用于对数组进行排序的I/ on可比较的记录(每个可存储在一个字)w位)。请注意,O（n / B)对应于线性I/ o，因为这是读/写输入/输出所需的I/ o量。阿加瓦尔和维特²用一个匹配的下界来补充它们的上界，表明基于比较的外部内存排序算法必须使Ω((n / B)格林_{M / B}（n / B) I / Os。在同一篇论文中，Aggarwal和Vitter还表明，任何处理密钥的算法不可分割的原子，意味着键被复制到磁盘块和从磁盘块中复制，但从来没有通过位技巧或类似的方法重建，必须使Ω(min{n, (n / B)格林_{M / B}（n / B)}) I / o。这个下界不假设基于比较的算法，而是做了一个不可分割的假设。注意，下界与基于比较的下界相匹配，足够大B（B> lgn就足够了)。因此，比较和不可分割性的设定已经(几乎)被完全理解了30多年。

然而，如果排序问题的输入假设为w位整数，我们允许对整数进行任意操作(哈希、异或技巧等)，那么情况就完全不同了。在标准的内存计算模型中，称为字ram，人们可以设计出远远优于基于比较的算法的整数排序算法w．更具体地说，如果字和键的大小是w=Θ(lgn)，则Radix Sort在中解决问题O（n)时间，和任意w，可以设计运行时间为的排序算法在随机情况下⁶而且O（nlg lgn)在决定论的情况下⁵(这两个边界都假设字大小和键大小互为常数因子)。在外部内存中，没有任何整数排序算法比基于比较的算法更快O（(n / B)格林_{M / B}（n / B)界是已知的!Aggarwal和Vitter在最初的论文中提出了一个重要的开放问题，即是否存在更快的整数排序算法²这就引入了外部内存模型。三十年过去了，我们仍然不知道这个问题的答案。

本文通过Li和Li的一个中心猜想，给出了内存整数排序的条件下界⁷在…领域网络编码．我们的条件下界表明，不可能设计出优于基于最优比较的整数排序算法，从而解决了Li和Li猜想下整数排序的复杂度。

1.1.网络编码

网络编码领域研究的是网络上的以下通信问题G加上边缘的容量限制k数据流，每个数据流具有指定的源-接收器节点对(年代_我，t_我)G，源接收器对之间并发传输数据的最大速率是多少?一个简单的解决方案是将数据作为不可分割的包转发，有效地将问题减少到多商品流(MCF)。网络编码的关键问题是使用编码/比特技巧是否能达到更高的速率。在有向图中，这个问题已知有一个肯定的答案，其中增长率可能高达Ω(|G|)(通过发送精心选择的输入位的异或);例如，阿德勒等人。¹然而，对于无向图，这个问题仍然是开放的，因为没有已知的例子表明网络编码可以比多商品流速做得更好。缺乏这样的例子导致了网络编码中的以下中心猜想。⁷

猜想1(无方向的k对推测)。编码率等于无向图中的多商品流量．

尽管这一猜想的核心是什么，但迄今为止，它拒绝了所有证明或反驳它的尝试。Adler等人。¹在猜想和算法的下界之间建立了一个令人兴奋的联系。更具体地说，他们证明了如果猜想1是正确的，那么立即得到以下所有的非平凡下界:

• 无视外部内存算法
• 无视word-RAM算法
• 无视双带图灵机

在上面，无视表示算法(或图灵机的磁带移动)的内存访问模式是固定的，独立于输入数据。因此，证明猜想1也将给出所有这类算法的第一个非平凡下界。我们可以从两方面来看待这种联系:要么是(受限)算法令人兴奋的条件下界，要么是证明猜想1将非常困难的强烈信号。

在本文中，我们回顾了猜想1的复杂性理论含义。我们的结果表明，对无关算法的限制是不必要的。更详细地说，我们展示了猜想1暗示了整数的外部内存排序和外部内存矩阵转置算法的非平凡(实际上是紧密的)下界。当字的大小远大于键的大小时，我们还得到了字ram排序算法的严格下界，以及a的转置的严格下界b×b一个字大小的字ram上的矩阵b位。引人注目的是，我们的下限在没有任何额外的假设，例如遗忘，不可分割，网络，或类似的。因此，证明猜想1就像证明在完全通用的字- ram模型中的超线性算法下界一样困难，这是一个远远超过当前下界技术的障碍!此外，我们证明了先前论文中关于算法是无关的假设对整数排序产生了巨大的影响:我们证明了一个Ω(nlgnΘ(lg。n)位整数，使用一个字大小为Θ(lgn)位。这与经典的(非无关的)基数排序算法形成了鲜明的对比O（n)时间。因此，对于某些问题，之前对无关算法的限制可能是非常严重的。

1.2.排序的下界

我们对外部内存整数排序的主要结果与猜想1的关系如下:

定理2。假设猜想1，对于带w的外部存储器排序问题的任意随机算法=Ω(lgn）位整数，最多有错误概率1/3,必须做出预期

I / o．

因此，如果我们相信猜想1，那么即使对于随机化算法，也没有希望利用整数输入来改进简单的基于外部内存比较的算法(当B≥lgn这样下界中的后一项就是最小值)。

现在观察一下，因为我们的下界只计算I/ o，当字的大小是一些时，下界立即适用于字ram算法b=Ω(lgn)通过设置米＝O（b),B＝b / w在上面的下界(CPU的内部状态，即寄存器，只能容纳恒定数量的单词)。因此，我们得到以下下界:

推论3。假设猜想1，任意随机字ram算法用于排序w=Ω(lgn）位整数，最多有错误概率1／3单词大小为b≥W位，必花

时间．

我们注意到字ram中的一个标准假设是字大小和键大小b，w=Θ(lgn)位。对于这种参数的选择，我们的下界退化到微不足道的程度t=Ω(n)．这是必然的，因为基数排序给出了匹配的上界。尽管如此，我们的下界表明，当键大小远远小于字大小时，就不能在线性时间内对整数排序(回想一下线性是O（西北/ b)，因为这是读/写输入/输出的时间)。

最后，我们证明了Adler等人在前一篇论文中提出的遗忘假设。¹可以证明非常强的排序下界，甚至超过已知的(非无关的)基数排序上界:

定理4。假设猜想1，任意无关随机字ram排序算法Θ(lgn）位整数，最多有错误概率1／3和字的大小Θ(lgn)，必须花Ω(nlgn）时间．

因此，至少对于整数排序这一自然问题来说，健忘对算法可能的性能有巨大的影响。因此，我们的结果不仅仅是将以前的技术应用到一个新问题上，而且是一个很大的加强。此外，正如我们在第3节中讨论的，消除遗忘假设需要新的和深入的思想，这将导致更具有挑战性的下限证明。

1.3.矩阵转置的下界

我们还谴责了阿德勒等人对下界的模拟。¹对于矩阵转置问题，这次没有任何遗忘的假设。在矩阵转置问题中，输入是ann×n矩阵一个与w-bit整数项。矩阵是按行为主的顺序给出的，这意味着每一行一个存储在n / B块B每个都是连续的。目标是计算一个^T的列主表示一个存储n / B的每列的磁盘块一个，每个包含一个连续的范围B列中的条目。

定理5。假设猜想1，任意求解有w位整数项的外存矩阵转置问题的随机算法，误差概率最大1/3,必须做出预期

I / o．

现在考虑一下字大小的字ram上的矩阵转置问题b位(以及内存大小)米＝O（b))。给定一个n×n矩阵一个与w-bit整数项，定理5中的下界表示(通过设置B＝b / w)：

推论6。假设猜想1，任何用于计算n转置的随机字ram算法×N个带w位整数项的矩阵，误差概率不超过w位1／3而字大小b位，必须花

时间．

回到顶部

2.预赛

我们现在给出一个正式的定义k-配对沟通问题和多商品流动问题。

k-对通信问题。为了使定义尽可能简单，我们将自己限制为有向无环通信网络/图，并假设每个源-接收器对之间的需求是相同的。这对我们的证明就足够了。关于更一般的定义，我们请读者参阅阿德勒等人。¹

的输入k-对通信问题是一个有向无环图G= (V，E)其中每条边e∈E有能力c（e)∈r⁺．有k来源年代₁、……年代_k∈V而且k汇t₁、……t_k∈V．通常情况下，还会有需求d_我在每个源接收器对之间，但为了简单起见，我们假设d_我所有对= 1。这对于我们的目的来说已经足够了。

每个源年代_我．收到消息一个_我来自预定义的消息集合一个（我)．我们可以方便地认为这条消息是从边缘到达的。因此，我们增加了一个额外的节点年代_我对于每个源，它有一个单独的外缘到年代_我．边缘有无限的容量。

网络编码解决方案为每条边指定e∈E字母表Γ(e)表示沿边缘可发送的可能消息集。对于一个节点v∈V，定义In(u)作为at的边集u．网络编码解决方案还为每条边指定e= (u，v)∈E，一个函数f_e:Π_{e‘∈Ιn (u）}Γ(e”)→Γ(e)决定沿边缘发送的信息e作为节点上所有传入消息的函数u．最后，为每个接收器指定一个网络编码解决方案t_我解码函数σ_我:Π_e∈Ιn (t_我)Γ(e)→米（我)．如果，对于所有输入，网络编码解决方案是正确的一个₁、……一个_k∈Π_我一个（我)，则σ_我应用于传入的消息t_我=一个_我，即每个源必须收到预期的消息。

在网络编码解决方案的执行中，每个额外的节点年代_我从传递信息开始一个_我来年代_我沿着边缘(年代_我，年代_我)．那么，每当一个节点u已收到消息一个_e沿着所有传入的边e= (v，u)，它计算f_e”(Π_{e∈Ιn (u）}一个_e)，并沿边缘转发讯息e”．

阿德勒等人。¹(并简化了一点)，我们定义率让每个源接收一个统一的、随机的、独立选择的消息一个_我从一个（我)．对于每条边e,让一个_e表示在边缘上发送的消息的随机变量e当使用给定输入执行网络编码解决方案时。网络编码解决方案实现速率快r如果:

• H（一个_我)≥理查德·道金斯_我＝r对所有我．
• 对于每条边e∈E，我们有H（一个_e)≤c（e)．

在这里H(x)为二元Shannon熵。直觉告诉我们速率是r，如果该解决方案可以处理将所有消息的熵提升一个因子r与需求相比。

Multicommodity流。无向图中的多商品流动问题G= (V，E)由一组k源-汇对(年代_我，t_我)的节点G．我们这样说年代_我是商品的来源吗我而且t_我是商品的水槽吗我．每条边e∈E有相关的能力c（e)∈r⁺．此外，还有一个需求d_我在每个源-接收器对之间。为了简单起见，我们假设d_我= 1为所有我这足以满足我们的需要。

多商品流问题的(分数)解为每对节点指定(u，v)和商品我，一个流动f_我（u，v)∈[0,1]。直观地说,f_我（u，v)指定商品的数量我是从哪里发出的u来v．流满足流保护，意思是:

• 对于所有节点u这不是源或汇，我们有∑_w∈vf_我（u，w−∑_w∈vf_我（w，u) = 0。
• 对于所有来源年代_我我们有∑_w∈vf_我（年代_我，w)−∑_w∈vf_我（w，年代_我) = 1。
• 对于所有的汇，我们有∑_w∈vf_我（w，t_我)−∑_w∈vf_我（t_我，w) = 1。

该流还满足任意对节点(u，v)和商品我，只有一个方向的流动，也就是，eitherf_我（u，v) = 0或f_我（v，u) = 0。此外，如果(u，v)并不是一个优势E,然后f_我（u，v) =f_我（v，u) = 0。多商品流动问题的解决方案达到的速率r如果:

• 对于所有的边e= (u，v)∈E，我们有r·∑_我d_我（f_我（u，v）+f_我（v，u)) =r·∑_我（f_我（u，v）+f_我（v，u)≤c（e)．

直观上，速率是r如果我们能把需求提高一倍r不违反容量限制。

无向的k对推测。对于我们的设置，猜想1暗示了以下内容k-对通信问题，由有向无环图指定G用边容量和一套k源汇对每对的需求为1，令r的最佳可实现网络编码速率G．同样,让G’表示将每条有向边引入而得到的无向图G无向(并保持容量、源-汇对和每对之间的需求为1)。让r '是可达到的最佳流量G’．猜想1暗示了这一点r≤r '．

在正式定义了编码率和流量率之后，我们还提到了Braverman等人的结果。⁴意味着如果存在一个图G网络编码率在哪里r以及流速r '对应的无向图G’满足r≥(1 +)r '对于常数ε > 0，则存在无穷图族{G^＊}，对应的间隔至少为(lg| .}G^＊|)^c对于一个常数c> 0。到目前为止，所有的证据都表明，如猜想1中形式化的那样，不存在这样的差距。

回到顶部

3.证据的概述

在本节中，我们概述了我们证明中的主要思想，并解释了我们为了消除遗忘假设而克服的障碍。为了证明我们对外部内存排序的下界，我们关注更简单的排序问题。在排列问题中，我们给定一个数组一个的n条目。的我的条目一个存储w-位数据项d_我目标π(我)．终点π(我)形成排列π{1，…，n}。目标是生成输出数组C在哪里d_我存储在条目中Cπ(我)]。数组一个而且C都存储在磁盘块中，这样每个磁盘块的一个商店b/ (lgn+w的每个磁盘块C商店b / w条目(一个块中可以打包的条目的最大数量)。一个排序算法，可以排序(lgn+w)位整数键可以用来解决排列问题，通过替换每个条目(π(我)，d_我)，以整数π(我)×2^w+d_我(在加法中，我们想到d_我作为[2]中的整数^w])。因此，证明排列的下界就足够了。

现在考虑一个排列算法A，为了简单起见，假设它是确定的并且总是正确的。正如阿德勒等人之前的工作一样。¹，我们定义一个图G（一个)，它捕获A在输入数组上的内存访问一个．这个图G对输入数组中的每个块都有一个节点，对输出数组中的每个块都有一个节点，对a写/读的每个中间块都有一个节点，我们称之为块节点。此外，图中还有一个表示a的内存状态的内存节点。其思想是，每当a将一个块读入内存时，我们就从相应的块节点向内存节点添加一条有向边。当A写入一个块时，我们创建一个新节点(替换块的前一个版本)，并从内存节点向新节点添加一个有向边。算法A现在可以用于在输入和输出块节点之间发送消息，如下:给定消息X₁、……X_n的w位和预期的输出块节点(存储Cπ(我)])为每条消息我，我们就能传递信息X_我从表示数组条目的输入块节点一个［我]到表示数组条目的输出块节点Cπ(我)]，只需模拟算法A:网络的每个块节点总是将任何传入的消息沿其出沿转发到内存节点。因此，内存节点接收它曾经读过的所有块的内容。因此，它可以模拟a。每当执行写操作时，它将沿边缘发送内容到指定的块节点。通过A的正确性，这将导致每个输出块节点都知道所有数组项的内容Cπ(我)]，应该存储在输出块中。检查这个模拟，我们看到我们需要一个容量b所有边缘上的位，以满足容量约束。另外，由网络编码率的定义(第2节)可知，编码率为w位。

我们要用猜想1来证明这个图G必须很大(即必须有很多I/ o)。为此，我们想争辩说，如果我们不直接G，那么有一个排列π，使许多对一个［我),Cπ(我)]，存储的块节点之间没有短路径一个［我),Cπ(我)]。如果我们能证明这一点n/2对(一个［我),Cπ(我))时，距离至少为ℓ步骤中的无向版本G，则达到流量的w的能力之和必然是这样的G至少是lwn/ 2。但是每个I/O只增加2b容量的位G．因此，如果A使tI/ o，那么它一定是结核病=Ω(ℓwn)⇒t=Ω((西北/b)×ℓ= Ω((n/B)×ℓ)。

不幸的是，我们不能说图中的许多对之间一定有一条很长的路径G我们在上面定义。问题是内存节点连接到所有块节点，因此距离永远不会超过2。为了解决这个问题，我们改变了的定义G稍:在每m / bI/ o时，我们停用内存节点并创建一个新的内存节点来替换它。进一步的I/ o在这个新的内存节点之间插入边缘。为了让新的内存节点继续模拟A，新的内存节点需要知道A的内存状态。因此，我们从旧的去激活的内存节点插入一条有向边到新的内存节点。边缘有容量米位。因此，在模拟中，当当前内存节点已执行时m / bI/ o，它将A的内存状态转发给下一个继续模拟的内存节点。的m / b在创建新内存节点之间选择I/O，以便保留由于I/O而平摊的容量增加O（b)．

我们现在已经得到了一个图表G所有节点的度数都以2为界m / b．因此，对于每个节点G，最多有(2)个m / b）^ℓ的距离内的节点ℓ．因此，直观地说，随机排列π应该具有大多数对(一个［我),C［π（我))，将有一个距离ℓ= Ω(lg_2米/bn/B)在相应的块节点之间。的下界t=Ω((n/B)×ℓ)=Ω((n/B)×lg_2米/bn/B)．

如果我们假设算法A像之前的工作一样是无关的，我们现在应该已经完成了。这是因为，在遗忘假设下，图表G会是一样的对所有输入数组。因此，人们确实可以找到理想的排列π，在大多数对之间有很大的距离(一个［我),C［π（我)))。此外，对应于该排列π和数据位串的所有输入d₁、……d_n可以用A和图正确模拟G．因此，人们立即得到了一个网络编码解决方案。然而，当A不被约束为无关时，可以有大量不同的图G由执行A。

为了克服这一障碍，我们首先认为，即使可以有许多不同的图，这样的图的数量仍然被大约(西北/ b+t）^t(每个I/O选择一个块读或写，有tI / o)。这意味着t＝o（n)，仍然可以找到一个图表G这是在许多不同的输入数组上运行A的结果一个．我们可以说，在所有这些输入中一个，有很多都对应于相同的排列π，并且排列π具有之前的性质，对于大多数对(一个［我),C［π（我))，将有一个距离ℓ= Ω(lg_2米/bn/B)在相应的块节点之间。因此，我们想对这样一个排列进行固定，用a得到一个网络编码方案。问题是我们只能说有许多数据位串d₁、……d_n这和π一起形成了一个数组一个A用图表表示G．因此，我们只能正确地传输大量消息，而不是所有消息。我们称之为集合F⊆{{0,1}^w｝ⁿ假设|F|≥2^{西北−o（西北）}．直观地说，如果我们画一个均匀的随机输入F，那么我们应该有一个速率为的网络编码解决方案w−o（w)．问题是网络编码的定义要求节点的输入是独立的。因此，我们不能立即说我们有一个有速率的网络编码解决方案w−o（w)通过求解一个均匀随机输入F．为了解决这个问题，我们采用以下方法:我们让每个数据位串起来d_我是一种统一的随机和独立的选择w位字符串。因此，如果我们能用这些输入来解决网络编码问题，那么我们就确实有了一个网络编码的解决方案。我们现在想找到一种转换位串的有效方法d₁、……d_n到新的位串d '₁、……d '_n与d '₁、……d '_n∈F．转换应该使每个输入块节点都能在本地计算d '_我，输出块节点应该能够恢复转换，也就是说，计算从d '_我原始位串d_我．为了实现这一点，我们需要修改G一点。我们的想法是引入一个协调节点，它可以发送映射之间的简短描述d_我年代和d '_我我们通过以下引理来实现这一点:

引理7。考虑一个协调者u，集合F的沟通游戏⊆{0,1}^西北n个玩家。假设|F|≥2^mw-r协调器接收n个均匀随机位串X作为输入_我每个w位，选择独立于另一个X_j．协调器然后发送一个没有前缀的消息R_我到第i个玩家，从信息R_我例如，在不知道X的情况下_我)，第i个玩家就可以计算一个向量τ_我∈{0,1}^w它的性质是串联问: =(τ₁⊕X₁)(τ₂⊕X₂(τ_n⊕X_n）满足问∈F，在哪里⊕表示位X0R。存在这样的协议

特别是，如果r＝o（西北）和w=ω(1),那么沟通就满足了∑_我E [|R_我|] =o（西北)．

我们使用的引理如下:我们创建一个协调节点u它连接到所有输入块节点和所有输出块节点。在a的模拟中，输入块节点首先将它们的输入发送到协调节点u．协调器然后计算引理中的消息并发送R_我返回输入块节点存储一个［我]以及存储数组条目的输出块节点Cπ(我)]。输入块节点现在可以计算了d '_我＝τ_我⊕d_我要获得一个输入d '₁、……d '_n∈F．然后我们可以运行算法A因为这是一个实际生成图的输入G．最后，输出块节点可以通过计算恢复映射d_我=τ_我⊕d '_我．因此，引理所实现的是一种局部修改节点输入的有效方法，从而获得算法A适用的输入。我们发现这种贡献非常新颖，并怀疑它可能在其他下界证明中也有应用。

节点的引入u当然允许一些流遍历不在原图中的路径G．因此，我们必须注意如何在边缘上设置到和从的容量u．我们注意到从输入节点到u只需要一个能力w每个数组条目(它们发送输入)的位，以及出的边un .需要R_我|]输入的容量d_我(一个这样的边到数组入口的输入块节点一个［我和一个这样的边到输出块节点用于数组入口Cπ(我)))。关键的观察结果是任何使用节点的流u作为一个中间节点必须遍历至少两条边u．因此，只有(西北+ 2∑_我E [|R_我)/2 2流可以穿过这样的路径。|F|≥2^{西北−o（西北）}，那么引理7说这个不大于西北/ 2 +o（西北)流。因此仍然存在西北/ 2−o（西北)的流，它必须穿过原来的长度ℓ=Ω(lg_{2m / b}n / B)路径和下界。

可以观察到，我们的证明使用了这样一个事实，即网络编码速率在强意义上最多是流量速率。实际上，节点的引入u允许流的恒定部分可能使用恒定长度的路径。因此，网络编码速率是至关重要的r流速r '推测满足吗r≤r '而不是，例如，r≤3r '．事实上，我们只能说一个好得令人难以置信的排列算法产生了一个图r≥基于“增大化现实”技术的对于某个常数一个> 1。然而，布雷弗曼等人。⁴最近证明，如果有一个图r≥(1 + ε)^{r '}对于常数ε > 0，则有一个无穷图族{G’}，其中差距是Ω((lg |G’|)^c)为常数c> 0。因此，一个好得令人难以置信的排列算法确实会为猜想1提供一个强有力的反例。

我们对引理7的证明是非常重要的，它是建立在由巴拉克等人约束。^3.用于压缩非产品分布下的交互通信。我们的主要想法是，对于{0,1}中的均匀随机位串，^西北(对应于级联X＝X₁ο…X_n的X_我的引理中)，则到最近位串的期望汉明距离必然是这样的Y在F是．协调器因此发现Y并传送异或信号X⊕Y敬球员们。XOR是稀疏的，因此可以通过只指定非零项使消息变得简短。证明了到最近向量的期望距离是是主要的技术难点，也是使用协议压缩思想的部分。

回到顶部

4.外部内存下限

正如在第3节的证明概述中提到的，我们通过一个更简单的排列问题的下界来证明我们的外部内存排序的下界:排列问题的输入由{1,2，…n}以及n位字符串d₁、……d_n∈{0,1}^w．我们假设w≥lgn这样所有的位串都可以是不同的。输入以数组的形式给出一个在哪里我“th条目一个［我存储元组π(我)，d_我)．我们假设输入以下列自然方式给出:我)被编码为a [lgn-bit整数和d_我是在使用时给出的w每个比特。

数组一个以块序列的形式呈现给外部内存算法，其中每个块包含⌊b/（w+ lgn)⌋的连续条目一个(方块有b＝Bw位)。为简单起见，我们从今往后假设(w+ lgn)分b．

该算法还给出了一个初始空输出数组C．数组C表示为n的话语w每个位，这些都被打包成包含b / w每个单词。目标是储存d_{π⁻¹（我）}在C［我］．也就是说，目标是复制位串d_我从一个［我)Cπ(我)]。我们说算法A的误差是ε对于置换问题，如果对于问题的每个输入，它产生的正确输出的概率至少为1−ε．

排列问题最著名的上界也适用于不可分割假设。这些算法解决了排序问题

I / o。²此外，在不可分性假设下，通过使用计数论证，可以很容易地证明这是最优的。²的n边界是通过运行简单的“内部存储器”算法获得的边界，该算法只是将每个元素一次放到正确的位置。另一个术语等价于基于最优比较的排序边界d_我作为[2]中的整数^w并连接π(我)○d_我=π(我)×2^w+d_我并对序列进行排序)。因此，任何处理(lgn+w)位键立即产生具有相同I/ o数量的排列算法。由此证明了排序问题的下界，并立即得到排序下界作为推论。

因此，我们开始使用猜想1为外部内存模型中的排列问题提供一个下界。在整个证明过程中，我们假设西北/ b＝n / B至少是一个大的常数。这是安全的假设，否则我们只要求Ω(1)的一个微不足道的下界。

设A是上的排列问题的随机外存算法n整数的w位。假设A的错误概率不超过1/3，让b以位数表示磁盘块大小。让米表示以位数衡量的内存大小。最后,让t表示A(在最坏的输入上)的期望I/ o数。

我/ O-graphs。对于输入数组一个表示排列π和位串d₁,……d_n和一个输出数组C，定义(随机)I/ o图G初始化G每个磁盘块中有一个节点一个每个磁盘块有一个节点C．另外，添加一个节点G表示a的初始内存，我们认为节点表示的磁盘块一个而且C作为块节点节点用a表示内存内存节点(见图1一个)．我们将添加更多的节点和边G通过观察A的执行一个．为了简化描述，我们将节点称为G要么死或生活．我们总是最多有一个活动的内存节点。最初，所有节点都是活动的。我们使用0标记内存节点。此外，我们用从1开始的连续整数标记块节点。因此，初始图中的块节点被标记为1,2，…，n（w+ lgn) /b+西北/ b．

现在，运行算法A一个．每当它进行I/O时，请按照以下步骤进行:如果这是第一次，则该块正在被访问，并且它不是输入或输出的一部分(对未访问的块的写操作)。然后，在中创建一个新的活动块节点G并从当前活动内存节点向新块节点添加有向边(参见图1 e)．用下一个未使用的整数标签标记新节点。否则,让v成为活动节点G对应于最后一次访问磁盘块的时间。我们添加一条有向边v到活动内存节点，标记v作为死块，创建一个新的活块节点v '，并添加从活动内存节点到的有向边v '．我们给新节点相同的标签v（图1 b而且c)．最后，每个人一次m / bI/ o时，我们将内存节点标记为死亡，创建一个新的活动内存节点，并从旧的内存节点向新的活动内存节点添加有向边(图1 d)．

图1。数组的I/ o图一个由3位字符串组成d₁、……d₈．在本例中，每个磁盘块包含两个单词的w= 3位，即B= 2 (and)b＝Bw= 6)。此外，主内存保存米= 6个字(米= 18)。图(a)显示了初始I/ o图。对于每个磁盘块，我们最初有一个块节点，如图所示。黑结点是死结点，白结点是活结点。图(b)显示了对第一个磁盘块进行I/O访问后更新的I/O图。图(c)是访问包含的块后的I/ o图C[1],C[2]。图(d)显示了在第一个磁盘块上再次进行I/O后的图形。此外，我们在每m / b＝M / B= 3个I/ o，并将旧内存节点标记为死亡。图(e)显示了访问输入或输出之外的某个块后更新的图。

以便更好地理解的定义G，可以观察到所有具有相同标签的节点都表示在整个算法执行过程中存在的磁盘块的不同版本。此外，总是有一个带有固定标签的活动节点，表示磁盘块的当前版本。另外，注意到在执行结束时，必须有一个活动的磁盘块节点G中的每个输出块C的空磁盘块的原始节点具有相同的标签C在执行A。

修正的随机性A.考虑A在输入上的执行一个表示均匀随机排列π以及独立和均匀随机位串d₁、……d_n∈{0,1}^w．因为A产生了期望tI/ o，根据马尔可夫不等式A的收益大于6tI/ o概率小于1/6。如果在这种情况下我们简单地中止，我们得到了一个最坏情况下的算法O（t， I/ o和错误概率为1/3 + 1/6 = 1/2。现在修正A的随机选择，得到确定性算法A^＊误差概率是1/2除以π的随机值d₁、……_n．一个^＊使t^＊= 6t最坏情况下的I/ o。观察A^＊，我们得到一个固定的I/O图G（一个)用于每个输入数组一个因为一个^＊是确定的。

找到一个流行的I/ o图。我们现在找到了一个I/ o图G这是运行A的结果^＊大量不同的输入。为了方便记法，令t表示A的最坏I/ o数^＊(而不用t^＊或6t)．观察运行A所能得到的不同I/ o图的总数^＊小:

引理8。没有超过

执行A可能产生的I/ o图^＊．

这意味着我们可以找到一个I/ o图，它对应于A的执行^＊在很多不同的输入上，而且，我们甚至可以假设A^＊在许多这样的输入上是正确的:

引理9。存在一个集合Γ，其中至少包含（n2 !^西北) / (2 (t+n（w+ lgn) /b+西北/b+ 1)^t＋1）不同的输入数组A，这样一个^＊是否所有输入都正确∈ΓI/ o图对所有A都是一样的∈Γ。

数据必须传输得很远。我们的下界证明的关键思想是证明存在一种大多数数据位串的排列d_我离输出入口很远吗Cπ(我)]在相应的I/ o图中。这将需要数据“传输”很远。根据猜想1，除非I/ o图很大，否则这是不可能的。因此，我们首先认为存在一种固定的排列，即数据平均必须传输很远，并且它还认为可以使用相同的I/ o图发送许多不同的数据值。为了使它更正式，令dist(π，我，G)表示块节点之间的距离G表示输入块存储一个［我)(在执行任何I/ o之前的初始节点)G表示存储的输出块Cπ(我)]在无向版本的G(不直接指向所有边)。

我们证明如下:

引理10。如果（t+n（w+ lgn) /b+西北/b+ 1)^t＋1≤(西北/b）^{（n/ 30)}，然后存在一个排列π,值的集合F⊆{{0,1}^w｝ⁿ以及满足以下条件的I/ o图G:

1. 所有人(d₁、……d_n)∈F，则认为算法A^＊在输入数组上执行一个对应于输入π和d₁、……d_n产生I/ o图G和一个^＊是正确的一个．
2. 
3. 至少有(4/5)N个指标I∈{1，…，n｝去哪个区?(π,我，G) > (1/2_{2m / b}（西北/ b)．

简化为网络编码。现在我们准备简化网络编码。我们证明的基本思想是使用引理10来获得I/ o图G和排列π的大距离节点之间包含一个［我和包含Cπ(我对许多人来说我．然后我们将创建一个源年代_我在表示的节点一个［我和相应的水槽t_我对应的节点Cπ(我)]。这些节点相距很远，但使用外部内存排列算法A^＊，有一个传输算法d_我从年代_我来t_我．因为两者之间的距离年代_我而且t_我至少是(1/2)lg吗_{2m / b}（西北/ b)为(4/5)n其中(年代_我，t_我)，由猜想1可知，网络中的容量之和至少为Ω(西北lg_{2m / b}（西北/ b我们可以传送w每对之间的位)。然而，运行外部内存算法的结果是一个网络/图G只有O（t)，每条都只需要传输b位(与读或写时的块内容相对应)。因此，每条边只需要有容量b进行还原的位。因此，网络中的容量之和为O（结核病)．这意味着t=Ω((西北/b)格林_2米/b（西北/b))。

然而，削减并没有那么简单。问题是引理10只留给我们一个子集F所有可能的值d₁、……d_n它想要传输信号。的其他值d₁、……_n，我们不能用算法A^＊通过网络/图形传输数据G．我们当然可以尝试抽样(d₁、……d_n)一致地从F然后对这些输入有一个网络编码解决方案。问题是这样的制服(d₁、……d_n)∈F，它不再认为编码网络中对源的输入是独立的!网络编码率只涉及独立源;因此，我们需要一种方法来打破这种依赖关系。我们通过增加一个额外的节点来做到这一点u还有一些编码网络的边缘。这个额外的节点u作为独立来源的协调者X₁、……X_n并将它们替换为输入(d₁、……d_n)∈F以这样一种方式运行^＊(d₁、……d_n)，并使用一点额外的沟通u让水槽恢复X_{π⁻¹（我）}从d_{π⁻¹（我）}．我们继续给出正式的构造。让G为I/ o图，π为排列，和F⊆{{0,1}^w｝ⁿ引理10所承诺的值。从G，构建编码网络G^＊如下:

1. 添加源节点和汇聚节点年代₁、……年代_n而且t₁、……t_n来G^＊．
2. 对于每个源年代_我，增加一个节点p_我．
3. 的所有节点G来G^＊．
4. 添加所有的边G来G^＊．块节点和内存节点之间的边有容量b位。两个内存节点之间的边有容量米位。
5. 删除所有对同一内存节点有出入边的块节点(这会使图变得无循环)。
6. 添加具有容量的有向边w每个源的比特年代_我来p_我，并添加具有容量的有向边w每一个的比特p_我输入块节点包含一个［我］．
7. 增加容量的边缘w来自输出块节点的位，其中包含Cπ(我)到水池边t_我．
8. 添加一个特殊节点u来G^＊．增加容量的边缘w每个源的比特年代_我来u．另外，添加一条有向边u对每一个p_我有能力ρ_我对于参数ρ_我> 0稍后修改。另外，添加一条边u下沉t_我容量ρ_我．

我们认为，对于ρ的选择足够大_我A .答案为A^＊有效地传输w每个源-接收器对之间的比特信息(年代_我，t_我)．我们解决这个问题的协议使用第3节中的引理7作为子例程。我们推迟引理7的证明。可以看出，存在一个用于传输的传输协议X₁、……X_n它满足了网络的所有容量约束G^＊．确切的协议可以在论文的完整版本中找到。

求下界。我们观察到对于所有的边，除了那些具有ρ容量的边_我，我们的协议发送固定数量的位。因此，这些边缘上的消息是无前缀的。对于有容量的边ρ_我时，协议发送一个无前缀的消息，其预期长度为ρ_我．因为所有边上的所有消息都是无前缀的，根据香农的源编码定理，每个消息的期望长度是其熵的上限。由于期望长度最多是对应边的容量，我们根据第2节中对网络编码速率的定义，得到上述解的速率为w位。因此，由猜想1可知，如果我们没有定向G^＊，则多商品流动率必须至少w位。从第2节多商品流通量的定义中，我们可以看出，这意味着存在一种(可能是分数)发送方式w每个源-汇对之间的流量单位。

我们首先检查可在对之间传输的流量(年代_我，t_我)沿着参观的小径u．我们观察到，任何这样的流必须使用至少两个边u．但是边的容量之和u是西北+ 2∑_我ρ_我．因此，可以沿使用的路径传输的流量u作为中间节点不超过西北+ 2∑_我ρ_我) / 2 =西北/ 2 +∑_我ρ_我．如果|F|≥2^{西北−o（西北）}，那么这就不超过西北/ 2 +o（西北)．由引理10，我们知道至少有(4/5)n指数我对于dist(π，我，G≥(1/2)lg_2米/b（西北/b)，但前提是(t+n（w+ lgn) /b+西北/b+ 1)^t＋1≤(西北/b）^(1/30)n．必须在这些对之间发送的总流量是(4/5)西北．这意味着至少有(4/5)西北- - - - - -西北/ 2 -o（西北) = Ω(西北)必须穿过(1/2)lg的流_{2m / b}（西北/ b= Ω(lg_{2m / b}（西北/ b))边缘G^＊的无向版本中，流必须使用路径G因为它不能通过捷径u)．因此，对应于边的容量之和G必须是Ω(西北lg_{2m / b}（西北/ b))，假设|F|≥2^{西北−o（西北）}．A的每一个I/O^＊增加边缘的容量O（b的两个边b增加一个新块节点时的位容量G和平摊b比特能力支付米后，内存节点之间的位边m / bI / o)。因此，如果A^＊最多赚tI/ o，它一定是这样的结核病=Ω(西北lg_2米/b（西北/b))如果|F|≥2^{西北−o（西北）}．但|F|≥2^西北/ 4 (t+n（w+ lgn) /b+西北/b+ 1)^t＋1．因此，我们两者都必须有t=Ω((西北/b)格林_2米/b（西北/b)或tlg (tn（w+ lgn) /b=Ω(西北)．最后，引理10也是必需的(t+n（w+ lgn) /b+西北/b+ 1)^t＋1≤(西北/b）^(1/30)n．结合所有这些意味着t=Ω((西北/b)格林_2米/b（西北/b),或t=Ω(西北/ lg (西北))或t=Ω(nlg (西北/b) / lg (nlg (西北/b)) = Ω(n)．

因此，利用约简排序，我们证明了:

为w=Ω(lgn)，我们可以用约简来排序，我们立即得到定理2作为推论。

定理2。假设猜想1，对于带w的外部存储器排序问题的任意随机算法=Ω(lgn）位整数，最多有错误概率1/3,必须做出预期

I / o．

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2020 ACM, Inc.

---

没有找到条目