原创《多维数据近似检索的分层LSH索引算法模型》：这是一篇与多维论文范文相关的免费优秀学术论文范文资料,为你的论文写作提供参考。
摘 要：该文鉴于数据管理技术发展的前瞻性考虑,以多维数据为处理对象,探索高性能數据过滤器的若干理论和实现技术,针对假阳性和假阴性过高的问题,以及对时空效率的要求,设计了适合多维数据近似检索的分层LSH索引算法模型.
关键词：多维数据；布鲁姆过滤器；局部敏感哈希；分层局部敏感哈希索引
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）02-0213-03
随着互联网、电子商务等信息技术的高速发展,数据规模呈海量增长,多个领域已经或正在积累TB、PB甚至EB级的大数据[1,2].如沃尔玛超市数据库超过2.5PB,每小时需要处理100余万条用户请求；社交网络Facebook存储了超过500亿张的照片；互联网数据资源每两年翻一番；全球的工业设备、汽车、电表上有无数的传感器,随时产生多种多样的海量数据信息.这些都标志着大数据时代已经来到,学术界、工业界和政府都已经开始密切关注大数据及其检索问题.
2012年美国奥巴马政府发布了“Big Data Research and DevelopmentInitiative”[3],投资2亿以上美元,计划在科学研究、环境、生物医学等领域利用大数据技术进行突破性研究,将“大数据战略”上升为国家战略.我国政府多部规划和项目指南都对“大数据”相关技术密切关注：《国家中长期科技发展规划纲要（2006-2020年）》提出“重点研究等海量信息处理及知识挖掘的理论与方法”；2014国家自然科学基金优先资助重点领域包括“大数据技术和应用中的挑战性科学问题”,并列出10个研究方向.
1 多维数据及其检索策略
信息存储空间的多元化给网络中数据资源的存储管理及新资源开发带来了新的挑战.大数据的存储与表示,大数据中知识快速且高效的挖掘是目前各互联网服务供应商关注的热点,普通网络用户也希望通过大数据获得更多的增值服务.数据量及数据复杂度急剧增长时,知识发现的难度及大大增加,计算量和响应时间也随之变化.研究与之对应的高效查询算法查找定位信息资源已经成为现代网络发展分布式信息共享中最常见的问题.精简结构的查询算法已经成为提升网络软件体系结构和完成大规模高效数据管理的关键.
由于大数据的数据体量巨大、类型繁多、价值大但有效信息比例低、要求处理速度快的特点,对当代信息传输、计算、存储以及面向各种应用的数据处理技术提出了前所未有的挑战.针对这些特征,学术界公认的大数据处理策略是先用过滤器快速过滤掉大部分无用的数据,留下可能有用的数据做进一步处理.但是,如何从静态或动态的海量数据中“提纯”出有价值的数据面临诸多困难,如：1）大数据时代的算法由于实时性的特点,其准确率不再是最主要指标,很多算法需要在实时性和准确率之间取得平衡；2）数据过滤必须更加谨慎,如果粒度过细,很容易将有用的信息过滤掉；如果过粗,又无法达到真正的清洗效果,因此需要在质和量之间仔细考虑和权衡.
大数据检索的实际应用中多采用近似查询,一般而言与目标距离越近,数据的价值就越高.为提高速度,可以设置一个多维数据过滤器,根据距离过滤掉大部分查询数据,少量剩下的数据可以再通过常规方法进一步处理,可以显著提高系统的整体性能.这个过滤器完成的就是近似成员查询（ApproximateMembership Query,AMQ）,即回答“查询对象q是否接近于数据集合中的某个对象”.现有AMQ技术主要是结合局部敏感哈希（Locality Sensitive Hashing,LSH）和布鲁姆过滤器（Bloom Filter,BF）设计的,如DSBF和LSBF.不过布鲁姆过滤器存在假阳性错误,局部敏感哈希算法需要大量的哈希表来建立索引结构,这就导致了大量的内存消耗,查询时也会带来大量的I/O访问.此外,尽管LSH的查询时间效率已经比较高了,但是依然存在进一步优化的空间.典型DSBF和LSBF这两个技术都有一个限制,即它们仅能过滤给定距离的AMQ查询.因此研究BF和LSH算法的特性,针对BF及LSH的缺点提出改进方案或者提出性能更优的相似性检索算法具有重要的研究意义.为了提出性能及适应性更好的相似性检索算法,以优化LSH结构、提升AMQ的质量和效率：设计多维数据近似检索的分层LSH索引算法模型.
2 基于BF及LSH的不同维度数据检索技术
布鲁姆过滤器（Bloom Filter,BF）是由B.H.Bloom在1970提出的经典过滤器[4],被广泛用在网络服务、数据包内容检测、信息检索、分布式数据库、协作缓存等领域.它对集合采用一个位串表示并能有效支持元素的哈希查找,对每个元素的表示只需要几个比特,是一种能够表示集合、支持集合查询的简洁数据结构,能够有效地过滤掉不属于集合的元素.布鲁姆过滤器结构的实质是将集合中的元素通过n个哈希函数映射到位串向量中,与传统的哈希查询算法中哈希存储表不同,布鲁姆过滤器中哈希表退化为一个位串,一个元素仅占用几个比特位.进行元素查询时,计算n个哈希函数,判断这个位串向量的n个对应比特位是否都为1.不过,布鲁姆过滤器作为一种集合查询的数据结构,在达到其高效简洁表示集合的同时,却存在可控的假阳性误判.
LSH技术是由P.Indyk等在1998年提出,它的思想是：先对数据集中的点进行哈希函数的映射,这样近距离点的冲突概率提高而远距离点的冲突概率降低.在查询时,将查询点按照相同的哈希函数哈希到桶中,然后取出桶中的所有点作为候选近似最近邻点,最后计算查询点与每个候选近似最近邻点的距离,通过该距离判断是否符合查询条件.使用哈希函数对整个数据集进行过滤,得到可能满足查询条件的点再计算距离,就避免点与数据集中所有点进行距离计算,提高了查询效率且无需降维.
2.1 单维数据布鲁姆过滤器
针对不同应用,布鲁姆过滤器有很多改进.计数布鲁姆过滤器CBF[5]将1位的比特扩展为3位或4位的计数器,能够处理元素删除操作.CBF可以正确地删除已经在集合中的元素,但如果这一先决条件不满足,就会产生假阴性（false negative）问题.为解决此问题,Guo等人[6]提出了一种新方案,在不减少0比特的情况下增加1比特,使得假阴性和假阳性一样减少.Time Decaying BF[7]在递减计数器值的同时也考虑时间因素.SBF[8]是另一个重复元素检测的解决方案,在SBF中0的预期分位数保持恒定,使得它适合在数据流中的重复检测,它还降低了假阳性和假阴性率.Space-code BF[9]关注测量精度、计算及存储复杂性之间的权衡.与标准的BF需要k次访问内存不同,Qiao等[10]提出Bloom-1只需要访问一次内存,他们还分析了不同的数据结构和性能,以获得查询代价和假阳性率都可接受的折中方案.
多维论文参考资料：
结论：多维数据近似检索的分层LSH索引算法模型为关于对写作多维论文范文与课题研究的大学硕士、相关本科毕业论文多维论文开题报告范文和相关文献综述及职称论文参考文献资料下载有帮助。
