Fast Distance Oracles for Any Symmetric Norm

Yichuan Deng, Zhao Song, Omri Weinstein +1

In the Distance Oracle problem, the goal is to preprocess $n$ vectors $x_1,x_2,\cdots ,x_n$ in a $d$-dimensional metric space $({\mathbb{X}}^d,\Vert \cdot {\Vert }_l)$ into a cheap data st…