外存全文索引算法的研究

摘要

对数据建立索引并提供检索功能是人们面对海量数据时的基本要求，在互联网时代尤为如此。在数据库中检索所需要的记录，在web信息中搜索符合自己要求的网页都需要对数据建立索引结构，对于法律文件，生物信息学中的DNA数据更需要支持全文匹配功能。索引结构包括外存索引和内存索引结构。对于后缀树和后缀数组等经典数据结构来说，虽然匹配速度快，但占用空间很大。压缩全文索引如CSA与FM-Index不适用于外存结构。
　　本文提出了一种空间和时间高效的外存压缩索引mKD-GBWT。理论上，mKD-GBWT压缩索引所占空间为O(nlogσ)位；可在O(|P|/B+√n/B+occ/B)I/Os内支持模式匹配查询，其中|P|为模式长度，n为文本规模，n为字符表大小，B为磁盘块大小。
　　本文提出了mKD-GBWT中高效外存串B-树算法、kd-树的外存存储结构及其正交范围查找算法；然后详细描述了mKD-GBWT采用多棵kd-树作为其正交范围查找结构的原理及其模式匹配算法；分析了mKD-GBWT索引的时空性能，最后高效地实现了mKD-GBWT索引；并针对各类数据（如分布均匀数据、有偏数据、高度重复数据等）进行了较为广泛的实验，实验表明，与2015年最新外存压缩索引GBWT相比，所提算法在实际中不仅存储空间高效，而且具有良好的I/O性能。
　　在工程方面，为了降低索引大小，本文提出采用crit-bit树作为串B-树中一个节点的数据结构，利用串B-树存储静态数据的特点将串B-树按照从左至右自底向上的顺序存储，避免了显式存储串B-树每个内部节点中的孩子指针，同时改进了kd-树的外存序列化算法提高了存储kd-树的磁盘页的空间利用率。为了提高查询效率，本文首先改进了串B-树的后缀范围查找算法避免了对搜索过程中重叠路径上节点的重复访问，然后利用mKD-GBWT模式匹配过程中所需要查询的正交范围只会位于一个划分的子区间内的特点，提出采用多棵kd-树作为mKD-GBWT索引的正交范围查找结构，每棵kd-树仅存储部分点集，这样在进行正交范围查找时只需要在其中一棵kd-树中进行，从而提高了查询效率。本文还对串B-树和kd-树的构造算法进行了改进，利用文本的最长公共前缀信息减少串B-树的构造时间，改进了kd-树的内部节点中点的分割算法使得构造的内存kd-树更适合磁盘序列化操作。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 引言

1.1 研究背景及意义

1.2 研究现状

1.3 本文主要工作

第二章 预备知识

2.1 基本概念

2.2 内存索引结构

2.3 外存数据结构

2.4 GBWT-索引

2.5 本章小结

第三章 mKD-GBWT索引

3.1 mKD-GBWT索引基本原理

3.2 外存串B-树的实现

3.3 外存kd-树的实现

3.4 mKD-GBWT索引的性能分析

3.5 本章小结

第四章 实验结果与分析

4.1 实验环境和测试数据

4.2 串B-树性能测试

4.3 外存kd-树性能测试

4.4 mKD-GBWT索引性能测试

4.5本章小结

第五章 总结与展望

5.1 总结

5.2 进一步的工作

参考文献

致谢

作者简介

1. 基本情况

2. 教育背景

3. 攻读硕士学位期间科研成果