Showing 2021Show all
3 papers · 1 filter
cs.DS2021
DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search
Matti Karppa, Martin Aumüller, Rasmus Pagh
Kernel Density Estimation (KDE) is a nonparametric method for estimating the shape of a density function, given a set of samples from the distribution. Recently, locality-sensitive…
cs.CR2021
Differentially Private Sparse Vectors with Low Error, Optimal Space, and Fast Access
Martin Aumüller, Christian Janos Lebeda, Rasmus Pagh
Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy. An ideal solution would use space close to information-theoretica…
cs.DS2021
Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?
Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi +2
Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points and a radius parameter , the -near nei…