CSML/CS Colloquium Speaker Nati Srebro Thursday, March 12, 4:30pm Computer Science 105 The Power of Asymmetry in Binary Hashing When looking for similar objects, like images and documents, and especially when querying a large remote data-base for similar objects, it is often useful to construct short similarity-preserving binary hashes. That is, to map each image or document to a short bit strings such that similar objects have similar bit strings. Such a mapping lies at the root of nearest neighbor search methods such as Locality Sensitive Hashing (LSH) and is recently gaining popularity in a variety of vision, image retrieval and document retrieval applications. In this talk I will demonstrate, both theoretically and empirically, that even for symmetric and well behaved similarity measures, much could be gained by using two different hash functions---one for hashing objects in the database and an entirely different hash function for the queries. Such asymmetric hashings can allow to significantly shorter bit strings and more accurate retrieval. Joint work with Behnam Neyshabur, Yury Makarychev and Russ Salakhutdinov