We consider the problem of approximate sorting in I/O model. The goal of approximate sorting in I/O model is to find out a permutation that is as close as possible to the true ordering of elements in $t$ I/O operations. However, the quality of approximate sorting in I/O model can not be well measured by the existing metrics on permutation space. Thus, we propose a new kind of metric named External metric, which ignores the errors and dislocation that happened in each I/O block. We consider the \textit{External Spearman's footrule metric} (short for \textit{ESP}) (\textit{Spearman's footrule metric} in RAM model) and a new metric \textit{external errors} (short for \textit{EE}) (\textit{errors} in RAM model). \textit{ESP} shows the block dislocation distance of each element and \textit{EE} states the number of the dislocation elements in the approximate result. According to the rate-distortion relationship endowed by these two metrics, we find the lower bound of these two metrics of the permutation generated by any external approximate sorting algorithm with $t$ I/O operations. Finally, we propose a k-pass external approximate sorting algorithm that is asymptotically optimal in I/O model.
翻译:我们考虑I/ O 模型中的近似排序问题。 在 I/ O 模型中近似排序的目标是找到尽可能接近于美元 I/ O 操作中元素真正排序的调值。 但是, I/ O 模型中近似排序的质量无法用现有的调整空间参数来很好地测量。 因此, 我们提出一种新的称为外部的衡量标准, 它忽略了每个 I/ O 块中发生的错误和错乱。 我们考虑 I/ O 模型中近似排序的目标是找到一个尽可能接近于美元 I/ O 操作中元素真正排序的调值。 但是, I/ O 模型中近似排序的质量无法用现有的调整位空间中的现有参数来衡量 。 因此, 我们提议一种新的称为外部测量值的质量( ) ( textititutit{ ) (textit{ errors ) 。\ textitleitleitleitalit { { { ESp} 显示每个元素和 文本 { ETE} 的调调调调度指标 的调值 } (对调值表示调和调值的调和调值的调值 。