By “efficient”, we mean
small space and preprocessing time (ideally \(\sim nd\) ),
fast query time (\(\ll n|S|\)  for a query \((q,S\subseteq [n])\) ) and ideally supporting dynamic updates to \(x_i\) 's in \(\widetilde{O}(d)\)  time.
Indeed, most ML applications involve rapidly-changing dynamic datasets, and it is becoming increasingly clear that static data structures do not adequately capture the requirements of real-world applications [1]}, [2]}, [3]}. As such, it is desirable to design a dynamic distance oracle which has both small update time (\(t_u\) ) for adding/removing a point \(x_i \in \mathbb {R}^d\) , and small query time (\(t_q\) ) for distance estimation. We remark that most known DOs are dynamic by nature (as they rely on linear sketching techniques), but for general metrics (e.g., graph shortest-path or the \(\ell _\infty \)  norm) this is much less obvious, and indeed linearity of encoding/decoding will be a key challenge in our data structure (see next section).
The problem is formally defined as follows:
