冲击哈希:接近最佳空间最小的完美哈希超越原始力量
Hans-Peter Lehmann1, Peter Sanders1, Stefan Walzer1
1Karlsruhe Institute of Technology, Karlsruhe, Germany.
概括
ShockHash通过使用一种新的子哈希方法显著改进了最小完美的哈希函数 (MPHF) 构建. 这种方法减少了施工时间和空间要求,使MPHF更高效.
科学领域:
- 计算机科学 计算机科学
- 算法算法是一种算法.
- 数据结构 数据结构
背景情况:
- 最小完美的哈希函数 (MPHF) 将n个密钥映射到n个整数,没有碰撞.
- 现有的MPHF构造方法通常依赖于具有高计算成本的蛮力方法.
- 理论上,MPHF的最佳空间约为1.44n位.
研究的目的:
- 介绍ShockHash,一种用于构建最小完美的哈希函数的新方法.
- 提高现有的MPHF构建算法的效率 (时间和空间).
- 减少在构建过程中需要测试的哈希函数种子数量.
主要方法:
- ShockHash使用两个哈希函数和1位检索数据结构来存储映射函数.
- 它将问题建模为在n边随机图中找到伪森林.
- 采用子哈希计算,从伪森林结构中导出MPHF.
主要成果:
- 冲击哈希将测试种子的预期数量减少到大约1.359^n,这与粗暴武力相比是显著的改善.
- 这导致种子存储空间大约减少n位,并加快了近2^n的速度.
- 双部分式ShockHash进一步缩短了预期的施工时间,约为1.166^n.
- 与RecSplit集成的ShockHash-RS实现了高达3个数量级更快的构建速度.
结论:
- ShockHash提供了一种更有效的方法来构建最小完美的哈希函数.
- 该方法实现了异常最佳的空间复杂性,同时大大减少了施工时间.
- ShockHash-RS展示了实际效率,可以快速为大型数据集构建MPHF.
相关概念视频
Optimization Problems
24
Optimization problems often involve identifying maximum or minimum values under specific constraints. A well-known example is determining the longest horizontal pipe that can be moved around a right-angled corner, where a 3-meter-wide hallway meets a 2-meter-wide hallway. This scenario, common in architectural design and industrial transport, can be understood conceptually through geometric and trigonometric reasoning.To visualize the problem, consider the pipe as a straight line that touches...
24
Optimal Foraging
13.6K
How animals obtain and eat their food is called foraging behavior. Foraging can include searching for plants and hunting for prey and depends on the species and environment.
13.6K
Routh-Hurwitz Criterion II
955
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
955
Compacting Factor test
548
The compacting factor test is a method used to assess the workability of concrete. It is especially suitable for concrete mixes containing aggregates up to one and a half inches in size. This test involves specialized equipment consisting of two truncated cone-shaped hoppers and a cylinder, all with polished interior surfaces to minimize friction.
The procedure begins by placing concrete into the upper hopper without any compaction. Once filled, the bottom door of this hopper is opened,...
The procedure begins by placing concrete into the upper hopper without any compaction. Once filled, the bottom door of this hopper is opened,...
548
Heuristics
657
Heuristics are problem-solving strategies that use mental shortcuts to simplify decision-making. Unlike algorithms, which must be followed precisely to achieve a correct result, heuristics offer a general problem-solving framework. They save time and energy but can sometimes lead to less rational decisions.
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
657
Routh-Hurwitz Criterion I
548
Consider an electrical power grid, where stability is essential to prevent blackouts. The Routh-Hurwitz criterion is a valuable tool for assessing system stability under varying load conditions or faults. By analyzing the closed-loop transfer function, the Routh-Hurwitz criterion helps determine whether the system remains stable.
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
548

