Dense Peelable Random Uniform Hypergraphs
Dense Peelable Random Uniform Hypergraphs
复制标题
密集可剥离随机均匀超图
DOI：
10.4230/lipics.esa.2019.38
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Stefan Walzer
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger;Stefan Walzer
我们描述了一个具有独立随机边缘的$ K $均匀超图。超图具有可剥离的可能性，即，即使边缘密度（顶点的边缘数）接近$ 1 $，也没有承认最低度$ 2 $的次毛。在我们的构造中，顶点集分为线性排列的片段，每个边缘都发生在$ k $连续段的随机顶点。令人惊讶的是，线性几何形状可以“从外部”剥离我们的图形。我们的超图的剥落性的密度阈值$ f_k $（$ f_3 \ of 0.918 $，$ f_4 \ oft 0.977 $，$ f_5 \ of y of 0.992 $，...）远远超出了相应的阈值，标准$ K $ - 均匀的随机超图。为了抓住$ f_k $，我们分析了一个理想化的剥离过程，该过程在我们的HyperGraph家族的随机弱极限上进行了分析。该过程可以用运算符上的功能描述，$ f_k $可以链接到与操作员有关的阈值。这些阈值然后使用数值方法进行处理。
随机超图基于哈希的各种数据结构的构建。这些数据结构经常依赖于超图或剥离性的剥离性，可提供简单的线性时间算法。为了证明我们的构建的有用性，我们使用了$ 3 $均匀的超图作为Botelho等人检索数据结构中标准$ 3 $均匀的超图的替换。这将内存使用率从123万美元的位降低到112万美元的$ $位（$ m $为输入大小），几乎没有运行时间的变化。
We describe a new family of $k$-uniform hypergraphs with independent random edges. The hypergraphs have a high probability of being peelable, i.e. to admit no sub-hypergraph of minimum degree $2$, even when the edge density (number of edges over vertices) is close to $1$. In our construction, the vertex set is partitioned into linearly arranged segments and each edge is incident to random vertices of $k$ consecutive segments. Quite surprisingly, the linear geometry allows our graphs to be peeled "from the outside in". The density thresholds $f_k$ for peelability of our hypergraphs ($f_3 \approx 0.918$, $f_4 \approx 0.977$, $f_5 \approx 0.992$, ...) are well beyond the corresponding thresholds ($c_3 \approx 0.818$, $c_4 \approx 0.772$, $c_5 \approx 0.702$, ...) of standard $k$-uniform random hypergraphs. To get a grip on $f_k$, we analyse an idealised peeling process on the random weak limit of our hypergraph family. The process can be described in terms of an operator on functions and $f_k$ can be linked to thresholds relating to the operator. These thresholds are then tractable with numerical methods.
Random hypergraphs underlie the construction of various data structures based on hashing. These data structures frequently rely on peelability of the hypergraph or peelability allows for simple linear time algorithms. To demonstrate the usefulness of our construction, we used our $3$-uniform hypergraphs as a drop-in replacement for the standard $3$-uniform hypergraphs in a retrieval data structure by Botelho et al. This reduces memory usage from $1.23m$ bits to $1.12m$ bits ($m$ being the input size) with almost no change in running time.
用于检索和近似成员资格的简洁数据结构
DOI：
10.1007/978-3-540-70575-8_32
发表时间：
2008
期刊：
影响因子：
--
作者：
Martin Dietzfelbinger;Rasmus Pagh
通讯作者：
Rasmus Pagh
随机二部图中左完美匹配的最优度分布
影响因子：
0.5
作者：
Martin Dietzfelbinger;Michael Rink
通讯作者：
Michael Rink
用于线性时间构造更密集的基于散列的数据结构的混合超图
DOI：
10.1007/978-3-642-35843-2_31
发表时间：
2013
期刊：
影响因子：
--
作者：
Michael Rink
通讯作者：
Michael Rink