Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
Alexandr AndoniRobert KrauthgamerKrzysztof OnakPublished in: CoRR (2010)
Keyphrases
- decision trees
- edit distance
- query complexity
- similarity measure
- edit operations
- graph matching
- exact learning
- data complexity
- distance measure
- distance function
- training data
- dynamic programming
- membership queries
- machine learning
- special case
- pairwise
- concept class
- similarity search
- vc dimension
- uniform distribution
- database
- relational databases
- object recognition
- databases