论文部分内容阅读
近年来,随着通信技术和智能移动终端的发展和普及,在许多应用和网站中越来越多的网络用户从单纯的信息“消费者”变成了信息的“生产者”和“传播者”,如微博、博客、微视频等应用。互联网中信息的数据量在飞速增长的同时数据的类型呈现多样化的趋势,基于此用户享受到更加便捷的服务,如基于地理位置的服务,语音查询、图片查询等。面对大规模数据和复杂的数据类型,如何进行有效的管理成为数据库领域的研究热点。本文深入研究了分布式环境下多种数据类型的相似性查询的相关问题,提出了针对各种数据类型的分布式查询框架,进一步提出了相应的NN查询、kNN、RkNN等相似性查询算法。本文的贡献点可概括如下。(1)针对支持树型索引的数据类型,首先,通过分析树型索引的共性特征,包括B-tree、M-tree、R-tree等,提出一种基于Chord拓扑支持树型索引的框架。之后在该框架下,为了协调分布式环境中的查询操作和更新操作,可以根据查询更新模式动态调整索引节点的副本数量,从而实现在更新代价较低的情况下尽可能地提高查询的效率。并进一步提出了范围查询算法和kNN查询算法。最后,为了进一步提高查询性能和更新效率,基于该分布式查询框架提出了动态索引优化方法。(2)针对空间文本混合数据类型,首先,结合空间文本数据类型的相似度计算的特征,提出了一种混合索引方法一hybrid-LSH,hybrid-LSH可以同时考虑空间相似度和文本相似度,以较大概率将相似的数据对象哈希到一个桶中,从而减少I/O代价,并从理论上分析了 hybrid-LSH的准确性和有效性。其次,提出了可以处理变化查询范围的适应性的NN查询算法和kNN算法。最后,结合云计算技术,将算法扩展到分布式环境中,因为hybrid-LSH避免了传统方法的对对比较,而只在各个哈希桶内进行计算,从而大量地节省了计算代价和网络代价。(3)针对带有关联关系的数据类型,首先,通过分析带有关联关系的数据类型的特征,提出了高效的面向该数据类型的分布式管理和查询框架。其次,通过分析决策树计算的特征,提出了高效的分布式决策树计算方法,该方法不需要对数据进行全局排序,而是只需要传输部分数据即可计算出满足质量的约近分裂点,通过理论分析证明了该方法约近的准确性和在计算复杂度方面的高效性。最后,在该框架下提出了基于决策树的相似性查询算法,该算法不需要比较所有的属性即可得出查询结果,从而节省了计算代价。(4)针对不确定性的文本数据类型,首先,通过分析不确定文本数据的余弦相似度计算的特征,提出了高效的相似度计算方法和改进的索引结构sMVP-tree。其次,因为余弦距离不属于度量距离函数,很难对数据构建索引,而且传统的方法主要侧重于集中式环境,本文通过对余弦距离计算进行转换并提出了基于余弦相似度面向不确定性文本数据的相似性查询框架。最后,给出了基于sMVP-tree的查询过滤方法,并结合该相似性查询框架提出了分布式环境下面向不确定文本数据类型的kNN查询和RkNN查询算法。