2fc6b8a3fc23108f184daa4759024c25-Paper-Conference.pdf

IntheDistanceOracle problem,thegoalistopreprocess nvectorsx1,x2,...,xn in a d-dimensional metric space(Xd, l) into a cheap data structure, so that given a query vectorq Xd and a subsetS [n] of the input data points, all distances q xi l forxi S canbequicklyapproximated(fasterthanthetrivial d|S|querytime).