Cache-Oblivious Peeling of Random Hypergraphs
Cache-Oblivious Peeling of Random Hypergraphs
复制标题
随机超图的缓存不经意剥离
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Vigna
中科院分区：
文献类型：
--
作者：
Djamal Belazzougui;P. Boldi;G. Ottaviano;Rossano Venturini;S. Vigna
随机生成的超图中剥离顺序的计算是许多构造中最耗时的步骤，例如完美的哈希方案，随机的R-SAT求解器，错误校正的代码和近似设置编码。尽管存在直接的线性时间算法，但其较差的I/O性能使其对于大小超过可用内部内存的超图形不切实际。我们展示了如何将剥离顺序的计算减少到少量的顺序扫描和分类，并分析其在合并模型中的I/O复杂性。所得算法需要O.Sort.N // I/ OS和O.N Log N/ Time将随机的超图剥离N边缘。我们通过使用最小的完美哈希功能（MPHF）作为测试案例，在现实世界中，在现实世界中实现了该算法的实现的性能：我们的算法在不到21小时的时间内建立了7：60亿键的MPHF。在一台机器上。所得的数据结构既比使用当前最新的MPHF构造获得的大规模钥匙集的数据结构更高，更快。
The computation of a peeling order in a randomly generated hypergraph is the most time-consuming step in a number of constructions, such as perfect hashing schemes, random r-SAT solvers, error-correcting codes, and approximate set encodings. While there exists a straightforward linear-time algorithm, its poor I/O performance makes it impractical for hypergraphs whose size exceeds the available internal memory. We show how to reduce the computation of a peeling order to a small number of sequential scans and sorts, and analyze its I/O complexity in the cache-oblivious model. The resulting algorithm requires O.sort.n// I/Os and O.n log n/ time to peel a random hypergraph with n edges. We experimentally evaluate the performance of our implementation of this algorithm in a real-world scenario by using the construction of minimal perfect hash functions (MPHF) as our test case: our algorithm builds a MPHF of 7:6 billion keys in less than 21 hours on a single machine. The resulting data structure is both more space-efficient and faster than that obtained with the current state-of-the-art MPHF construction for large-scale key sets.