简单制表哈希的威力
该论文研究了哈希在机器学习中降维的基本用途,比较了各种哈希方案的性能,主要关注该领域中的两个应用:相似度估计与特征哈希。作者发现 Dahlgaard 等人的混合制表哈希是一种在许多应用中表现良好的伪随机哈希函数,其性能与真随机哈希函数相似,比 MurmurHash3 快 40%。
Nov, 2017
通过构建 4 倍独立的哈希函数,实现了期望对数搜索时间的线性探测,对于(1+ϵ)- 近似的 minwise 独立,需要 Ω(log 1/ϵ)独立的哈希函数匹配一个上限,并证明了 Dietzfelbinger [STACS'96] 的快速 2 倍独立乘 - 移位方案在这两种应用中效果不好。
Feb, 2013
提出使用有限独立哈希的新方法来解决 boolean satisfiability 问题,并基于此方法设计了两个实用算法:一个近似均匀生成器和一个可扩展的近似模型计数器,该方法具有强大的理论保证和可扩展性,可适用于不同的应用领域。
Apr, 2014
在计算机完全被妥协的情况下,本文讨论了基于共享文本源的熵集中、非二进制空间算术的流密码和从挑战文本生成密码的哈希算法等几种人类可计算算法在该情况下能够提供足够安全性,并通过计算机统计分析得出结论。
Dec, 2023
本文建立了 b 位最小哈希的理论框架,通过仅存储每个(最小化)哈希值的最低 b 位,可以在计算效率和存储空间方面获得相当大的优势,提供了任何 b 的相似度的无偏估计,即使在最不利的情况下,使用 b = 1 也可以将存储空间至少减少 21.3(或 10.7)倍,如果对相似度 > 0.5 感兴趣。
Oct, 2009
本文探讨了一种利用通用哈希和 SAT 求解器的方法,可以在不牺牲正确性保证的同时,处理具有数十万个变量的公式,解决了人工智能中受限采样和计数的两个基本问题,这对于概率推理及规划,约束随机验证等方面有着广泛应用,并探讨一些需要解决的挑战。
Dec, 2015
我们提出了一种随机算法,它通过解决一小部分带有随机生成校验约束的离散组合优化问题,从而在高概率下能够得到可靠的常数近似值,从而有效地逼近离散图模型的分区函数。
Feb, 2013
该研究论文探讨了如何通过增加短的随机奇偶约束来计算公式满足的真实赋值(模型),实现 NP 问题的计数,尤其是当需要添加多个约束时,随机奇偶约束的集合解的几何结构类似于纠错编码,得到了严格的数学保证。
Jul, 2017