# Local Density Estimation in High Dimensions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2018.

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

- [Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing](https://mlsanity.com/paper/2604.04603/) (2026)

## Abstract (arXiv)

An important question that arises in the study of high dimensional vector representations learned from data is: given a set D of vectors and a query q, estimate the number of points within a specified distance threshold of q. We develop two estimators, LSH Count and Multi-Probe Count that use locality sensitive hashing to preprocess the data to accurately and efficiently estimate the answers to such questions via importance sampling. A key innovation is the ability to maintain a small number of hash tables via preprocessing data structures and algorithms that sample from multiple buckets in each hash table. We give bounds on the space requirements and sample complexity of our schemes, and demonstrate their effectiveness in experiments on a standard word embedding dataset.