Cache-oblivious index for approximate string matching

DOI10.1016/J.TCS.2011.03.004MaRDI QIDQ551183zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Wing-Kai Hon, Tak-Wah Lam, Rahul Shah, Siu-Lung Tam, Jeffrey Scott Vitter

Publication date 14 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10722/140789

zbMATH Keywords

string matchingindexingcache-obliviousapproximate queriesI/O model

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Algorithms on strings (68W32)

Recommendations

• Cache-Oblivious Index for Approximate String Matching
• Compressed Indexes for Approximate String Matching
• A linear size index for approximate pattern matching
• Compressed indexes for approximate string matching
• A Linear Size Index for Approximate Pattern Matching

Cites work

• scientific article; zbMATH DE number 1670652 (Why is no real title available?)
• scientific article; zbMATH DE number 1979501 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms and data structures for external memory
• Cache-Oblivious B-Trees
• Cache-oblivious algorithms
• Cache-oblivious planar orthogonal range searching and counting
• Cache-oblivious string dictionaries
• Compressed indexes for approximate string matching
• Design and implementation of an efficient priority queue
• Dictionary matching and indexing with errors and don't cares
• Dynamic text and static pattern matching
• Fast Algorithms for Finding Nearest Common Ancestors
• Improved approximate string matching using compressed suffix data structures
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Lowest common ancestors in trees and directed acyclic graphs
• Preserving order in a forest in less than logarithmic time and linear space
• Suffix Arrays: A New Method for On-Line String Searches
• Text Indexing and Dictionary Matching with One Error
• The string B-tree

Cited in

(2)

• Approximate String Matching Using a Bidirectional Index
• Cache-Oblivious Index for Approximate String Matching

This page was built for publication: Cache-oblivious index for approximate string matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q551183)