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

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).