Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jda.2011.04.004
Title: A linear size index for approximate pattern matching
Authors: Chan, H.-L.
Lam, T.-W.
Sung, W.-K. 
Tam, S.-L.
Wong, S.-S. 
Keywords: Approximate pattern matching
Full text indexing
Indexing with errors
Space complexity
Issue Date: 2011
Source: 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
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.
Source Title: Journal of Discrete Algorithms
URI: http://scholarbank.nus.edu.sg/handle/10635/41515
ISSN: 15708667
DOI: 10.1016/j.jda.2011.04.004
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

10
checked on Dec 11, 2017

Page view(s)

52
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


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