File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: A linear size index for approximate pattern matching
  • Basic View
  • Metadata View
  • XML View
TitleA linear size index for approximate pattern matching
 
AuthorsChan, HL1
Lam, TW1
Sung, WK2
Tam, SL1
Wong, SS2
 
KeywordsApproximate Pattern Matching
Full Text Indexing
Indexing With Errors
Space Complexity
 
Issue Date2011
 
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jda
 
CitationJournal Of Discrete Algorithms, 2011, v. 9 n. 4, p. 358-364 [How to Cite?]
DOI: http://dx.doi.org/10.1016/j.jda.2011.04.004
 
AbstractThis paper revisits the problem of indexing a text S[1.n] for pattern matching with up to k errors. A naive solution either has a worst-case matching time complexity of Ω(m k) or requires Ω(n k) space, where m is the length of the pattern. Devising a solution with better performance has been a challenge until Cole et al. (2004) [5] showed an O(n log kn)-space index that can support k-error matching in O(m + occ + log knloglogn) time, where occ is the number of occurrences. Motivated by the indexing of long sequences like DNA, we have investigated the feasibility of devising a linear-size index that still has a time complexity linear in pattern length. This paper in particular presents an O(n)-space index that supports k-error matching in O(m+occ+(logn) k(k+1)loglogn) worst-case time. This index can be further compressed from O(n) words into O(n) bits with a slight increase in the time complexity. © 2011 Elsevier B.V. All rights reserved.
 
ISSN1570-8667
2013 SCImago Journal Rankings: 0.990
 
DOIhttp://dx.doi.org/10.1016/j.jda.2011.04.004
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChan, HL
 
dc.contributor.authorLam, TW
 
dc.contributor.authorSung, WK
 
dc.contributor.authorTam, SL
 
dc.contributor.authorWong, SS
 
dc.date.accessioned2012-06-26T06:32:30Z
 
dc.date.available2012-06-26T06:32:30Z
 
dc.date.issued2011
 
dc.description.abstractThis paper revisits the problem of indexing a text S[1.n] for pattern matching with up to k errors. A naive solution either has a worst-case matching time complexity of Ω(m k) or requires Ω(n k) space, where m is the length of the pattern. Devising a solution with better performance has been a challenge until Cole et al. (2004) [5] showed an O(n log kn)-space index that can support k-error matching in O(m + occ + log knloglogn) time, where occ is the number of occurrences. Motivated by the indexing of long sequences like DNA, we have investigated the feasibility of devising a linear-size index that still has a time complexity linear in pattern length. This paper in particular presents an O(n)-space index that supports k-error matching in O(m+occ+(logn) k(k+1)loglogn) worst-case time. This index can be further compressed from O(n) words into O(n) bits with a slight increase in the time complexity. © 2011 Elsevier B.V. All rights reserved.
 
dc.description.natureLink_to_subscribed_fulltext
 
dc.identifier.citationJournal Of Discrete Algorithms, 2011, v. 9 n. 4, p. 358-364 [How to Cite?]
DOI: http://dx.doi.org/10.1016/j.jda.2011.04.004
 
dc.identifier.citeulike9191078
 
dc.identifier.doihttp://dx.doi.org/10.1016/j.jda.2011.04.004
 
dc.identifier.epage364
 
dc.identifier.issn1570-8667
2013 SCImago Journal Rankings: 0.990
 
dc.identifier.issue4
 
dc.identifier.scopuseid_2-s2.0-80755140493
 
dc.identifier.spage358
 
dc.identifier.urihttp://hdl.handle.net/10722/152018
 
dc.identifier.volume9
 
dc.languageeng
 
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jda
 
dc.publisher.placeNetherlands
 
dc.relation.ispartofJournal of Discrete Algorithms
 
dc.relation.referencesReferences in Scopus
 
dc.subjectApproximate Pattern Matching
 
dc.subjectFull Text Indexing
 
dc.subjectIndexing With Errors
 
dc.subjectSpace Complexity
 
dc.titleA linear size index for approximate pattern matching
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chan, HL</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Sung, WK</contributor.author>
<contributor.author>Tam, SL</contributor.author>
<contributor.author>Wong, SS</contributor.author>
<date.accessioned>2012-06-26T06:32:30Z</date.accessioned>
<date.available>2012-06-26T06:32:30Z</date.available>
<date.issued>2011</date.issued>
<identifier.citation>Journal Of Discrete Algorithms, 2011, v. 9 n. 4, p. 358-364</identifier.citation>
<identifier.issn>1570-8667</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/152018</identifier.uri>
<description.abstract>This paper revisits the problem of indexing a text S[1.n] for pattern matching with up to k errors. A naive solution either has a worst-case matching time complexity of &#937;(m k) or requires &#937;(n k) space, where m is the length of the pattern. Devising a solution with better performance has been a challenge until Cole et al. (2004) [5] showed an O(n log kn)-space index that can support k-error matching in O(m + occ + log knloglogn) time, where occ is the number of occurrences. Motivated by the indexing of long sequences like DNA, we have investigated the feasibility of devising a linear-size index that still has a time complexity linear in pattern length. This paper in particular presents an O(n)-space index that supports k-error matching in O(m+occ+(logn) k(k+1)loglogn) worst-case time. This index can be further compressed from O(n) words into O(n) bits with a slight increase in the time complexity. &#169; 2011 Elsevier B.V. All rights reserved.</description.abstract>
<language>eng</language>
<publisher>Elsevier BV. The Journal&apos;s web site is located at http://www.elsevier.com/locate/jda</publisher>
<relation.ispartof>Journal of Discrete Algorithms</relation.ispartof>
<subject>Approximate Pattern Matching</subject>
<subject>Full Text Indexing</subject>
<subject>Indexing With Errors</subject>
<subject>Space Complexity</subject>
<title>A linear size index for approximate pattern matching</title>
<type>Conference_Paper</type>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1016/j.jda.2011.04.004</identifier.doi>
<identifier.scopus>eid_2-s2.0-80755140493</identifier.scopus>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-80755140493&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>9</identifier.volume>
<identifier.issue>4</identifier.issue>
<identifier.spage>358</identifier.spage>
<identifier.epage>364</identifier.epage>
<publisher.place>Netherlands</publisher.place>
<identifier.citeulike>9191078</identifier.citeulike>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. National University of Singapore