论文标题
遗物遗忘：一种非常简单的遗忘
Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
论文作者
论文摘要
我们提出了一种概念上简单的遗漏和遗忘的随机排列算法，称为遗物遗漏的排序和遗物遗漏的随机排列。 Bucket Oblevious -Sort使用$ 6N \ LOG N $ TIME（通过内存访问的数量来衡量）和$ 2Z $客户端存储，其错误概率为$ z $中的错误概率为小。上述运行时仅比非封合合并排序基线的$ 3 \ times $慢。对于$ 2^{30} $元素，它比Bitonic Sort的$ 5 \ times $ $ \ times $，在实际实现中，事实上忽略的排序算法。
We propose a conceptually simple oblivious sort and oblivious random permutation algorithms called bucket oblivious sort and bucket oblivious random permutation. Bucket oblivious sort uses $6n\log n$ time (measured by the number of memory accesses) and $2Z$ client storage with an error probability exponentially small in $Z$. The above runtime is only $3\times$ slower than a non-oblivious merge sort baseline; for $2^{30}$ elements, it is $5\times$ faster than bitonic sort, the de facto oblivious sorting algorithm in practical implementations.
