For \(\ell _p\)  norms, the DO problem is well-understood [1]},where the standard tool for constructing the data structure is via randomized linear sketching
: The basic idea is to reduce the dimension (\(d\) ) of the data points by applying some sketching matrix \(\Phi \in \mathbb {R}^{m \times d}\)  (\(m \ll d\) ) to each data point \(x_i\)  and store the sketch \(\Phi x_i\in \mathbb {R}^m\) . For a query point \(q\) , linearity then allows to estimate the distance from \(\Phi (q-x_i)\) . The seminal works of [2]}, [3]}, [4]}, [5]} developed polylogarithmic-size sketching methods for the \(\ell _2\) -norm, which was extended, in a long line of work, to any \(\ell _p\)  norm with \(0<p<2\)  [6]}, [7]}, [8]}.
For \(p>2\) , the sketch-size (\(d\) ) becomes polynomial, yet still sublinear in \(d\)  [9]}, [1]}.
