A sublinear algorithm for approximate keyword searching

DOI10.1007/BF01185432zbMath0941.68560OpenAlexW2165156013MaRDI QIDQ1336965

Eugene W. Myers

Publication date: 26 February 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01185432

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Protein sequences, DNA sequences (92D20) Information storage and retrieval of data (68P20)

Related Items (12)

A metric index for approximate string matching ⋮ New and faster filters for multiple approximate string matching ⋮ Multiple filtration and approximate pattern matching ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ Approximate string matching with compressed indexes ⋮ Multiple approximate string matching ⋮ Fast Approximate Search in Large Dictionaries ⋮ Text indexing with errors ⋮ Efficient generation of super condensed neighborhoods ⋮ What’s Behind Blast ⋮ A new method for approximate indexing and dictionary lookup with one error ⋮ Indexing text with approximate \(q\)-grams

Cites Work

• An \(O(ND)\) difference algorithm and its variations
• A subquadratic algorithm for approximate limited expression matching
• A fast string searching algorithm
• An Improved Algorithm For Approximate String Matching
• Finding approximate patterns in strings
• Algorithms for approximate string matching
• The theory and computation of evolutionary distances: Pattern recognition
• Fast Pattern Matching in Strings

This page was built for publication: A sublinear algorithm for approximate keyword searching