O(log s)-Approximate Nearest Neighbor Search for the Earth Mover’s Distance

on YouTube ↗37m

" summary

Presents the first improvement in approximation for ANN under Earth Mover’s Distance in over a decade, reducing prior O(log^2 s) to Õ(log s) while keeping sublinear O(n^ε) query time. Uses probabilistic tree embeddings but replaces fixed edge weights with a data-dependent LSH built from a random poly(s) sample, hybridizing with classic AIK weights. Proves an extension lemma that shows guarantees extend to a Chamfer neighborhood and then glues that with AIK’s fallback to get the final ANN data structure.

AI-written summary · about

" chapters (21)

1. 0:00Welcome
2. 1:08Nearest neighbor for EMD
3. 2:11Earth Mover’s Distance
4. 3:15Problem setup
5. 6:20Problem goals
6. 7:21Nearest neighbor in l1
7. 8:26EMD search results
8. 10:15EMD computation complexity
9. 11:18EMD into tree metrics
10. 13:06Probabilistic tree embeddings
11. 14:09Fast tree embeddings
12. 16:16Data-dependent embeddings
13. 18:23How embeddings work
14. 20:52Embedding differences
15. 22:57Challenges in embeddings
16. 24:00Sample tree algorithm
17. 25:47Hybrid edge weights
18. 27:12Chamfer neighborhoods
19. 30:45Final algorithm
20. 31:48Open problems
21. 34:57Q&A