Almost random graphs with simple hash functions
Almost random graphs with simple hash functions
复制标题
具有简单哈希函数的几乎随机图
DOI：
10.1145/780542.780634
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Philipp Woelfel
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger;Philipp Woelfel
我们描述一种简单的随机构造方法，用于从全集\(U\)生成哈希函数对\(h_1\)，\(h_2\)，其值域\(V = [m] = \{0, 1, \ldots, m - 1\}\)且\(W = [m]\)，使得对于每个键集\(S \subseteq U\)，其中\(n = |S| \leq m / (1 + \varepsilon)\)，具有节点集\(V \cup W\)和边集\(\{(h_1(x), h_2(x)) | x \in S\}\)的（随机）二分（多重）图呈现出一种本质上随机的结构。该构造将\(d\)元独立类（\(d\)为相对较小的常数）与著名的随机偏移技术相结合。在将存储\(h_1\)和\(h_2\)的描述所需空间保持在\(O(n^{\zeta})\)（对于任意固定的\(\zeta < 1\)）的同时，我们获得了比此前此类构造（涉及西格尔的高性能哈希类）小得多的（常数）求值时间。主要的新技术是对图结构和哈希函数内部结构的联合分析，以及一种观察随机（多重）图的圈结构的新方法。这种构造可用于改进帕格和罗德勒的“布谷鸟哈希”（2001年），为模拟键集\(S\)上的均匀哈希获得一种比奥斯特林和帕格（2002/2003年）近期构造更简单且更快的替代方法，并用于在分布式内存机器上模拟共享内存。我们还描述了一种不使用多项式实现（近似）\(d\)元独立哈希的新方法。
We describe a simple randomized construction for generating pairs of hash functions h1,h2 from a universe U to ranges V = [m] = (0,1,...,m-1) and W = [m] so that for every key set S ⊆ U with n = |S| ≤ m/(1 + ε) the (random) bipartite (multi)graph with node set V ∪ W and edge set (h1(x),h2(x))| x ∈ S exhibits a structure that is essentially random. The construction combines d-wise independent classes for d a relatively small constant with the well-known technique of random offsets. While keeping the space needed to store the description of h1 and h2 at O(nζ), for ζ < 1 fixed arbitrarily, we obtain a much smaller (constant) evaluation time than previous constructions of this kind, which involved Siegel's high-performance hash classes. The main new technique is the combined analysis of the graph structure and the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random (multi)graphs. The construction may be applied to improve on Pagh and Rodler's "cuckoo hashing" (2001), to obtain a simpler and faster alternative to a recent construction of Ostlin and Pagh (2002/03) for simulating uniform hashing on a key set S, and to the simulation of shared memory on distributed memory machines. We also describe a novel way of implementing (approximate) d-wise independent hashing without using polynomials.