# Data Structures for Density Estimation

arXiv: https://arxiv.org/abs/2306.11312 · HTML: https://mlsanity.com/paper/2306.11312/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 20 Jun 2023.

## Builds on (most cited first, 9 of 9)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [The Structure of Optimal Private Tests for Simple Hypotheses](https://mlsanity.com/paper/1811.11148/) (2018)
- [Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians](https://mlsanity.com/paper/1312.1054/) (2013)
- [Locally Private Hypothesis Selection](https://mlsanity.com/paper/2002.09465/) (2020)

## Built on by (most cited first, 4 of 4)

- [Statistical-Computational Trade-offs for Density Estimation](https://mlsanity.com/paper/2410.23087/) (2024)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph](https://mlsanity.com/paper/2509.16180/) (2025)

## Abstract (arXiv)

We study statistical/computational tradeoffs for the following density estimation problem: given k distributions v1, ldots, vk over a discrete domain of size n, and sampling access to a distribution p, identify vi that is "close" to p. Our main result is the first data structure that, given a sublinear (in n) number of samples from p, identifies vi in time sublinear in k. We also give an improved version of the algorithm of Acharya et al. (2018) that reports vi in time linear in k. The experimental evaluation of the latter algorithm shows that it achieves a significant reduction in the number of operations needed to achieve a given accuracy compared to prior work.