大规模动态后缀索引的高效率算法研究

Driven by the rapid development of modern information and network technologies, the amount of multi-source heterogeneous data is growing quickly, optimizing organization and pre-processing of the data are needed for the efficient management and use of data. Indexing is an important pre-processing method that is widely applied in the fields of data processing and storage management. An index built on a suffix array is usually termed as an SA index, it is a fundamental data structure for full-text search. This project researches efficient algorithms for massive dynamic suffix indices, these new algorithms are of advanced theoretic and practical performance and can be applied for online full-text search on massive heterogeneous data. In particular, the key algorithmic problems to be studied are: 1) Parallel algorithms for building an SA in shared internal memory; 2) Algorithms for building an SA in SSD external memory; 3) Algorithms for merging SAs in linear time; 4) Algorithms for building and checking an SA simultaneously; 5) Adaptive algorithms for building and merging SAs; 6) Algorithms for approximate search on SAs in external memory. The expected outcome includes: 6 international journal papers (not less than 3 papers on journals listed as CCF A) and 4 conference papers indexed by SCI/EI , 6 invention patent applications, 4 software copyright registrations; a full-text search prototype system for heterogeneous dynamic data of signals, logs, codes and genome.

随着现代信息和网络技术的快速发展，采集的多源异构数据规模迅速增大，有效管理和使用这些数据需要对其进行组织优化和预处理。索引是重要的预处理方法，广泛用于数据的处理和存储管理等领域。以后缀数组为核心的索引统称为SA索引，是全文搜索的重要数据结构。项目研发高效的大规模动态后缀索引算法，成果具有先进的理论和实际性能，可用于海量异构动态数据的在线全文搜索。围绕以下若干关键算法问题开展研究：1、共享内存SA构建并行算法；2、SSD的SA构建外存算法；3、线性时间的SA合并算法；4、同时构建和验证SA的算法；5、自适应的SA构建和合并算法；6、外存SA的模糊查找算法。预期成果：发表SCI/EI收录国际期刊论文6篇（CCF A类期刊论文3篇以上）和会议论文4篇，申请发明专利6个，登记软件著作版权4项；通用于信号、日志、代码和基因等异构动态数据的全文搜索原型系统。

以数据的后缀数组为核心的后缀索引是异构数据全文搜索的重要技术，构造后缀数组的关键任务是对数据的所有后缀进行排序，索引的构建和存储效率直接影响索引的可用性。项目研发高效的大规模动态后缀索引算法，成果具有先进的理论和实际性能，可用于海量异构动态数据的在线全文搜索。主要研究工作包括：（1）共享内存多核计算机上的并行后缀归纳排序算法；（2）多核计算机上用归纳排序方法同时构建和验证后缀数组；（3）外存计算模型上时间和空间高效的后缀排序算法；（4）多核计算机上节省空间的LZ77因子分解多线程并行算法；（5）支持大规模异构数据全文搜索的后缀索引系统；（6）以全文搜索系统增强HDFS用于海量小文件管理。取得以下研究成果：发表SCI/EI收录的国际学术期刊论文7篇、国际学术会议论文2篇；申请国家发明专利7项，已获得授权4项，公开3项；登记软件著作权4项；博士论文2篇、硕士论文4篇；研发了通用于信号、日志、代码和基因等异构动态数据的全文搜索系统、分布式海量小文件管理系统。