Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jda.2011.04.004
DC FieldValue
dc.titleA linear size index for approximate pattern matching
dc.contributor.authorChan, H.-L.
dc.contributor.authorLam, T.-W.
dc.contributor.authorSung, W.-K.
dc.contributor.authorTam, S.-L.
dc.contributor.authorWong, S.-S.
dc.date.accessioned2013-07-04T08:29:20Z
dc.date.available2013-07-04T08:29:20Z
dc.date.issued2011
dc.identifier.citationChan, H.-L., Lam, T.-W., Sung, W.-K., Tam, S.-L., Wong, S.-S. (2011). A linear size index for approximate pattern matching. Journal of Discrete Algorithms 9 (4) : 358-364. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jda.2011.04.004
dc.identifier.issn15708667
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/41515
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.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.jda.2011.04.004
dc.sourceScopus
dc.subjectApproximate pattern matching
dc.subjectFull text indexing
dc.subjectIndexing with errors
dc.subjectSpace complexity
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1016/j.jda.2011.04.004
dc.description.sourcetitleJournal of Discrete Algorithms
dc.description.volume9
dc.description.issue4
dc.description.page358-364
dc.identifier.isiut000213950900006
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

11
checked on Jan 16, 2020

WEB OF SCIENCETM
Citations

6
checked on Jan 16, 2020

Page view(s)

117
checked on Dec 30, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.