论文部分内容阅读
过去三十年,计算机硬件技术以令人惊奇的速度快速持续发展,已经极大地推动了数据库和信息工业发展。借助于技术的进步,数据以前所未有的速度产生。随着信息化程度的提高,数据已经超出了原始关系数据的范畴。大量新型应用服务如基于内容的图片检索等涌现,这直接使得各种新型应用数据如超文本、多媒体、交易数据等层出不穷。在实际数据建模时,大部分新型应用数据都可以建模成为高维数据(high-dimensional data),比如图像数据经过特征提取后可建模成高维空间中的特征向量,超市交易数据可建模成高维离散目录空间中的稀疏向量等。大量高维数据在众多的研究和应用领域扮演着越来越重要的角色。当前,对高维数据的查询处理研究,已经成为了学术界和产业界中一个重要课题。
本文紧跟当前国内外前沿研究,通过分析已有高维数据查询处理研究的不足,从实际应用需求出发,集中于高维不确定数据查询处理以及高维分布式数据相似查询处理两大研究点,面对其中许多难点包括高维不确定数据下的“维度灾难”、指数复杂度的概率值计算、对等网络下的高维“维度灾难”等,提出了一系列有效的解决方案,并使用大量实验验证了所提方法的有效性。
本文的主要研究内容分为两个部分。第一部分考虑到数据不确定性,利用可能世界语义来建模不确定数据,深入研究了高维概率阈值范围查询和高维概率集合包含查询。第二部分从数据的处理方式出发,主要研究对等网络分布式环境下的高维相似查询处理。本文的主要贡献及创新点如下:
(1)本文设计了一个基于数据单维映射的高维不确定数据概率阈值范围查询处理框架。该框架利用概率分位点作为概率剪枝信息的基本结构,可实现高性价比的概率剪枝。基于该高效的剪枝技术,该框架使用了面向高维不确定数据的数据映射机制,并基于该机制将高维不确定数据对象映射到一维数据空间,然后使用已有单维索引结构如B+树来索引高维数据对象。与此相适应,该框架使用了高维查询转换技术,将高维概率阈值范围查询转化成为若干个单维范围查询。同时,框架还运用了一个衡量分位点剪枝能力的数学模型,并借助了高效的分位点选取方法以选取“最优”剪枝能力的分位点集合以进行映射和索引。实验证明,与已有的技术相比,该框架可有效减少查询处理代价,并提高了查询效率。
(2)本文提出了面向高维不确定集值数据的集合包含查询以及设计了其高效的处理方法。首先,针对集值数据类型,本文提出了不确定模型以及两种新型概率包含语义:概率集合包含以及期望Jaccard包含。接着,本文提出了面向概率集合包含语义的高效计算方法,然后,基于所提的概率包含语义,本文进一步提出了两种重要的操作:概率阈值包含查询以及概率阈值包含连接,并设计了概率阈值集合包含查询和概率阈值集合包含连接的处理算法。最后,本文提出了面向期望Jaccard包含的高效计算方法。实验结果反映了所提查询处理方法的有效性。
(3)提出了一个查询代价可调的、支持高容错的、对等网络下的高维相似查询处理框架。该框架使用了一种能概括数据信息的简单结构,以有效地描述网络节点数据的聚类信息。该框架基于一种数据局部性保存的映射机制,使用了一个面向高维数据的分布式索引,有效地支持了节点数据发布和相似查询服务。基于该分布式索引,框架可以实现查询代价可调的高维相似查询处理,并在节点失效情况下仍能提供数据的可用性。该框架借助已有多探测技术,优化了分布式索引大小以及并实现了有效的查询负载均衡。本文在Chord中继网上实现了该框架。实验结果表明,该框架远远优于简单基于空间分区的高维查询处理方法。