5 papers
Results of the Big ANN: NeurIPS'23 competition
Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber +20
The 2023 Big ANN Challenge, held at NeurIPS 2023, focused on advancing the state-of-the-art in indexing data structures and search algorithms for practical variants of Approximate…
PLAN: Variance-Aware Private Mean Estimation
Martin Aumüller, Christian Janos Lebeda, Boel Nelson +1
Differentially private mean estimation is an important building block in privacy-preserving algorithms for data analysis and machine learning. Though the trade-off between privacy…
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…
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…
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…