The Library
Sublinear time approximation of the cost of a metric knearest neighbor graph
Tools
Czumaj, Artur and Sohler, Christian (2020) Sublinear time approximation of the cost of a metric knearest neighbor graph. In: Annual ACMSIAM Symposium on Discrete Algorithms (SODA'2020), Salt Lake City, Utah, USA, January 58, 2020, Salt Lake City, Utah, USA, 58 Jan 2020. Published in: Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms pp. 29732992. ISBN 9781611975994. doi:10.1137/1.9781611975994.180

PDF
WRAPsublineartimeapproximationcostmetricknearestneighborgraphCzumaj2020.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 npoint 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 knearest neighbor (kNN) 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 > Computer Science  
Library of Congress Subject Headings (LCSH):  Metric spaces, Approximation theory, Random variables  
Journal or Publication Title:  Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms  
Publisher:  SIAM  
ISBN:  9781611975994  
Official Date:  2020  
Dates: 


Date of first compliant deposit:  23 December 2019  
Page Range:  pp. 29732992  
DOI:  10.1137/1.9781611975994.180  
Status:  Peer Reviewed  
Publication Status:  Published  
Publisher Statement:  First Published in Proceedings of the 31st Annual ACMSIAM 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  
RIOXX Funder/Project Grant: 


Conference Paper Type:  Paper  
Title of Event:  Annual ACMSIAM Symposium on Discrete Algorithms (SODA'2020), Salt Lake City, Utah, USA, January 58, 2020  
Type of Event:  Conference  
Location of Event:  Salt Lake City, Utah, USA  
Date(s) of Event:  58 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