File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Cache-oblivious index for approximate string matching

TitleCache-oblivious index for approximate string matching
Authors
Issue Date2007
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4580 LNCS, p. 40-51 How to Cite?
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((n logk n)/B) disk pages and finds all k-error matches with O((|P| + occ)/B + logk n log logB n) 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(log n)) I/Os. The second index reduces the space to O{{n log n)/B) disk pages, and the I/O complexity is O((|P| + occ)/B + log k(k+1) n log log n). © Springer-Verlag Berlin Heidelberg 2007.
Persistent Identifierhttp://hdl.handle.net/10722/93153
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorHon, WKen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorShah, Ren_HK
dc.contributor.authorTam, SLen_HK
dc.contributor.authorVitter, JSen_HK
dc.date.accessioned2010-09-25T14:52:30Z-
dc.date.available2010-09-25T14:52:30Z-
dc.date.issued2007en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4580 LNCS, p. 40-51en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93153-
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((n logk n)/B) disk pages and finds all k-error matches with O((|P| + occ)/B + logk n log logB n) 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(log n)) I/Os. The second index reduces the space to O{{n log n)/B) disk pages, and the I/O complexity is O((|P| + occ)/B + log k(k+1) n log log n). © Springer-Verlag Berlin Heidelberg 2007.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleCache-oblivious index for approximate string matchingen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-37849007688en_HK
dc.identifier.hkuros128193en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-37849007688&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4580 LNCSen_HK
dc.identifier.spage40en_HK
dc.identifier.epage51en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridHon, WK=7004282818en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridShah, R=35365088300en_HK
dc.identifier.scopusauthoridTam, SL=14042926200en_HK
dc.identifier.scopusauthoridVitter, JS=7005508549en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats