大规模序列数据集的压缩索引与搜索算法研究

Proliferation of data at massive scales poses serious new challenges in terms of storing, managing, retrieving, and mining intelligent information from data. Aimed at improving the performance of storing, indexing and searching for large-scale data as the basic goal, we focus in this project on proposing space-efficient wavelet tree construction and developing generic library package of wavelet trees, hoping to offer the supports in the data structures for large-scale applications. Secondly, based on the wavelet tree, the efficient compressed representation of neighbor function phi of compressed suffix array is established and space-efficient compressed suffix array construction algorithm is proposed. Thirdly, we create the wavelet tree construction algorithm in external memory so that each rank and select can be done in logarithmic time with base B, where B is the block transfer size in the external memory model. Fourthly, combining various approximation metrics like edit distance and hamming distance, we establish an I/O efficient compressed index, supporting phrases searching and top-k query. Finally, we develop a prototype for the large-scale text retrieval system in external memory on TPIE. The project will build new theoretical foundations in the field of massive data processing, with applications to fields like databases and information retrieval. It will drive forward current state of the art in web search engine technology (by impacting the way inverted indexes are used).

大规模数据的激增为存储、管理、检索和从数据挖掘智能信息提出了新的挑战。本项目以改善大规模数据的存储、索引和搜索的性能为基本目标，首先，提出空间高效的小波树构造算法，开发出小波树构造通用类库，为大规模数据处理应用研究提供数据结构上的支持；其次，建立基于小波树的压缩后缀数组近邻函数phi的高效压缩表示方法，提出空间高效的压缩后缀数组构造算法；再次，提出外存模型上的小波树构造算法，达到rank和select操作可在以B为底的对数时间内完成，其中B为外存模型中的块传输大小；然后，结合多种近似测度（如编辑距离、海明距离），建立I/O高效的支持短语搜索的压缩索引，回答top-k查询；最后，基于TPIE平台，开发外存模型上的压缩索引系统原型。该项目将在大规模数据处理领域建立新的理论，并可应用于数据库和信息检索等领域。这将有望推动Web搜索引擎技术（影响倒排索引的使用方式）。

(1) 项目的背景. 大数据的激增为存储、检索和从数据搜索可用信息提出了新的挑战。项目期望从压缩索引这样一个新的视觉来研究大数据的存储、检索和搜索问题。这包括大规模文本数据集的压缩索引的基础理论与方法、简明数据结构设计、压缩索引上的高效模式查询。.(2) 主要研究内容. 本项目主要研究大规模文本数据集的压缩索引的基本理论与方法；建立空间高效的压缩索引理论框架，提出高效的压缩后缀数组构造算法及支持高效查询的简明数据结构。.(3) 重要结果. 在压缩索引的基础理论和方法方面做出了较好的工作。主要包括：提出了一种高阶熵压缩的全文自索引，压缩索引占用2nHk + n + o(n)位的空间；提出了线性时间压缩索引构造算法。建立了基于BWT变换和小波树的最优压缩索引构造理论框架，压缩索引使用nHk + o(n) log \sigma + o(nHk)位的空间；提出了压缩索引上高效的查询算法。提出了首个实用外存简明文本索引，该索引占用O(n log \sigma)位的空间，执行一次模式匹配查询最坏情况下的I/O复杂度为O(|P|/B + log_B n log_\sigma n + √(n/B) + occ/B)，其中B是磁盘块大小，occ是输出点数。建立了图数据库搜索的压缩数据结构理论。.(4) 关键数据及科学意义. 我们在本领域重要刊物IEEE/ACM Transactions on Computational Biology and Bioinformatics (JCR = 2)和BMC Bioinformatics (JCR = 2)，重要会议IEEE Data Compression Conference (CCF B类会议)和ACM-SIAM Proceedings of the Algorithm Engineering and Experiments (ALENEX) (算法工程重要会议)等发表了15篇论文（其中10篇为刊物论文，5篇为会议论文），SCI检索8篇，EI检索7篇。此外，还有3篇论文已投顶级刊物在审。开发了可在GitHub上访问的压缩索引软件.（https://github.com/hongweihuo-lab）。这些研究成果为进一步研究大规模图数据库的压缩索引与搜索，高通量测序数据集的结构模式发现，在基因组水平上探索基因的表