A sublinear algorithm for approximate keyword searching

DOI10.1007/BF01185432MaRDI QIDQ1336965zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

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

Cited in

(13)

• A new method for approximate indexing and dictionary lookup with one error
• Approximate string matching with compressed indexes
• Multiple filtration and approximate pattern matching
• A subquadratic algorithm for approximate limited expression matching
• Efficient generation of super condensed neighborhoods
• Indexing text with approximate \(q\)-grams
• Fast approximate search in large dictionaries
• New and faster filters for multiple approximate string matching
• What's behind blast
• Multiple approximate string matching
• A unified view to string matching algorithms
• A metric index for approximate string matching
• Text indexing with errors

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

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