Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.
Elazar GoldenbergTomasz KociumakaRobert KrauthgamerBarna SahaPublished in: FOCS (2022)
Keyphrases
- edit distance
- dynamic programming
- query processing
- string similarity
- similarity measure
- string matching
- distance function
- approximate string matching
- similarity join
- graph edit distance
- computer vision
- levenshtein distance
- edit operations
- query language
- query evaluation
- tree structured data
- distance computation
- approximate matching
- similarity search
- pattern recognition
- worst case
- tree edit distance
- graph matching
- range queries