Cache-oblivious index for approximate string matching

DOI10.1016/j.tcs.2011.03.004zbMath1221.68073OpenAlexW2176354471WikidataQ58062913 ScholiaQ58062913MaRDI QIDQ551183

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

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

Cites Work

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

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