MIT 6.854 Spring 2016 Lecture 6: Nearest Neighbor Search and LSH

[@aleksagordic9593]

0:00 - 3:30 intro 3:30 - 7:00 nearest neighbor (NN) problem setup 7:00 - 9:15 some applications of nearest neighbor problem -> spam classification 9:15 - 12:50 approach #1 (no preprocessing on a query do a linear search) 12:49 - 17:12 approach #2 (1 dimension, d == 1, binary search) 17:12 - 20:40 approach #2 (2 dimensions, d == 2, Voronoi diagram) 20:40 - 25:20 higher dimensions problems => all approaches have exponential space and time 25:20 - 28:20 approximate NN method (c-ANN) 28:20 - 34:00 digression to (r1, r2)-PLEB problem 34:00 - 47:45 connection between c-ANN and (r1, r2)-PLEB 47:45 - 54:00 LSH (locality sensitive hashing) 54:00 - 58:30 LSH function example 58:30 - 1:05:00 theorem that we can use LSH to solve PLEB 1:05:00 wrapping up

[@ahmedhusain8911]

Appreciate it man

[@reinerwilhelms-tricarico344]

Funny how the automatically (?) tracking camera registers anyone who shows up late or leaves early, yet occasionally looses the lecturer.

[@shramanraychaudhuri8400]

XIA!!

[@botongma3179]

+Shraman Ray Chaudhuri XIAAAA!