Our distance oracle follows the “sketch-and-decode” approach, which was extensively used in many other sublinear-time compressed sensing and sparse recovery problems [1]}, [2]}, [3]}, [4]}, [5]}.
The main idea is to compress the data points into smaller dimension by computing, for each data point \(x_i\in \mathbb {R}^d\) , a (randomized) linear sketch \(\Phi \cdot x_i\in \mathbb {R}^{d^{\prime }}\)  with \(d^{\prime }\ll d\)  at preprocessing time, where \(\Phi x_i\)  is an unbiased estimator of \(\Vert x_i\Vert \) .
At query time, given a query point \(q\in \mathbb {R}^d\) , we analogously compute its sketch \(\Phi q\) . By linearity of \(\Phi \) , the distance between \(q\)  and \(x_i\)  (i.e., \(\ell (q-x_i)\) ) can be trivially decoded from the sketch difference \(\Phi q-\Phi x_i\) . As we shall see, this simple virtue of linearity is less obvious to retain when dealing with general symmetric norms.
