Hashing Searching Sketching.

Posted in Conferences, Companies, Science, Development on February 01, 2007

Hashing Searching Sketching.
Google Tech Talks
November 20, 2006

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 will also see some lower bounds and applications to kd trees.

Watch Video

Tags: Techtalks, Google, Conferences, Science, Lectures, Computer Science, Broadcasting, Development, Companies