论文标题
剥离接近可定位性阈值：基于哈希的数据结构中的空间耦合
Peeling Close to the Orientability Threshold: Spatial Coupling in Hashing-Based Data Structures
论文作者
论文摘要
在多项选择数据结构中，每个元素$ x $在套装$ s $ m $键中与随机集合$ e（x）\ subseteq [n] $ abuck $ \ ell \ geq 1 $ by hash函数。此设置由HyperGraph $ h =（[n]，\ {e（x）\ mid x \ in S \}）$捕获。在关联的存储桶中加工每个密钥的相当于找到向每个HyperEdge分配的$ \ ell $ - 方向，以使每个顶点分配给每个顶点，以最多分配$ \ ell $ $ hyperedges。如果每个$ h $的每个subhypergraph最多都具有最低$ \ ell $，则可以贪婪地找到$ \ ell $ - 定位，而$ h $称为$ \ ell $ -peelable。剥落性在可逆的布鲁姆查找表中具有核心作用，并且可以加快检索数据结构，完美的哈希功能和杜鹃的桌子的构建。 相对于$ \ ell $ - 定向性和$ \ ell $ - pelability，许多超图具有急剧的密度阈值，即作为密度$ c = \ frac {m} {n} $的密度，这些物业的可能性从这些属性的概率降至近1美元$ 0 $ $ 0 $。在完全随机的$ k $ - 均匀的超图中，阈值$ c_ {k，\ ell}^*$ for $ \ ell $ - 方向可显着超过$ \ ell $ - peelability的阈值。在本文中，对于$（k，\ ell）\ neq（2,1）$和每个$ z> 0 $，每$ k \ geq 2 $和$ \ ell \ geq 1 $，我们构建了一个随机$ k $ roniform-surom-riform-riform-riform hypraphs的新家族。随机的超蛋白质使$ \ ell $ - peelability和$ \ ell $ - 方向性阈值接近$ c_ {k，\ ell}^*$ as $ z \ rightarrow \ rightarrow \ infty $。 我们通过在低密度平价检查代码中发现的空间耦合来利用阈值饱和的现象。一旦与数据结构的连接变得清晰，Kudekar，Richardson和Urbanke（2015）的框架在我们的证明中繁重。
In multiple-choice data structures each element $x$ in a set $S$ of $m$ keys is associated with a random set $e(x) \subseteq [n]$ of buckets with capacity $\ell \geq 1$ by hash functions. This setting is captured by the hypergraph $H = ([n],\{e(x) \mid x \in S\})$. Accomodating each key in an associated bucket amounts to finding an $\ell$-orientation of $H$ assigning to each hyperedge an incident vertex such that each vertex is assigned at most $\ell$ hyperedges. If each subhypergraph of $H$ has minimum degree at most $\ell$, then an $\ell$-orientation can be found greedily and $H$ is called $\ell$-peelable. Peelability has a central role in invertible Bloom lookup tables and can speed up the construction of retrieval data structures, perfect hash functions and cuckoo hash tables. Many hypergraphs exhibit sharp density thresholds with respect to $\ell$-orientability and $\ell$-peelability, i.e. as the density $c = \frac{m}{n}$ grows past a critical value, the probability of these properties drops from almost $1$ to almost $0$. In fully random $k$-uniform hypergraphs the thresholds $c_{k,\ell}^*$ for $\ell$-orientability significantly exceed the thresholds for $\ell$-peelability. In this paper, for every $k \geq 2$ and $\ell \geq 1$ with $(k,\ell) \neq (2,1)$ and every $z > 0$, we construct a new family of random $k$-uniform hypergraphs with i.i.d. random hyperedges such that both the $\ell$-peelability and the $\ell$-orientability thresholds approach $c_{k,\ell}^*$ as $z \rightarrow \infty$. We exploit the phenomenon of threshold saturation via spatial coupling discovered in the context of low-density parity-check codes. Once the connection to data structures is in plain sight, a framework by Kudekar, Richardson and Urbanke (2015) does the heavy lifting in our proof.
