论文部分内容阅读
随着大数据时代的来临,在诸如图像与多媒体数据库、地理信息系统、数据挖掘与分析系统等海量数据应用系统中,都需要在大数据集中进行最近邻查找,即查找出与给定查询对象最为相似的一个或一组对象。最近邻查找问题在低维空间已经有较为有效的解决方案,而在高维数据空间,由于“维度灾难”的存在使得最近邻查找问题变得非常困难,目前解决这一问题最有效的技术是建立高维索引。现有高维索引主要分为树结构索引和基于哈希的索引两类。树结构索引技术通过对空间进行划分建立树形的辅助查询结构,在数据维度较低时,效果较好。当维度超过数十维后,树结构索引容易产生索引空间重叠问题,导致索引占用空间大且时间效率低。在基于哈希的索引技术中,利用查询对象哈希函数值可以在次线性时间内查找到与其较为相似对象,因而得到广泛的研究和应用。在广泛阅读国内外参考文献的基础上,本文对位置敏感哈希算法进行了系统的研究。在研究中,我们发现位置敏感哈希理论与基于该理论的算法实现有着本质差别,而这一差别导致应用传统性能分析方法所得到的分析结论是不正确的。为此,本文从位置敏感哈希算法性能分析入手开展研究工作,论文工作包括:(1)阐述了位置敏感哈希理论和基于该理论的算法实现间的本质区别。使用真实数据集对位置敏感哈希算法的理论性能与实际性能进行对比分析,在实验上验证了二者是完全不同的。(2)传统位置敏感哈希算法性能分析所基于的前提在实际应用中并不存在,因而会导致理论分析结果与实际性能不符合。在实验中表现为位置敏感哈希算法的召回率会在理论值附近上下波动,而非精确相等。为此,我们提出了新的位置敏感哈希算法性能分析模型,该模型能精确地预测算法的实际性能。(3)为了验证新模型的有效性,在E2LSH代码的基础上,完成了基于位置敏感哈希理论的两种算法实现——LSHN和LSHC。使用Mnist、Color、Audio等高维数据集,通过实验比较了LSHN和LSHC的召回率和碰撞率。实验结果表明,传统性能分析方法得到的结果与实际算法性能有不小的差距,而本文所提出的新模型则准确的预测了算法在实际应用中的表现。