This problem can be viewed as an online version of the (approximate) closest-pair problem [1]}, which asks to find the closest pair of points among an offline batch of data points \( X = x_1,\ldots , x_n \in \mathbb {R}^d\) , or equivalently, the smallest entry of the covariance matrix \(X X^\top \) . One major (theoretical) advantage of the offline case is that it enables the use of fast matrix-multiplication (FMM) to speed-up the computation of the covariance matrix [1]}, [3]}, [4]}, [5]} (i.e., sub-linear amortized per query). By contrast, in the online setting such speedups are conjectured to be impossible [6]}, [7]}.
