Fast Distance Oracles for Any Symmetric Norm

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.