Estimating and detecting similarities in datasets is a fundamental problem in computer science, and a basic subroutine in most industry-scale ML applications, from optimization [1]}, [2]}, [3]} and reinforcement learning [4]}, to discrepancy theory [5]} and covariance estimation [6]}, [7]}, Kernel SVMs [8]}, [9]}, compression and clustering [10]}, [11]},
to mention a few.
Such applications often need to quickly compute distances of
online (test) points to a subset of points in the input data set (e.g., the training data) for transfer-learning and classification. These applications have motivated the notion of distance oracles (DO) [12]}, [13]}, [14]}: In this problem,
the goal is to preprocess a dataset of \(n\)  input points \(X = (x_1, x_2,\ldots , x_n)\) 
in some \(d\) -dimensional metric space, into a small-space data structure which,
given a query vector \(q\)  and a subset \(\mathsf {S} \subseteq [n]\) , can quickly estimate all the distances \(\mathsf {d}(q,x_i)\)  of \(q\)  to \(\mathsf {S}\)  (note that the problem of estimating a single distance \(\mathsf {d}(q,x_i)\)  is not interesting in \(\mathbb {R}^d\) , as this can be trivially done in \(O(d)\)  time, which is necessary to merely read the query \(q\) ). The most well-studied case (in both theory and practice) is when the metric space is in fact a normed space, i.e., the data points
\(\lbrace x_i\rbrace _{i\in [n]}\in \mathbb {R}^d\)  are endowed with some predefined
norm \(\Vert \cdot \Vert \) , and the goal is to quickly estimate \(\Vert x_i-q\Vert \)  simultaneously for all \(i\) , i.e., in time
\(\ll nd\)  which is the trivial query time.
Distance oracles can therefore be viewed as generalizing matrix-vector multiplication: for the inner-product distance function \(\langle x_i,q \rangle \) , the query asks to approximate \(X\cdot q\)  in \(\ll nd\)  time.
