基于LSH的Web数据相似性查询研究

论文摘要

随着Web技术的发展及其广泛应用,Web上涌现了海量的、格式繁多的数据。对这些数据的查询和管理成为Web应用的重要步骤。其中,相似性查询作为人们获取信息的重要手段,是Web数据管理的重要应用之一。Web数据和应用的多样性使得Web数据相似性计算也是多样化的。同时,Web数据的高维性给其相似性查询带来了新的挑战。为了平衡查询效率和查询效果,人们提出了相似性近似计算方案。位置敏感哈希（Locality Sensitive Hashing, LSH）作为相似性近似计算的最新技术,获得了广泛的研究并使用于诸多相似性查询的应用中。本文首先根据类型对Web数据进行了分类,综述了位置敏感哈希（Locality Sensitive Hashing, LSH）技术的研究现状,针对Web数据的特点和Web数据管理的挑战,本文使用位置敏感哈希技术对Web上的数据在以下三个方面进行了研究：在Hadoop平台上研究了大规模XML数据结构相似性查询：对于字符串数据,研究了基于Hash的字符串相似性连接；对文本数据相似性查询,提出了基于学习的相似性查询框架和算法。本文的主要贡献总结如下：1.在Hadoop平台上研究了大规模XML数据结构近似相似性查询。首先我们研究了XML树结构相似性计算、Hadoop集群的编程模式,接着研究了XML树结构信息提取技术pq-gram,并使用pq-gram对XML提取结构信息,我们在Hadoop集群上使用MapReduce实现了LSH索引,该索引可以支持大规模XML结构近似相似性查询。最后在真实数据集上,验证了我们的方法对XML结构相似性查询具有良好的查询性能和可扩展性。2.使用Min-hashing LSH技术提出了基于Hash的字符串近似相似性连接算法。我们首先研究了字符串相似性连接问题,分析了Trie-join相似性连接技术和真实数据集上相似性连接的特点,利用基于Min-Hashing的LSH提出了Hashed-Join,用于近似处理在编辑距离约束下字符串近似相似性连接。Hashed-Join首先把字符串数据使用LSH进行分组聚类,进而在各个组内使用Trie-Join技术进行相似性连接。该算法可以方便地扩展到分布式平台处理大规模的字符串相似性连接。最后本文通过在真实数据集上的实验分析和对比,证实了本文提出方法具有更好的连接性能和可扩展性。3.提出了基于学习的相似性查询算法。本文在研究分析LSH的随机投影（Random Projection）技术的基础上，证明了高维数据随机投影之后的二进制编码满足语义哈希的要求。把二元编码用作数据的类标号,提出了基于学习的高维数据相似性查询框架和算法。在该框架下,研究了近似k-最近邻查询和c-近似最近邻查询。通过实验验证和分析,证实了本文的方法与现有方法相比,不仅减少了编码长度、降低了数据预处理的时间和空间代价,而且提高了查询效率综上所述,本文结合Web数据的特点,使用位置敏感哈希技术解决Web数据相似性查询问题,主要的工作包括：使用MapReduce实现了大规模XML数据结构相似性查询；提出了基于Hash的字符串相似性连接算法；提出了基于学习的相似性查询架构和算法。本文对以上提出的算法在真实数据集上进行了实验,验证了效率、效果和可扩展性。

论文目录

• 摘要
• Abstract
• 目录
• 图目录
• 表目录
• 第一章 绪论
• 1.1 引言
• 1.2 研究背景
• 1.2.1 数据密集型计算的兴起
• 1.2.2 Web数据的特点
• 1.2.3 相似性查询
• 1.2.4 Web数据的相似性计算
• 1.3 本文的主要工作
• 1.3.1 XML结构相似性近似查询
• 1.3.2 字符串相似性连接近似查询
• 1.3.3 基于学习的相似性查询
• 1.4 本文的结构
• 第二章 基础知识
• 2.1 数学基础
• 2.1.1 图论
• 2.1.2 熵
• 2.1.3 代数
• 2.2 位置敏感哈希
• 2.2.1 常用的相似性度量
• 2.2.2 位置敏感哈希原理
• 2.2.3 位置敏感哈希的定义
• 2.2.4 位置敏感哈希过程
• 2.3 位置敏感哈希种类
• 2.3.1 Min-Hashing
• 2.3.2 随机投影
• p范数的位置敏感哈希'>2.3.3 L_p范数的位置敏感哈希
• 2.4 LSH的限制与改进
• 2.5 LSH的应用
• 2.6 本章小结
• 第三章 基于MapReduce的XML结构相似性查询
• 3.1 问题定义
• 3.1.1 XML模型
• 3.1.2 树编辑趴离
• 3.1.3 pq-gram
• 3.2 集群计算Hadoop
• 3.2.1 HDFS
• 3.2.2 MapReduce
• 3.3 基于LSH的XML结构相似性计算
• 3.4 处理架构
• 3.5 算法
• 3.6 实验结果
• 3.6.1 实验环境
• 3.6.2 数据集
• 3.6.3 查询处理的性能
• 3.6.4 查询质量
• 3.6.5 扩展性
• 3.7 相关工作
• 3.8 本章小结
• 第四章 基于Hash的字符串近似相似性连接
• 4.1 问题定义
• 4.1.1 q-gram
• 4.1.2 字符串相似性度量
• 4.2 字符串Trie-Join
• 4.2.1 Trie Join
• 4.2.2 现象观察
• ed-Join处理'>4.3 Hash^ed-Join处理
• 4.3.1 处理框架
• 4.3.2 处理算法
• 4.4 实验
• 4.4.1 实验环境
• 4.4.2 数据集
• 4.4.3 连接性能
• 4.4.4 连接质量
• 4.4.5 扩展性能
• 4.5 相关工作
• 4.6 本章小结
• 第五章 基于学习的近似相似性查询
• 5.1 问题定义
• 5.1.1 近似k-近邻查询
• 5.1.2 c-近似最近邻查询
• 5.1.3 随机投影
• 5.1.4 熵最大化准则
• 5.1.5 支持向量机分类器
• 5.2 近似相似性查询
• 5.2.1 理论证明
• 5.2.2 处理流程
• 5.2.3 相关算法
• 5.2.4 复杂性分析
• 5.3 实验
• 5.3.1 实验设置
• 5.3.2 实验数据集
• 5.3.3 近似k-最近邻查询
• 5.3.4 c-近似最近邻查询
• 5.4 相关工作
• 5.5 本章小结
• 第六章 结论与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 附录
• 致谢