Hashing Searching Sketching.

Channel:

Google TechTalks

Subscribers:

348,000

Published on October 9, 2007 2:08:56 AM ● Video Link: https://www.youtube.com/watch?v=EdsyTzUk1A8

Duration: 1:02:03

14,144 views

31

Google Tech Talks
November 20, 2006

ABSTRACT
We will see improved results on search using hashing and sketching. Hashing is often analyzed as balls being thrown into bins where you think of the hash items as balls and buckets as bins. By studying variants of the balls and bins processes we obtain a hashing algorithm with 85% hash table space utilization. We will also study locality sensitive hashing, a hashing method used for nearest neighbor search, as opposed to exact search. A locality sensitive hash function is likely to map nearby elements to the same bucket. We will see a variant of locality sensitive hashing that finds an approximate nearest neighbor in high dimensions using linear space. We...