Abstract
In the Distance Oracle problem, the goal is to preprocess $n$ vectors $x_1, x_2, \dots, x_n$ in a $d$-dimensional metric space $(\mathbb{X}^d, \| \cdot \|_l)$ into an efficient data structure. Given a query vector $q \in \mathbb{X}^d$ and a subset $S \subseteq [n]$ of the input data points, the oracle must quickly approximate all distances $\| q - x_i \|_l$ for $x_i \in S$ faster than the trivial $O(d|S|)$ query time. While optimal data structures exist for standard $\ell_p$ norms, this paper introduces a fast $(1+\varepsilon)$ distance oracle for the broader class of symmetric norms. This class includes Orlicz norms, top-$k$ norms, max-mixture and sum-mixture of $\ell_p$ norms, and the box-norm. The proposed data structure achieves $\tilde{O}(n (d + \mathrm{mmc}(l)^2 ) )$ preprocessing time and $\tilde{O}(d + |S| \cdot \mathrm{mmc}(l)^2)$ query time, where $\mathrm{mmc}(l)$ is the concentration modulus of the norm.
Introduction
Efficient similarity search and distance estimation are foundational to modern machine learning, data mining, and high-dimensional geometry. The standard approach to these problems involves "Distance Oracles"—data structures that use sketching or dimensionality reduction to provide fast approximations. While the behavior of $\ell_p$ norms is well-understood, real-world applications often utilize more complex metrics that are symmetric (invariant to the sign and permutation of coordinates) but do not fit the standard $\ell_p$ mold.
This research addresses a fundamental question: Is symmetry alone sufficient to guarantee efficient dimensionality reduction? By providing a unified framework for any symmetric norm, the authors bridge the gap between ad-hoc sketching techniques and a generalized theory of metric embeddings.
Methodology
The authors propose a "sketch-and-decode" framework enhanced by three primary innovations designed to handle the complexities of general symmetric norms.
1. Layer Approximation
Building on the Indyk-Woodruff framework, the authors decompose vectors into magnitude-based "layers" (e.g., coordinates with values between $2^i$ and $2^{i+1}$). Because symmetric norms are invariant to coordinate order, the total norm can be estimated by counting how many coordinates fall into each layer. This reduces the high-dimensional distance calculation to a lower-dimensional counting problem.
2. Shared Randomness
To optimize space and time, the authors utilize shared randomness across all data points. By using the same set of random coordinate subsets for the entire dataset, they significantly reduce the number of sketches required to maintain accuracy, solving the "layer explosion" problem found in previous theoretical models.
3. Locate-and-Verify Decoding
Perhaps the most significant innovation is the shift from "reconstruction" to "verification." Traditional sparse recovery techniques attempt to reconstruct coordinate values from a sketch, which is computationally expensive. The authors observe that in a distance oracle setting, the original data points are available in memory. Therefore, the sketch only needs to locate potential "heavy hitter" coordinates (those contributing most to the distance). The oracle then verifies these values by looking them up in the original data, drastically accelerating the query phase.
Theoretical Results
The complexity of the proposed oracle is governed by the maximum modulus of concentration ($mmc(l)$), a parameter measuring how much the norm concentrates on a random sphere.
Complexity Bounds
- Preprocessing Time and Space: $\tilde{O}(n(d + mmc(l)^2))$
- Query Time: $\tilde{O}(d + |S| \cdot mmc(l)^2)$ for a subset $S$ of data points.
For standard $\ell_p$ norms, these runtimes match the current state-of-the-art. Furthermore, the authors demonstrate that the dependence on $mmc(l)$ is near-optimal, matching known lower bounds for streaming norm estimation.
Significance and Applications
This work provides a single, unified data structure capable of handling a diverse array of norms used in practice:
- Orlicz Norms: Used in harmonic analysis and stochastic processes.
- Top-$k$ Norms: Frequently used for robustness to outliers by considering only the $k$ largest coordinates.
- $k$-Support Norms: Used in machine learning for sparse recovery tasks.
- Box-Norms and Mixtures: Used in complex optimization and clustering problems.
By proving that any symmetric norm can be efficiently sketched, the authors provide a powerful tool for researchers who previously had to derive custom sketching algorithms for every new metric.
Limitations and Future Work
While the framework is highly general, its efficiency is tied to the concentration modulus $mmc(l)$. For norms where $mmc(l)$ is large, query times may degrade. Whether this dependence is an inherent property of symmetric norms or an artifact of current techniques remains an open question. Additionally, the framework relies strictly on symmetry; extending these fast oracles to asymmetric norms—where the order or sign of coordinates matters—remains a significant challenge for future research.
Summary updated