Mixed Hypergraphs for Linear-Time Construction of Denser Hashing-Based Data Structures
Mixed Hypergraphs for Linear-Time Construction of Denser Hashing-Based Data Structures
复制标题
用于线性时间构造更密集的基于散列的数据结构的混合超图
DOI：
10.1007/978-3-642-35843-2_31
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Michael Rink
中科院分区：
文献类型：
--
作者：
Michael Rink
有几种基于哈希的数据结构，其空间利用率（每个表单元格的键）直接取决于某些底层随机均匀超图中出现2核的边密度阈值。我们表明，通过修改这些数据结构，使thek-均匀超图被某些非均匀超图所取代，它们的空间利用率可以提高。这些非均匀超图是均匀超图的混合，每个超图具有线性数量的边，但具有不同的边大小。在两种不同边大小的情况下，我们给出了每种大小的最佳（预期）边数量的解决方案，使得所得混合超图的2核阈值最大化。对于合适的边缘大小，我们获得了最佳阈值为0.920的混合超图，提高了最大2-核心阈值为任何随机均匀超图，这是约0.818。
There are several hashing-based data structures whose space utilization (keys per table cells) directly depends on the edge density threshold for the appearance of a 2-core in some underlying randomk-uniform hypergraph. We show that by modifying these data structures such that thek-uniform hypergraphs are replaced by certain non-uniform hypergraphs their space utilization can be improved. These non-uniform hypergraphs are a mixture of uniform hypergraphs each with a linear number of edges but with different edge sizes. In the case of two different edge sizes we give a solution for the optimal (expected) number of edges of each size such that the 2-core threshold for the resulting mixed hypergraph is maximized. For suitable edge sizes we obtain optimal thresholds for mixed hypergraphs up to 0.920, improving the maximum 2-core threshold for any randomk-uniform hypergraph, which is about 0.818.
登录
查看更多内容
图、超图和散列
DOI：
--
发表时间：
1993
期刊：
International Workshop on Graph-Theoretic Concepts in Computer Science
影响因子：
--
作者：
G. Havas;B. Majewski;N. Wormald;Z. Czech
通讯作者：
Z. Czech
理论上良好的检索数据结构的实验变体
DOI：
10.1007/978-3-642-04128-0_66
发表时间：
2009
期刊：
影响因子：
--
作者：
Martin Aumüller;Martin Dietzfelbinger;Michael Rink
通讯作者：
Michael Rink
随机二部图中的最大匹配与布谷鸟哈希表的空间利用率
DOI：
--
发表时间：
2009
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
A. Frieze;Páll Melsted
通讯作者：
Páll Melsted
随机超图中的纯字面规则阈值和核心
DOI：
--
发表时间：
2004
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Michael Molloy
通讯作者：
Michael Molloy
用于检索和近似成员资格的简洁数据结构
DOI：
10.1007/978-3-540-70575-8_32
发表时间：
2008
期刊：
影响因子：
--
作者：
Martin Dietzfelbinger;Rasmus Pagh
通讯作者：
Rasmus Pagh