"这篇文献提出了一种快速近似最近邻搜索算法，名为Error Weighted Hashing (EWH)，适用于二进制的汉明空间。EWH算法在速度上比流行的局部敏感哈希（LSH）快20倍，并且即使在大最近邻距离下也能保持良好性能，而LSH在这种情况下可能失效。该算法通过根据哈希向量之间的差异对候选最近邻进行加权，显著减少了候选数量。EWH适用于基于二进制指纹的多媒体检索和复制检测系统。在包含超过1000个视频的指纹数据库上，EWH在特定检测精度下比LSH快10倍以上，同时在相同的检索时间内，EWH的检测准确度更高，错误率降低了15倍。"
在本文中，作者主要探讨了如何在大规模数据集上有效地执行最近邻搜索，这是一个在信息检索、图像识别、多媒体内容分析等众多领域中的核心问题。传统的搜索方法，如朴素的全库扫描，随着数据量的增加变得极其低效。因此，研究人员提出了各种近似搜索策略，其中最著名的一种是局部敏感哈希（LSH）。LSH利用哈希函数将高维数据投影到低维空间，使得相似的数据点有更高的概率映射到相同的哈希桶中。然而，LSH在处理较大最近邻距离时效率下降，因为需要检查的候选集过大。
文章提出的EWH算法则在LSH的基础上进行了改进。EWH的核心思想是不仅仅依赖于哈希碰撞来确定候选最近邻，而是引入了一个误差权重的概念。这个权重反映了两个哈希向量之间的汉明距离，即对应位不同的数量。通过这种方式，EWH能够优先考虑那些与查询点哈希值更接近的候选，从而减少误报率并提高检索效率。
EWH算法的实现步骤大致如下：
1. 首先，使用哈希函数将文件名转换为64位哈希值。
2. 然后，从每个64位哈希值中随机抽取4位，形成一个字串，根据这些字串将文件分配到不同的哈希桶中。
3. 查询时，同样对查询点进行哈希处理，抽取相同的位数，找出所有可能的匹配桶。
4. 对于每个桶，EWH不仅考虑桶内的所有字符串作为候选集，还使用汉明字典记录所有字串与其他字串的汉明距离，根据预设的权重范围选择候选最近邻。
5. 最后，通过对候选集应用误差权重，EWH能够减少需要检查的候选数量，从而提高搜索速度，同时保持较高的查全率和查准率。
在实验部分，EWH在包含大量视频指纹的数据库上展示了其优越性，对于特定的检测精度，它不仅运行速度快，而且错误率低，这使得EWH成为解决大规模数据集近似最近邻搜索问题的一个有力工具。
我的内容管理
展开
