Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph

.Let \((X,d)\) be an \(n\)-point metric space. We assume that \((X,d)\) is given in the distance oracle model, that is, \(X = \{1, , n\}\) and for every pair of points \(x, y\) from \(X\) we can query their distance \(d(x,y)\) in constant time. A \(k\)-nearest neighbor (\(k\)-NN) graph for \((X,d)\) is a directed graph \(G = (V,E)\) that has an edge to each of \(v\)'s \(k\) nearest neighbors. We use \({cost}(G)\) to denote the sum of edge weights of \(G\). In this paper, we study the problem of approximating \({cost}(G)\) in sublinear time when we are given oracle access to the metric space \((X,d)\) that defines \(G\). Our goal is to develop an algorithm that solves this problem faster than the time required to compute \(G\). We first present an algorithm that in \({O}ε(n^2/k)\) time with probability at least \( 23\) approximates \({cost}(G)\) to within a factor of \(1 + ε\). Next, we present a more elaborate sublinear algorithm that in time \({O}ε(min \{n k3/2, n^2/k\})\) computes an estimate \(cost̄\) of \({cost}(G)\) that satisfies with probability at least \( 23\) \(|{cost}(G) -{cost̄} | ≤ ε · ({cost}(G) +{mst}(X))\), where \({mst}(X)\) denotes the cost of the minimum spanning tree of \((X,d)\). Further, we complement these results with near matching lower bounds. We show that any algorithm that for a given metric space \((X,d)\) of size \(n\), with probability at least \( 23\), estimates \({cost}(G)\) to within a \(1 + ε\) factor requires \(Ω (n^2/k)\) time. Similarly, any algorithm that with probability at least \( 23\) estimates \({cost}(G)\) to within an additive error term \(ε · ({mst}(X) +{cost}(X))\) requires \(Ωε(min \{n k3/2, n^2/k\})\) time.