Importance Sampling in High Dimensions via Hashing

Locality-sensitive hashing is widely used for high-dimensional nearest-neighbor search. This talk develops another view of hashing as a biased sampling method for density-estimation queries. Given a point set and a query, one may estimate kernel density by summing distance-dependent influence functions, or count points within a chosen radius. A linear scan is costly for large datasets and many queries. The presentation surveys recent methods that preprocess the data and use locality-sensitive hashing to construct unbiased estimators for these problems and their extensions. It covers joint work with Arturs Backurs, Piotr Indyk, Vishnu Natchu, Paris Syminelakis, and Xian (Carrie) Wu.