Timezone: »

 
Poster
Space and Time Efficient Kernel Density Estimation in High Dimensions
Arturs Backurs · Piotr Indyk · Tal Wagner

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #53
in Algorithms -- Density Estimation »

Recently, Charikar and Siminelakis (2017) presented a framework for kernel density estimation in provably sublinear query time, for kernels that possess a certain hashing-based property. However, their data structure requires a significantly increased super-linear storage space, as well as super-linear preprocessing time. These limitations inhibit the practical applicability of their approach on large datasets.

In this work, we present an improvement to their framework that retains the same query time, while requiring only linear space and linear preprocessing time. We instantiate our framework with the Laplacian and Exponential kernels, two popular kernels which possess the aforementioned property. Our experiments on various datasets verify that our approach attains accuracy and query time similar to Charikar and Siminelakis (2017), with significantly improved space and preprocessing time.

Keywords: Similarity and Distance Learning · Density Estimation · Algorithms · Algorithms -> Kernel Methods; Algorithms
[ Paper]  [ Slides] 

Author Information

Arturs Backurs (MIT)
Piotr Indyk (MIT)
Tal Wagner (MIT)

More from the Same Authors