Name
Abstract | ||
|---|---|---|
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((nlog^kn)/B) disk pages and finds all k-error matches with O((|P|+occ)/B+log^knloglog"Bn) 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 @W(|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+log^k^(^k^+^1^)nloglogn). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2011.03.004 | CPM |
Keywords | DocType | Volume |
approximate string matching,external memory,indexation,string matching,data structure | Journal | 412 |
Issue | ISSN | ISBN |
29 | 0304-3975 | 3-540-73436-8 |
Citations | PageRank | References |
4 | 0.38 | 26 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wing-Kai Hon | 1 | 856 | 78.67 |
| Tak-Wah Lam | 2 | 1860 | 164.96 |
| Rahul Shah | 3 | 1059 | 61.31 |
| Siu-Lung Tam | 4 | 127 | 19.19 |
| Jeffrey Scott Vitter | 5 | 6628 | 1246.72 |