Access Restriction

Author Dementiev, Roman ♦ Krkkinen, Juha ♦ Mehnert, Jens ♦ Sanders, Peter
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Algorithm engineering ♦ I/O-efficient ♦ Algorithms for strings ♦ External memory ♦ Large data sets ♦ Secondary memory ♦ Suffix array
Abstract Suffix arrays are a simple and powerful data structure for text processing that can be used for full text indexes, data compression, and many other applications, in particular, in bioinformatics. However, so far, it has appeared prohibitive to build suffix arrays for huge inputs that do not fit into main memory. This paper presents design, analysis, implementation, and experimental evaluation of several new and improved algorithms for suffix array construction. The algorithms are asymptotically optimal in the worst case or on average. Our implementation can construct suffix arrays for inputs of up to 4-GB in hours on a low-cost machine. As a tool of possible independent interest, we present a systematic way to design, analyze, and implement $\textit{pipelined}$ algorithms.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-08-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 12
Page Count 24
Starting Page 1
Ending Page 24

Open content in new tab

   Open content in new tab
Source: ACM Digital Library