Fetching the paper…
Reading the bibliography…
In this paper we revisit the kernel density estimation problem: given a kernel $K(x, y)$ and a dataset of $n$ points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query $q$, a $(1+\epsilon)$-approximation to $\mu:=\frac1{|P|}\sum_{p\in P} K(p, q)$.
Local polynomial modelling and its applications: monographs on statistics and applied probability 66
Jianqing Fan and Irene Gijbels · 1996
Earlier work this paper cites.
A short course on fast multipole methods
R Beatson and Leslie Greengard · 1997
Earlier work this paper cites.
Approximate nearest neighbors: Towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
N-body’problems in statistical learning
Alexander G Gray and Andrew W Moore · 2001
Earlier work this paper cites.
Learning with kernels: support vector machines, regularization, optimization, and beyond
Bernhard Scholkopf and Alexander J Smola · 2001
Earlier work this paper cites.
Finding nearest neighbors in growth-restricted metrics
David R Karger and Matthias Ruhl · 2002
Earlier work this paper cites.
Nonparametric density estimation: Toward computational tractability
Alexander G Gray and Andrew W Moore · 2003
Earlier work this paper cites.
Improved fast gauss transform and efficient kernel density estimation
Changjiang Yang, Ramani Duraiswami, Nail A Gumerov, and Larry Davis · 2003
Earlier work this paper cites.
Locality-sensitive hashing scheme based on p-stable distributions
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni · 2004
Earlier work this paper cites.
Kernel methods for pattern analysis
John Shawe-Taylor, Nello Cristianini, et al · 2004
Earlier work this paper cites.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Alexandr Andoni and Piotr Indyk · 2006
Earlier work this paper cites.
Dual-tree fast gauss transforms
Dongryeol Lee, Andrew W Moore, and Alexander G Gray · 2006
Earlier work this paper cites.
Gaussian processes for machine learning
Carl Edward Rasmussen and Christopher K. I. Williams · 2006
Earlier work this paper cites.
Linear-time algorithms for pairwise statistical problems
Parikshit Ram, Dongryeol Lee, William March, and Alexander G Gray · 2009
Earlier work this paper cites.
Comparing distributions and shapes using the kernel distance
Sarang Joshi, Raj Varma Kommaraji, Jeff M Phillips, and Suresh Venkatasubramanian · 2011
Cited alongside, same era.
ε \varepsilon -samples for kernels
Jeff M Phillips · 2013
Cited alongside, same era.
Fast and scalable polynomial kernels via explicit feature maps
Ninh Pham and Rasmus Pagh · 2013
Cited alongside, same era.
Beyond locality-sensitive hashing
Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya P. Razenshteyn · 2014
Cited alongside, same era.
Subspace embeddings for the polynomial kernel
Haim Avron, Huy Nguyen, and David Woodruff · 2014
Cited alongside, same era.
Nonparametric ridge estimation
Christopher R Genovese, Marco Perone-Pacifico, Isabella Verdinelli, Larry Wasserman, et al · 2014
Cited alongside, same era.
Efficient density evaluation for smooth kernels
Arturs Backurs, Moses Charikar, Piotr Indyk, and Paris Siminelakis · 2018
Later among the works it cites.
Arrays of (locality-sensitive) count estimators (ace): Anomaly detection on the edge
Chen Luo and Anshumali Shrivastava · 2018
Later among the works it cites.
Improved coresets for kernel density estimates
Jeff M Phillips and Wai Ming Tai · 2018
Later among the works it cites.
Near-optimal coresets of kernel density estimates
Jeff M Phillips and Wai Ming Tai · 2018
Later among the works it cites.
Hardness of approximate nearest neighbor search
Aviad Rubinstein · 2018
Later among the works it cites.
Local density estimation in high dimensions
Xian Wu, Moses Charikar, and Vishnu Natchu · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Generalized outlier detection with flexible kernel density estimates
Erich Schubert, Arthur Zimek, and Hans-Peter Kriegel · 2014
Cited alongside, same era.
On the estimation of the gradient lines of a density and the consistency of the mean-shift algorithm
Ery Arias-Castro, David Mason, and Bruno Pelletier · 2015
Cited alongside, same era.
Optimal data-dependent hashing for approximate near neighbors
Alexandr Andoni and Ilya P. Razenshteyn · 2015
Cited alongside, same era.
Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh · 2017
Cited alongside, same era.
Optimal hashing-based time-space trade-offs for approximate near neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, and Erik Waingarten · 2017
Cited alongside, same era.
Hashing-based-estimators for kernel density in high dimensions
Moses Charikar and Paris Siminelakis · 2017
Cited alongside, same era.
Space and time efficient kernel density estimation in high dimensions
Arturs Backurs, Piotr Indyk, and Tal Wagner · 2019
Later among the works it cites.
Multi-resolution hashing for fast pairwise summations
Moses Charikar and Paris Siminelakis · 2019
Later among the works it cites.
Lsh-sampling breaks the computation chicken-and-egg loop in adaptive stochastic gradient estimation
Beidi Chen, Yingchen Xu, and Anshumali Shrivastava · 2019
Later among the works it cites.
Discrepancy, coresets, and sketches in machine learning
Zohar S. Karnin and Edo Liberty · 2019
Later among the works it cites.
Scaling-up split-merge mcmc with locality sensitive sampling (lss)
Chen Luo and Anshumali Shrivastava · 2019
Later among the works it cites.
Rehashing kernel evaluation in high dimensions
Paris Siminelakis, Kexin Rong, Peter Bailis, Moses Charikar, and Philip Levis · 2019
Later among the works it cites.
Kernel Evaluation in High Dimensions: Importance Sampling and Nearest-Neighbor Search
Paraskevas Syminelakis · 2019
Later among the works it cites.
Oblivious sketching of high-degree polynomial kernels
Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh · 2020
Closest in time.