Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] FOCS Practice talk Today 1:00pm - 1:30pm @ Gates 463A

Paris Syminelakis psimin at
Fri Oct 13 12:07:01 PDT 2017

Hi all,

I am going to be giving a FOCS practice talk today between 1:00pm - 1:30pm at Gates 463A and would be great to get some feedback. Everyone is welcome! Abstract follows.


Title: Hashing-Based-Estimators for Kernel Density in High Dimensions.

Abstract: Given a set of points $P\subset \R^{d}$ and a kernel $k$, the Kernel Density Estimate at a point $x\in\R^{d}$  is defined as $\mathrm{KDE}_{P}(x)=\frac{1}{|P|}\sum_{y\in P} k(x,y)$. We study the problem of designing a data structure that given a data set $P$ and a kernel function, returns \emph{approximations to the kernel density} of a query point in \emph{sublinear time}.  We introduce a class of unbiased estimators for kernel density  implemented through locality-sensitive hashing, and give general theorems bounding the variance of such estimators.

These estimators give rise to   efficient data structures for estimating the kernel density in high dimensions for a variety of commonly used kernels. Our work is the first to provide data-structures with theoretical guarantees that improve upon simple random sampling in high dimensions.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list