Sublinear time approximation of the cost of a metric k-nearest neighbor graph

Preview

PDF WRAP-Sublinear-time-approximation-cost-metric-k-nearest-neighbor-graph-24.pdf - Accepted Version - Requires a PDF viewer. Download (910kB) | Preview

Request Changes to record.

Abstract

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 eduge to each of v's ka 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 Õε(n^2/k) time with probability at least 2/3 approximates cost(G) to within a factor of 1+ε. Next, we present a more elaborate sublinear algorithm that in time Õε(min{nk^3/2, n^2/k}) computes an estimate cost of cost(G) that satisfies with probability at least 2/3 |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 2/3, estimates cost(G) to within a 1+ε factor requires Ω(n^2/k) time. Similarly, any algorithm taht with probability at least 2/3 estimates cost(G) to wtihin an additive error term ε ⋅ (mst(X) + cost(X)) requires Ωε(min{nk^3/2, n^2/k}) time.

Request changes or add full text files to a record

Repository staff actions (login required)

View Item