Beyond Locality-Sensitive Hashing
Date: Wednesday, November 20, 2013
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Location: 32 G575
Host: Piotr Indyk
Contact: Nina L. Olff, 617-253-6025, firstname.lastname@example.org
Speaker URL: None
email@example.com, firstname.lastname@example.org, email@example.com
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.
Created by Nina L. Olff at Thursday, October 31, 2013 at 9:59 AM.