Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.jda.2011.04.004
DC Field | Value | |
---|---|---|
dc.title | A linear size index for approximate pattern matching | |
dc.contributor.author | Chan, H.-L. | |
dc.contributor.author | Lam, T.-W. | |
dc.contributor.author | Sung, W.-K. | |
dc.contributor.author | Tam, S.-L. | |
dc.contributor.author | Wong, S.-S. | |
dc.date.accessioned | 2013-07-04T08:29:20Z | |
dc.date.available | 2013-07-04T08:29:20Z | |
dc.date.issued | 2011 | |
dc.identifier.citation | Chan, 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.issn | 15708667 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/41515 | |
dc.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 Ω(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.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.jda.2011.04.004 | |
dc.source | Scopus | |
dc.subject | Approximate pattern matching | |
dc.subject | Full text indexing | |
dc.subject | Indexing with errors | |
dc.subject | Space complexity | |
dc.type | Conference Paper | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1016/j.jda.2011.04.004 | |
dc.description.sourcetitle | Journal of Discrete Algorithms | |
dc.description.volume | 9 | |
dc.description.issue | 4 | |
dc.description.page | 358-364 | |
dc.identifier.isiut | 000213950900006 | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
SCOPUSTM
Citations
12
checked on Jan 17, 2021
Page view(s)
133
checked on Jan 20, 2021
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.