FM-index分块并行算法及其实现  

Parallelization of Blocked FM-index Algorithm and Its Implementation

作　　者：李开士[1] 张云泉[2] 李玉成[2] 

机构地区：[1]中国科学院研究生院,北京100080 [2]中国科学院软件研究所并行计算实验室

出　　处：《计算机工程》2008年第8期53-54,58,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60303020);国家自然科学基金资助重点项目(60533020);国家重点基础研究发展计划基金资助项目(2005CB321702);国家“863”计划基金资助项目(2006AA01A102,2006AA01A125);中科院与审计署合作研究基金资助项目

摘　　要：查询海量数据有压缩和索引两种方法来提高速度,该文结合这两种方法提出了压缩查询的方法。FM-index是一种自索引的全文查询算法,存在内存占用过大的问题,对于复杂的查询效率也不理想。该文提出分块FM-index算法,在分块的基础上采用MPI对算法进行并行化,解决了内存占用过多的问题,达到了较好的并行效率。When dealing with massive volume data,there are two ways to achieve high performance：one is to compress and the other one is to build index.Combining these two methods,compressed query is proposed.FM-index is such a compressed self-index algorithm used for full-text query.The algorithm occupies a large amount of main memory and is unable to handle complex query efficiently.To deal with these problems,this paper proposes a blocked version FM-index algorithm and parallelizes it using MPI.The blocked algorithm greatly reduces its memory usage,while the parallel version of blocked FM-index algorithm achieves acceptable scalability.

关 键 词：压缩 自索引 FM-index算法 分块 并行 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]