Article: Cache-oblivious index for approximate string matching

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleCache-oblivious index for approximate string matching
AuthorsHon, WK3
Lam, TW2
Shah, R4
Tam, SL2
Vitter, JS1
KeywordsApproximate queries
Cache-oblivious
I/O model
Indexing
String matching
Issue Date2011
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
CitationTheoretical Computer Science, 2011, v. 412 n. 29, p. 3579-3588 [How to Cite?]
DOI: http://dx.doi.org/10.1016/j.tcs.2011.03.004
AbstractThis 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 Ω (|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) . © 2011 Elsevier B.V. All rights reserved.
ISSN0304-3975
2011 Impact Factor: 0.665
2011 SCImago Journal Rankings: 0.055
DOIhttp://dx.doi.org/10.1016/j.tcs.2011.03.004
ISI Accession Number IDWOS:000292077200015
Funding AgencyGrant Number
Taiwan NSC96-2221-E-007-082
99-2221-E-007-123
Hong Kong RGC7140/06E
US NSFCCF-0621457
CCF-1017623
Funding Information:

A preliminary version appears in Proceedings of 18th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 40-51, 2007. This research is supported in part by Taiwan NSC Grants 96-2221-E-007-082 and 99-2221-E-007-123 (Wing-Kai Hon), Hong Kong RGC Grant 7140/06E (Tak-Wah Lam), and US NSF Grants CCF-0621457 and CCF-1017623 (Rahul Shah and Jeffrey Scott Vitter).

ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorHon, WK
dc.contributor.authorLam, TW
dc.contributor.authorShah, R
dc.contributor.authorTam, SL
dc.contributor.authorVitter, JS
dc.date.accessioned2011-09-23T06:19:20Z
dc.date.available2011-09-23T06:19:20Z
dc.date.issued2011
dc.description.abstractThis 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 Ω (|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) . © 2011 Elsevier B.V. All rights reserved.
dc.description.naturepostprint
dc.identifier.citationTheoretical Computer Science, 2011, v. 412 n. 29, p. 3579-3588 [How to Cite?]
DOI: http://dx.doi.org/10.1016/j.tcs.2011.03.004
dc.identifier.citeulike9193876
dc.identifier.doihttp://dx.doi.org/10.1016/j.tcs.2011.03.004
dc.identifier.epage3588
dc.identifier.hkuros192200
dc.identifier.isiWOS:000292077200015
Funding AgencyGrant Number
Taiwan NSC96-2221-E-007-082
99-2221-E-007-123
Hong Kong RGC7140/06E
US NSFCCF-0621457
CCF-1017623
Funding Information:

A preliminary version appears in Proceedings of 18th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 40-51, 2007. This research is supported in part by Taiwan NSC Grants 96-2221-E-007-082 and 99-2221-E-007-123 (Wing-Kai Hon), Hong Kong RGC Grant 7140/06E (Tak-Wah Lam), and US NSF Grants CCF-0621457 and CCF-1017623 (Rahul Shah and Jeffrey Scott Vitter).

dc.identifier.issn0304-3975
2011 Impact Factor: 0.665
2011 SCImago Journal Rankings: 0.055
dc.identifier.issue29
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-79956348246
dc.identifier.spage3579
dc.identifier.urihttp://hdl.handle.net/10722/140789
dc.identifier.volume412
dc.languageeng
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
dc.publisher.placeNetherlands
dc.relation.ispartofTheoretical Computer Science
dc.relation.referencesReferences in Scopus
dc.rightsNOTICE: this is the author’s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical Computer Science, 2011, v. 412 n. 29, p. 3579-3588. DOI: http://dx.doi.org/10.1016/j.tcs.2011.03.004
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
dc.subjectApproximate queries
dc.subjectCache-oblivious
dc.subjectI/O model
dc.subjectIndexing
dc.subjectString matching
dc.titleCache-oblivious index for approximate string matching
dc.typeArticle
Author Affiliations
  1. University of Kansas
  2. The University of Hong Kong
  3. National Tsing Hua University
  4. Louisiana State University