Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach.
Barna SahaPublished in: FOCS (2017)
Keyphrases
- edit distance
- space efficient
- dynamic programming
- rna secondary structures
- data structure
- edit operations
- data streams
- graph matching
- string matching
- sliding window
- similarity measure
- string similarity
- approximate matching
- levenshtein distance
- b tree
- string edit distance
- bloom filter
- suffix array
- tree edit distance
- distance function
- distance measure
- reinforcement learning
- data sets
- database
- english text
- object recognition