云计算系统中索引与查询处理技术研究

哈尔滨工业大学  王金宝

本文的研究工作针对云计算系统中的查询处理技术和索引技术，运用数据管理技术、计算复杂性和算法学的理论和知识，针对云计算系统中不同查询类型的处理算法和不同的数据类型的索引技术进行研究。本文的主要研究工作包括以下方面：首先，本文提出了云计算系统中的多维索引结构。本文针对云计算系统中的多维数据提出点查询、范围查询和k最近邻查询的处理算法，包括计算节点之间的分布式算法和计算节点内部的索引选择算法。真实云计算平台中的实验验证了本文提出的云计算多维索引结构的有效性。第二，本文提出了云计算系统中字符串相似性查询的算法。为了减少查询在系统中使用计算节点的数量，本文设计了基于字符向量的数据划分方法，用于划分字符串数据集合。该方法将相似的字符串划分到相同的计算节点中，并在查询处理过程中确定查询需要访问的计算节点集合。第三，本文提出了云计算系统中空间近似关键字查询算法。本文给出了全局索引选择方法，用于全局索引的初始化和周期性维护。在查询处理方面，本文给出了基于编辑距离的范围近似关键字查询和最近邻近似关键字查询的算法。在分布式集群中的实验结果验证了本文提出的索引结构的有效性。第四，本文提出了云计算系统中多维聚集查询处理算法。针对以上问题，本文提出了云计算系统中的多维聚集操作方案，通过两层索引结构减少参与查询的计算节点以及单个计算节点中聚集操作计算量。本文给出了使用两层索引结构处理多维聚集查询的算法框架，并在该框架中提出了性能优先模式和低功耗模式下的多维聚集查询算法。在两种模式下的多维聚集算法中提出了查询分配问题，并证明了两种模式中查询分配问题都是NP完全问题。本文给出解决两个NP完全问题的近似算法，并证明了两个近似算法的近似比。理论证明分析和模拟实验结果验证了本文提出的多维聚集查询方案的有效性。

云计算系统中索引与查询处理技术研究