ACM通信
研究突出了
技术角度:买一送一
分类和传输数据是我们使用数字计算机的两个最基本的任务。下面的论文证明了计算机执行这两项任务的效率之间的显著联系，将一个长期存在的关于归并排序最优性的问题和另一个在数据传输的网络编码研究中非常不同的开放问题联系起来。
“合并排序”是最早为数字计算机编写的程序之一。虽然，作为一种基于比较的内存算法，它已经被其他占用内存更好的排序算法以及比任何基于比较的算法更快的算法(如基数排序)所取代，但归并排序在需要外部存储的大量数据排序方面仍然很重要。它可以修改为一次合并多个流，并且只需要对许多存储媒体通用的顺序访问。一个自然要问的问题是:(多路)归并排序是外部内存排序算法的最佳选择吗?或者我们能做得更好?随着大型数据集的普及，这可能有许多实际应用。
要回答这个问题，我们需要一个合适的成本衡量标准。现在的计算机有许多层的存储层次，因此有许多层的“外部”存储器;数据以块(而不是单个数据项)的形式在级别之间传输。这些传输的成本通常超过“内部”内存中操作的成本。因此，对于外部内存算法来说，一个合适的开销度量是传输大小相同的块的数量B输入到大小相同的内存中M。1988年，开发成本衡量方法的阿加瓦尔和维特指出米/ 2B-way Merge Sort，它模拟内存中输入大小的算法的比较传输n / B，对于基于比较的排序算法是渐近最优的，即使对于仅仅将矩阵从行主序转换为列主序的排序实例也是如此。他们留下的挑战是，确定这是否也适用于一般的外部内存排序算法。
对于内存算法，两者之间的鸿沟O（n日志n)对于基于比较的算法和一般算法来说，时间是相当大的:基数排序，它使用间接寻址，运行O（n)时位的长度w键是O(日志n)．另外，正如这篇论文所指出的，对w位单词使用哈希操作的其他内存算法，对于所有的值都可以实现接近这个级别的性能w。一个将军O（n)时间排序算法均可实现w(这里没有考虑这个开放性问题)。然而，间接寻址和哈希的操作似乎没有类似的外部内存算法，这使得归并排序的最优可行。
下面的论文证明了计算机排序数据的效率和传输数据的效率之间的显著联系。
尽管针对单个发送者和接收者的编码理论可以追溯到计算的早期，网络编码是一种较新的发明，出现在共享通信网络中多个发送方-接收方对的环境中。Ahlswede等人表明，在有向网络中，如果网络中的节点主动合并它们接收到的数据内容，而不是简单地将其作为不可分割的单元转发，那么就有可能以更高的速率发送数据。他们的经典例子如下图所示:年代1而且年代2可以同时发送消息流到t1而且t2分别，如果每个度为1的节点沿两条输出边发送其输入，节点u将其输入消息的异或传递给v和节点t1而且t2，依次计算输入流的异或。
另一方面，如果链接是无向的，就像在右边的网络中，不需要编码(甚至使用)就可以达到相同的速率。u，v)链接):每一个年代我只需使用其他每个链路的一半带宽就可以发送x我来t我．(在本例中，可由连续时间步内的交替消息流使用链接。)这个解决方案是网络上(分数)多商品流的一个例子，其中有发送方和接收方对(年代1，t1), (年代2，t2)、单位需求和单位容量。这样的流在每个边缘为每个发送-接收对保留一部分容量。的无向k-pairs猜想，这一观点起源于Li和Li在2004年的一篇论文，认为这样的多商品流解决方案总是最优的，因此在无向网络中，网络编码永远不会有优势。令人惊讶的结果是，如果这个网络编码猜想(一种弱形式)是真的，那么多路合并排序对于外部内存排序是渐进最优的!
另外，根据这篇论文得出的结论，比合并排序更好的算法还有第二个好处:它可以用于设计有向网络，其中使用网络编码实现的速率任意高于不使用网络编码可能实现的速率，即使去掉了网络的方向限制。
数字图书馆是由计算机协会出版的。版权所有©2020 ACM股份有限公司
没有发现记录