Fast Distance Oracles for Any Symmetric Norm

This primitive is a basic subroutine in machine learning, data mining and similarity search applications. In the case of \ell_p norms, the problem is well understood, and optimal data structures are known for most values of p . This class includes \ell_p norms and Orlicz norms as special cases, as well as other norms used in practice, e.g. We propose a novel data structure with \tilde{O}(n (d \mathrm{mmc}(l) 2)) preprocessing time and space, and t_q \tilde{O}(d n \cdot \mathrm{mmc}(l) 2) query time, where \mathrm{mmc}(l) is a complexity-measure (modulus) of the symmetric norm under consideration.