Parallelization of FM-Index

Di Zhang, Yunquan Zhang, Shengfei Liu, Xiaodi Huang

Research output: Book chapter/Published conference paperConference paperpeer-review

2 Citations (Scopus)
310 Downloads (Pure)


A parallel design and implementation of FM-index is presented in this paper. In applications, the performance of the FM-index is crucial, which is a self-contained, highly compressed indexing algorithm. With the popularity of multi-core processors, parallel computing allows the FM-index to run faster by performing multiple computations simultaneously when possible. Our approach works by splitting input data into overlapping blocks with equal size, and running them through the FM-index algorithm simultaneously on multiple processors. After analyzing and refactoring the sequential version, we organize the data flows of all operations according to a unified parallel framework. The experimental results show that, in general our approach has achieved a significant and sub-linear speedup on widespread symmetrical multi-processing architectures. This will greatly reduce the running time of executing operations on large data sets.
Original languageEnglish
Title of host publicationIEEE International Conference on High Performance Computing and Communications
Place of PublicationUSA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages5
ISBN (Electronic)9780769533520
Publication statusPublished - 2008
EventHPCC 2008: 10th International Conference - Dalian, China, China
Duration: 25 Sep 200827 Sep 2008


ConferenceHPCC 2008: 10th International Conference


Dive into the research topics of 'Parallelization of FM-Index'. Together they form a unique fingerprint.

Cite this