File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Compressed indexes for approximate string matching

TitleCompressed indexes for approximate string matching
Authors
KeywordsApproximate String Matching
Compressed Index
Issue Date2010
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica (New York), 2010, v. 58 n. 2, p. 263-281 How to Cite?
Abstract
We revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k ) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log∈nlog∈log∈n) time. The previously best solution achieving this time complexity requires an index of O(nlog∈n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog∈nlog∈log∈n+occ) time, and k-error matching, for any k>2, in O(m k-1log∈nlog∈log∈n+occ) time. © 2008 Springer Science+Business Media, LLC.
DescriptionResult in this paper has appeared in a preliminary form in the Proceedings of the 14th Annual European Symposium (ESA 2006), see this record in hub (with postprint fulltext): http://hub.hku.hk/handle/10722/92634
Persistent Identifierhttp://hdl.handle.net/10722/152439
ISSN
2013 Impact Factor: 0.567
ISI Accession Number ID
Funding AgencyGrant Number
Hong Kong RGCHKU 7140/06E
Funding Information:

The research T.-W. Lam was supported by the Hong Kong RGC Grant HKU 7140/06E.

References
Grants

 

Author Affiliations
  1. The University of Hong Kong
  2. National University of Singapore
DC FieldValueLanguage
dc.contributor.authorChan, HLen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorSung, WKen_US
dc.contributor.authorTam, SLen_US
dc.contributor.authorWong, SSen_US
dc.date.accessioned2012-06-26T06:39:05Z-
dc.date.available2012-06-26T06:39:05Z-
dc.date.issued2010en_US
dc.identifier.citationAlgorithmica (New York), 2010, v. 58 n. 2, p. 263-281en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152439-
dc.descriptionResult in this paper has appeared in a preliminary form in the Proceedings of the 14th Annual European Symposium (ESA 2006), see this record in hub (with postprint fulltext): http://hub.hku.hk/handle/10722/92634-
dc.description.abstractWe revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k ) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log∈nlog∈log∈n) time. The previously best solution achieving this time complexity requires an index of O(nlog∈n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog∈nlog∈log∈n+occ) time, and k-error matching, for any k>2, in O(m k-1log∈nlog∈log∈n+occ) time. © 2008 Springer Science+Business Media, LLC.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmica (New York)en_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectApproximate String Matchingen_US
dc.subjectCompressed Indexen_US
dc.titleCompressed indexes for approximate string matchingen_US
dc.typeArticleen_US
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityChan, HL=rp01310en_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.natureLink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s00453-008-9263-2en_US
dc.identifier.scopuseid_2-s2.0-77955655806en_US
dc.identifier.hkuros177358-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77955655806&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume58en_US
dc.identifier.issue2en_US
dc.identifier.spage263en_US
dc.identifier.epage281en_US
dc.identifier.isiWOS:000279681700003-
dc.publisher.placeUnited Statesen_US
dc.relation.projectCompressed indexes for approximate string matching, with applications to biological sequences-
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridSung, WK=13310059700en_US
dc.identifier.scopusauthoridTam, SL=14042926200en_US
dc.identifier.scopusauthoridWong, SS=8439889300en_US
dc.identifier.citeulike3811405-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats