Space and Time Efficient Kernel Density Estimation in High Dimensions

Arturs Backurs; Piotr Indyk; Tal Wagner

NeurIPS 2019poster81 citations

Space and Time Efficient Kernel Density Estimation in High Dimensions

Abstract

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.

BibTeX

@inproceedings{NEURIPS2019_a2ce8f17,
 author = {Backurs, Arturs and Indyk, Piotr and Wagner, Tal},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Space and Time Efficient Kernel Density Estimation in High Dimensions},
 url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/a2ce8f1706e52936dfad516c23904e3e-Paper.pdf},
 volume = {32},
 year = {2019}
}