Beyond Locality-Sensitive Hashing

Speaker: Ilya Razenshteyn , MIT/CSAIL

Date: Wednesday, November 20, 2013

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32 G575

Event Type:

Room Description:

Host: Piotr Indyk

Contact: Nina L. Olff, 617-253-6025, olff@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu, compalgsem@lists.csail.mit.edu

Reminder Subject: TALK: Algorithms & Complexity Seminar: Ilya Razenshteyn "Beyond Locality-Sensitive Hashing"

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in Rd, our algorithm achieves Oc(dn?) query time and Oc(n1+?+nd) space, where ??7/(8c2)+O(1/c3)+oc(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ?1 norm with ??7/(8c)+O(1/c3/2)+oc(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998). Our data structure is able to bypass the locality-sensitive hashing barrier by using data-dependent hash functions (previous work used functions that are oblivious to the data). Joint work with Alexandr Andoni, Piotr Indyk and Nguy?n Lê Huy A short summary of the paper can be found here.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Nina L. Olff at Thursday, October 31, 2013 at 9:59 AM.