File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: A space and time efficient algorithm for constructing compressed suffix arrays
  • Basic View
  • Metadata View
  • XML View
TitleA space and time efficient algorithm for constructing compressed suffix arrays
 
AuthorsHon, WK2
Lam, TW2
Sadakane, K1
Sung, WK3
Yiu, SM2
 
KeywordsCompression
Construcion
Pattern mathching
Text indexing
 
Issue Date2007
 
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
 
CitationAlgorithmica (New York), 2007, v. 48 n. 1, p. 23-36 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00453-006-1228-8
 
AbstractWith the first human DNA being decoded into a sequence of about 2.8 billion characters, much biological research has been centered on analyzing this sequence. Theoretically speaking, it is now feasible to accommodate an index for human DNA in the main memory so that any pattern can be located efficiently. This is due to the recent breakthrough on compressed suffix arrays, which reduces the space requirement from O(n log n) bits to O(n) bits. However, constructing compressed suffix arrays is still not an easy task because we still have to compute suffix arrays first and need a working memory of O(n log n) bits (i.e., more than 13 gigabytes for human DNA). This paper initiates the study of constructing compressed suffix arrays directly from the text. The main contribution is a construction algorithm that uses only O(n) bits of working memory, and the time complexity is O(n log n). Our construction algorithm is also time and space efficient for texts with large alphabets such as Chinese or Japanese. Precisely, when the alphabet size is |∑|, the working space is O(n log |∑|) bits, and the time complexity remains O(n log n), which is independent of |∑|. © Springer 2007.
 
ISSN0178-4617
2013 Impact Factor: 0.567
 
DOIhttp://dx.doi.org/10.1007/s00453-006-1228-8
 
ISI Accession Number IDWOS:000246152800002
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorHon, WK
 
dc.contributor.authorLam, TW
 
dc.contributor.authorSadakane, K
 
dc.contributor.authorSung, WK
 
dc.contributor.authorYiu, SM
 
dc.date.accessioned2010-09-06T09:50:31Z
 
dc.date.available2010-09-06T09:50:31Z
 
dc.date.issued2007
 
dc.description.abstractWith the first human DNA being decoded into a sequence of about 2.8 billion characters, much biological research has been centered on analyzing this sequence. Theoretically speaking, it is now feasible to accommodate an index for human DNA in the main memory so that any pattern can be located efficiently. This is due to the recent breakthrough on compressed suffix arrays, which reduces the space requirement from O(n log n) bits to O(n) bits. However, constructing compressed suffix arrays is still not an easy task because we still have to compute suffix arrays first and need a working memory of O(n log n) bits (i.e., more than 13 gigabytes for human DNA). This paper initiates the study of constructing compressed suffix arrays directly from the text. The main contribution is a construction algorithm that uses only O(n) bits of working memory, and the time complexity is O(n log n). Our construction algorithm is also time and space efficient for texts with large alphabets such as Chinese or Japanese. Precisely, when the alphabet size is |∑|, the working space is O(n log |∑|) bits, and the time complexity remains O(n log n), which is independent of |∑|. © Springer 2007.
 
dc.description.natureLink_to_subscribed_fulltext
 
dc.identifier.citationAlgorithmica (New York), 2007, v. 48 n. 1, p. 23-36 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00453-006-1228-8
 
dc.identifier.citeulike4736346
 
dc.identifier.doihttp://dx.doi.org/10.1007/s00453-006-1228-8
 
dc.identifier.epage36
 
dc.identifier.hkuros128171
 
dc.identifier.isiWOS:000246152800002
 
dc.identifier.issn0178-4617
2013 Impact Factor: 0.567
 
dc.identifier.issue1
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-34547375123
 
dc.identifier.spage23
 
dc.identifier.urihttp://hdl.handle.net/10722/88951
 
dc.identifier.volume48
 
dc.languageeng
 
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
 
dc.publisher.placeUnited States
 
dc.relation.ispartofAlgorithmica (New York)
 
dc.relation.referencesReferences in Scopus
 
dc.subjectCompression
 
dc.subjectConstrucion
 
dc.subjectPattern mathching
 
dc.subjectText indexing
 
dc.titleA space and time efficient algorithm for constructing compressed suffix arrays
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Hon, WK</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Sadakane, K</contributor.author>
<contributor.author>Sung, WK</contributor.author>
<contributor.author>Yiu, SM</contributor.author>
<date.accessioned>2010-09-06T09:50:31Z</date.accessioned>
<date.available>2010-09-06T09:50:31Z</date.available>
<date.issued>2007</date.issued>
<identifier.citation>Algorithmica (New York), 2007, v. 48 n. 1, p. 23-36</identifier.citation>
<identifier.issn>0178-4617</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/88951</identifier.uri>
<description.abstract>With the first human DNA being decoded into a sequence of about 2.8 billion characters, much biological research has been centered on analyzing this sequence. Theoretically speaking, it is now feasible to accommodate an index for human DNA in the main memory so that any pattern can be located efficiently. This is due to the recent breakthrough on compressed suffix arrays, which reduces the space requirement from O(n log n) bits to O(n) bits. However, constructing compressed suffix arrays is still not an easy task because we still have to compute suffix arrays first and need a working memory of O(n log n) bits (i.e., more than 13 gigabytes for human DNA). This paper initiates the study of constructing compressed suffix arrays directly from the text. The main contribution is a construction algorithm that uses only O(n) bits of working memory, and the time complexity is O(n log n). Our construction algorithm is also time and space efficient for texts with large alphabets such as Chinese or Japanese. Precisely, when the alphabet size is |&#8721;|, the working space is O(n log |&#8721;|) bits, and the time complexity remains O(n log n), which is independent of |&#8721;|. &#169; Springer 2007.</description.abstract>
<language>eng</language>
<publisher>Springer New York LLC. The Journal&apos;s web site is located at http://link.springer.de/link/service/journals/00453/index.htm</publisher>
<relation.ispartof>Algorithmica (New York)</relation.ispartof>
<subject>Compression</subject>
<subject>Construcion</subject>
<subject>Pattern mathching</subject>
<subject>Text indexing</subject>
<title>A space and time efficient algorithm for constructing compressed suffix arrays</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0178-4617&amp;volume=48:1&amp;spage=23&amp;epage=36&amp;date=2007&amp;atitle=A+Space+and+Time+Efficient+Algorithm+for+Constructing+Compressed+Suffix+Arrays+</identifier.openurl>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1007/s00453-006-1228-8</identifier.doi>
<identifier.scopus>eid_2-s2.0-34547375123</identifier.scopus>
<identifier.hkuros>128171</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-34547375123&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>48</identifier.volume>
<identifier.issue>1</identifier.issue>
<identifier.spage>23</identifier.spage>
<identifier.epage>36</identifier.epage>
<identifier.isi>WOS:000246152800002</identifier.isi>
<publisher.place>United States</publisher.place>
<identifier.citeulike>4736346</identifier.citeulike>
</item>
Author Affiliations
  1. Kyushu University
  2. The University of Hong Kong
  3. National University of Singapore