位置敏感哈希算法的性能分析研究

被引量 : 3次 | 上传用户:daidaide21
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着大数据时代的来临,在诸如图像与多媒体数据库、地理信息系统、数据挖掘与分析系统等海量数据应用系统中,都需要在大数据集中进行最近邻查找,即查找出与给定查询对象最为相似的一个或一组对象。最近邻查找问题在低维空间已经有较为有效的解决方案,而在高维数据空间,由于“维度灾难”的存在使得最近邻查找问题变得非常困难,目前解决这一问题最有效的技术是建立高维索引。现有高维索引主要分为树结构索引和基于哈希的索引两类。树结构索引技术通过对空间进行划分建立树形的辅助查询结构,在数据维度较低时,效果较好。当维度超过数十维后,树结构索引容易产生索引空间重叠问题,导致索引占用空间大且时间效率低。在基于哈希的索引技术中,利用查询对象哈希函数值可以在次线性时间内查找到与其较为相似对象,因而得到广泛的研究和应用。在广泛阅读国内外参考文献的基础上,本文对位置敏感哈希算法进行了系统的研究。在研究中,我们发现位置敏感哈希理论与基于该理论的算法实现有着本质差别,而这一差别导致应用传统性能分析方法所得到的分析结论是不正确的。为此,本文从位置敏感哈希算法性能分析入手开展研究工作,论文工作包括:(1)阐述了位置敏感哈希理论和基于该理论的算法实现间的本质区别。使用真实数据集对位置敏感哈希算法的理论性能与实际性能进行对比分析,在实验上验证了二者是完全不同的。(2)传统位置敏感哈希算法性能分析所基于的前提在实际应用中并不存在,因而会导致理论分析结果与实际性能不符合。在实验中表现为位置敏感哈希算法的召回率会在理论值附近上下波动,而非精确相等。为此,我们提出了新的位置敏感哈希算法性能分析模型,该模型能精确地预测算法的实际性能。(3)为了验证新模型的有效性,在E2LSH代码的基础上,完成了基于位置敏感哈希理论的两种算法实现——LSHN和LSHC。使用Mnist、Color、Audio等高维数据集,通过实验比较了LSHN和LSHC的召回率和碰撞率。实验结果表明,传统性能分析方法得到的结果与实际算法性能有不小的差距,而本文所提出的新模型则准确的预测了算法在实际应用中的表现。
其他文献
白血病是一种基因组发生动态变化的造血干/祖细胞疾病。染色体易位和/或基因突变是常见的遗传学异常。近来,研究提示白血病的发生遵循"多次打击"模式。在慢性粒细胞白血病中,
检务保障是检察执法公信力的重要保障,对检察机关履行法律监督职能具有重要的制度价值。本文在对检务保障的法律内涵与法律价值进行分析的基础上,研究分析检务保障在宪政要求
写作提纲,是对所写的文章进行构思后记下的内容要点,它在写作中具有指导性,十分重要。不少中学生作文时都没有写提纲的好习惯:有的不懂得写提纲的重要性,怕耽误时间,会写而不写;更多
期刊
在急性冠脉综合征的人群中,不良事件的风险是随着年龄的增加而增加的。据统计,尽管ACS人群中75岁以上人群仅占6%,但是75岁以上的死亡率却占了总体死亡率的65%。既往有研究显
期刊
制造业作为国家的支柱产业,其发展前景与国家的国民经济息息相关。而面向订单装配作为现代制造业重要的生产模式应用也越来越广泛。伴随着计算机技术、自动化技术、网络通讯技
作为创新性的基础,批判性思维已成为了许多国家教育研究的热点之一。在我国课程改革过程中,批判性思维的培养也成为了高职人才培养的重要目标。英语学科的学科特点尤其阅读环节
目的研究综合护理干预在肺结核合并糖尿病医院感染控制中的应用效果。方法选取该院2013年11月—2014年11月收治的肺结核合并糖尿病患者62例,按照数字随机法随机分成观察组和
目的:研究新疆软紫草多糖(ARPS)对环磷酰胺(CTX)致小鼠免疫功能低下的影响。方法:采用腹腔注射CTX制造小鼠免疫损伤模型,同时应用软紫草多糖100(低)、200(中)、300(高)mg·kg
目的:建立壮药白金颗粒中薯蓣皂苷元的含量测定方法.方法:采用C18色谱柱(ODS-3,250 mm'4.6 mm,5μm),甲醇-水(89∶11)为流动相,检测波长为203 nm,流速为1ml/min,柱温为35℃,进样量为
随着视频监控规模的不断扩大,仅仅使用人力对成千上万的监控摄像头进行在线监视、对海量监控视频进行分析已经不能满足需求。由于智能监控不需要在人为干预情况下对摄像机采