Cache-oblivious index for approximate string matching

Cache-oblivious index for approximate string matching,10.1016/j.tcs.2011.03.004,Theoretical Computer Science,Wing-Kai Hon,Tak-Wah Lam,Rahul Shah,Siu-L

Cache-oblivious index for approximate string matching  
BibTex | RIS | RefWorks Download
This paper revisits the problem of indexing a text for approximate string matching. Specifically, given a text T of length n and a positive integer k, we want to construct an index of T such that for any input pattern P, we can find all its k-error matches in T efficiently. This problem is well-studied in the internal-memory setting. Here, we extend some of these recent results to external-memory solutions, which are also cache-oblivious. Our first index occupies O((nlogkn)/B) disk pages and finds all k-error matches with O((|P|+occ)/B+logknloglogBn) I/Os, where B denotes the number of words in a disk page. To the best of our knowledge, this index is the first external-memory data structure that does not require Ω(|P|+occ+poly(logn)) I/Os. The second index reduces the space to O((nlogn)/B) disk pages, and the I/O complexity is O((|P|+occ)/B+logk(k+1)nloglogn).
Journal: Theoretical Computer Science - TCS , vol. 412, no. 29, pp. 3579-3588, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.