# On Adaptive Distance Estimation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2020.

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

- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Terminal Embeddings in Sublinear Time](https://mlsanity.com/paper/2110.08691/) (2021)
- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Adversarially Robust Distributed Count Tracking via Partial Differential Privacy](https://mlsanity.com/paper/2311.00346/) (2023)
- [The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimation](https://mlsanity.com/paper/2507.16345/) (2025)

## Abstract (arXiv)

We provide a static data structure for distance estimation which supports it adaptive queries. Concretely, given a dataset X = xii = 1n of n points in ℝd and 0 < p ≤ 2, we construct a randomized data structure with low memory consumption and query time which, when later given any query point q ∈ ℝd, outputs a (1+ε)-approximation of lVert q - xi rVertp with high probability for all i∈[n]. The main novelty is our data structure's correctness guarantee holds even when the sequence of queries can be chosen adaptively: an adversary is allowed to choose the jth query point qj in a way that depends on the answers reported by the data structure for q1,ldots,qj-1. Previous randomized Monte Carlo methods do not provide error guarantees in the setting of adaptively chosen queries. Our memory consumption is tilde O((n+d)d/ε2), slightly more than the O(nd) required to store X in memory explicitly, but with the benefit that our time to answer queries is only tilde O(ε-2(n + d)), much faster than the naive Theta(nd) time obtained from a linear scan in the case of n and d very large. Here tilde O hides log(nd/ε) factors. We discuss applications to nearest neighbor search and nonparametric estimation. Our method is simple and likely to be applicable to other domains: we describe a generic approach for transforming randomized Monte Carlo data structures which do not support adaptive queries to ones that do, and show that for the problem at hand, it can be applied to standard nonadaptive solutions to ℓp norm estimation with negligible overhead in query time and a factor d overhead in memory.