In this paper we revisit the kernel density estimation problem: given a\nkernel $K(x, y)$ and a dataset of $n$ points in high dimensional Euclidean\nspace, prepare a data structure that can quickly output, given a query $q$, a\n$(1+\\epsilon)$-approximation to $\\mu:=\\frac1{|P|}\\sum_{p\\in P} K(p, q)$. First,\nwe give a single data structure based on classical near neighbor search\ntechniques that improves upon or essentially matches the query time and space\ncomplexity for all radial kernels considered in the literature so far. We then\nshow how to improve both the query complexity and runtime by using recent\nadvances in data-dependent near neighbor search.\n We achieve our results by giving a new implementation of the natural\nimportance sampling scheme. Unlike previous approaches, our algorithm first\nsamples the dataset uniformly (considering a geometric sequence of sampling\nrates), and then uses existing approximate near neighbor search techniques on\nthe resulting smaller dataset to retrieve the sampled points that lie at an\nappropriate distance from the query. We show that the resulting sampled dataset\nhas strong geometric structure, making approximate near neighbor search return\nthe required samples much more efficiently than for worst case datasets of the\nsame size. As an example application, we show that this approach yields a data\nstructure that achieves query time $\\mu^{-(1+o(1))/4}$ and space complexity\n$\\mu^{-(1+o(1))}$ for the Gaussian kernel. Our data dependent approach achieves\nquery time $\\mu^{-0.173-o(1)}$ and space $\\mu^{-(1+o(1))}$ for the Gaussian\nkernel. The data dependent analysis relies on new techniques for tracking the\ngeometric structure of the input datasets in a recursive hashing process that\nwe hope will be of interest in other applications in near neighbor search.\n