论文部分内容阅读
在生物信息、电子商务等领域，随着离散无序（non-ordered discrete）数据规模的不断增长，有效的离散无序数据空间（non-ordered discrete data space，NDDS）索引技术正逐渐成为关注的热点。传统的单一加载（tuple loading，TL）技术已经不能满足数据规模的要求，加快索引构建速度的批量加载（bulk loading，BL）方法应运而生。近年来，并行计算技术快速发展，特别是处理大数据的并行计算框架的出现，使得并行模式在数据空间索引中受到越来越多的重视，并在许多实际应用中得到使用，大大提高了索引的构建性能和查询性能。本文在深入分析国内外连续数据空间（continuous data space，CDS）和NDDS索引以及并行批量加载技术的基础上，就以下内容进行了研究： 1）NDDS索引方法的分析与设计 分析了 NDDS中数据特性，并介绍了这种数据空间中重要的几何概念以及常用的查询类型，讨论了索引加载的相关技术，设计了一种NDDS中并行批量加载方法。 2）NDDS静态索引PND-tree及其拓扑结构 分析了NDDS中已有动态索引的结构，提出了NDDS中静态索引结构PND-tree，并根据先验知识对其拓扑结构进行了定义。 3）PND-tree的并行分割策略与过程 研究了NDDS中动态索引结构的分割策略，为PND-tree提出了基于启发式方法的多路分割策略，并描述了基于MapReduce的并行分割过程。 4）PND-tree的构建与实验分析 通过分割过程中获得的信息，自下而上地构建PND-tree；为了进行性能对比，使用基于缓冲的批量加载方法构建了BoND-tree。以基因数据的索引构建实验表明，本课题所设计的并行批量加载方法在不损失查询性能的情况下，其构建速度远远快于传统的索引构建方法。 综上，面向并行编程框架，设计并实现了NDDS并行批量加载算法，并通过实现算法验证了方法的有效性和正确性。