The Library
Sublinear time approximation of the cost of a metric k-nearest neighbor graph
Tools
Czumaj, Artur and Sohler, Christian (2020) Sublinear time approximation of the cost of a metric k-nearest neighbor graph. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2020), Salt Lake City, Utah, USA, January 5-8, 2020, Salt Lake City, Utah, USA, 5-8 Jan 2020. Published in: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms pp. 2973-2992. ISBN 9781611975994. doi:10.1137/1.9781611975994.180
|
PDF
WRAP-sublinear-time-approximation-cost-metric-k-nearest-neighbor-graph-Czumaj-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1156Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611975994.180
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 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 Õ∊(n2/k) time with probability at least approximates cost(G) to within a factor of 1 + ∊. Next, we present a more elaborate sublinear algorithm that in time Õϵ(min{nk3/2, n2/k}) computes an estimate of cost(G) that satisfies with probability at least
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 estimates cost(G) to within a 1 + ∊ factor requires Ω(n2/k) time. Similarly, any algorithm that with probability at least estimates cost(G) to within an additive error term ϵ · (mst(X) + cost(X)) requires Ωϵ(min{nk3/2, n2/k}) time.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Metric spaces, Approximation theory, Random variables | |||||||||
Journal or Publication Title: | Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms | |||||||||
Publisher: | SIAM | |||||||||
ISBN: | 9781611975994 | |||||||||
Official Date: | 2020 | |||||||||
Dates: |
|
|||||||||
Page Range: | pp. 2973-2992 | |||||||||
DOI: | 10.1137/1.9781611975994.180 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Re-use Statement: | First Published in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2020) published by the Society for Industrial and Applied Mathematics (SIAM). Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 23 December 2019 | |||||||||
Date of first compliant Open Access: | 27 April 2020 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2020), Salt Lake City, Utah, USA, January 5-8, 2020 | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Salt Lake City, Utah, USA | |||||||||
Date(s) of Event: | 5-8 Jan 2020 | |||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year