File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A linear size index for approximate pattern matching

TitleA linear size index for approximate pattern matching
Authors
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
Citation
Journal Of Discrete Algorithms, 2011, v. 9 n. 4, p. 358-364 How to Cite?
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.
Persistent Identifierhttp://hdl.handle.net/10722/152018
ISSN
2014 SCImago Journal Rankings: 0.822
References

 

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:32:30Z-
dc.date.available2012-06-26T06:32:30Z-
dc.date.issued2011en_US
dc.identifier.citationJournal Of Discrete Algorithms, 2011, v. 9 n. 4, p. 358-364en_US
dc.identifier.issn1570-8667en_US
dc.identifier.urihttp://hdl.handle.net/10722/152018-
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.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jdaen_US
dc.relation.ispartofJournal of Discrete Algorithmsen_US
dc.subjectApproximate Pattern Matchingen_US
dc.subjectFull Text Indexingen_US
dc.subjectIndexing With Errorsen_US
dc.subjectSpace Complexityen_US
dc.titleA linear size index for approximate pattern matchingen_US
dc.typeConference_Paperen_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.1016/j.jda.2011.04.004en_US
dc.identifier.scopuseid_2-s2.0-80755140493en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80755140493&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume9en_US
dc.identifier.issue4en_US
dc.identifier.spage358en_US
dc.identifier.epage364en_US
dc.publisher.placeNetherlandsen_US
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.citeulike9191078-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats