# Fast Distance Oracles for Any Symmetric Norm

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2022.

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

- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph](https://mlsanity.com/paper/2502.00739/) (2025)
- [Generalized Sobolev IPM for Graph-Based Measures](https://mlsanity.com/paper/2510.25591/) (2025)

## Abstract (arXiv)

In the Distance Oracle problem, the goal is to preprocess n vectors x1, x2, cdots, xn in a d-dimensional metric space (mathbbXd, | · |l) into a cheap data structure, so that given a query vector q ∈ mathbbXd and a subset Ssubseteq [n] of the input data points, all distances | q - xi |l for xi∈ S can be quickly approximated (faster than the trivial ~ d|S| query time). This primitive is a basic subroutine in machine learning, data mining and similarity search applications. In the case of ℓp norms, the problem is well understood, and optimal data structures are known for most values of p. Our main contribution is a fast (1+varepsilon) distance oracle for any symmetric norm |·|l. This class includes ℓp norms and Orlicz norms as special cases, as well as other norms used in practice, e.g. top-k norms, max-mixture and sum-mixture of ℓp norms, small-support norms and the box-norm. We propose a novel data structure with tildeO(n (d + mmc(l)2 ) ) preprocessing time and space, and tq = tildeO(d + |S| · mmc(l)2) query time, for computing distances to a subset S of data points, where mmc(l) is a complexity-measure (concentration modulus) of the symmetric norm. When l = ℓp , this runtime matches the aforementioned state-of-art oracles.