Please use this identifier to cite or link to this item:
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
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.
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
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.


checked on Jan 16, 2020


checked on Jan 16, 2020

Page view(s)

checked on Dec 30, 2019

Google ScholarTM



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