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

项目名称： 大规模序列数据集的压缩索引与搜索算法研究

项目编号： No.61373044

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 霍红卫

作者单位： 西安电子科技大学

项目金额： 75万元

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

中文关键词： 压缩索引；简明数据结构；BWT变换；小波树；外存

英文摘要： 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

英文关键词： Compressed indexes；Succinct data structures；Burrows-Wheeler transform；Wavelet trees；External memory