Robust Proximity Search for Balls Using Sublinear Space

Sariel Har-Peled; Nirman Kumar

doi:10.1007/s00453-016-0254-4

Robust Proximity Search for Balls Using Sublinear Space

Sariel Har-Peled, Nirman Kumar

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Given a set of n disjoint balls b₁, ⋯ , b_n in IRd, we provide a data structure of near linear size that can answer (1 ± ε) -approximate kth-nearest neighbor queries on the balls in O(log n+ 1 / ε^d) time, where k and ε may be provided at query time. If k and ε are provided in advance, we provide a data structure to answer such queries requiring O(n / k) space; that is, the data structure requires sublinear space if k is sufficiently large.

Original language	English (US)
Pages (from-to)	279-299
Number of pages	21
Journal	Algorithmica
Volume	80
Issue number	1
DOIs	https://doi.org/10.1007/s00453-016-0254-4
State	Published - Jan 1 2018

Keywords

Approximation algorithms
Data structures
Proximity search

ASJC Scopus subject areas

Computer Science(all)
Computer Science Applications
Applied Mathematics

Online availability

10.1007/s00453-016-0254-4

Library availability

Discover UIUC Full Text

Cite this

@article{4060252b771b487f8cd287566f041e0d,

title = "Robust Proximity Search for Balls Using Sublinear Space",

abstract = "Given a set of n disjoint balls b1, ⋯ , bn in IRd, we provide a data structure of near linear size that can answer (1 ± ε) -approximate kth-nearest neighbor queries on the balls in O(log n+ 1 / εd) time, where k and ε may be provided at query time. If k and ε are provided in advance, we provide a data structure to answer such queries requiring O(n / k) space; that is, the data structure requires sublinear space if k is sufficiently large.",

keywords = "Approximation algorithms, Data structures, Proximity search",

author = "Sariel Har-Peled and Nirman Kumar",

note = "Funding Information: Work on this paper was partially support by NSF AF awards CCF-0915984, CCF-1421231, and CCF-1217462. Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/s00453-016-0254-4",

language = "English (US)",

volume = "80",

pages = "279--299",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Robust Proximity Search for Balls Using Sublinear Space

AU - Har-Peled, Sariel

AU - Kumar, Nirman

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Given a set of n disjoint balls b1, ⋯ , bn in IRd, we provide a data structure of near linear size that can answer (1 ± ε) -approximate kth-nearest neighbor queries on the balls in O(log n+ 1 / εd) time, where k and ε may be provided at query time. If k and ε are provided in advance, we provide a data structure to answer such queries requiring O(n / k) space; that is, the data structure requires sublinear space if k is sufficiently large.

AB - Given a set of n disjoint balls b1, ⋯ , bn in IRd, we provide a data structure of near linear size that can answer (1 ± ε) -approximate kth-nearest neighbor queries on the balls in O(log n+ 1 / εd) time, where k and ε may be provided at query time. If k and ε are provided in advance, we provide a data structure to answer such queries requiring O(n / k) space; that is, the data structure requires sublinear space if k is sufficiently large.

KW - Approximation algorithms

KW - Data structures

KW - Proximity search

UR - http://www.scopus.com/inward/record.url?scp=84997796215&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84997796215&partnerID=8YFLogxK

U2 - 10.1007/s00453-016-0254-4

DO - 10.1007/s00453-016-0254-4

M3 - Article

AN - SCOPUS:84997796215

SN - 0178-4617

VL - 80

SP - 279

EP - 299

JO - Algorithmica

JF - Algorithmica

IS - 1

ER -

Robust Proximity Search for Balls Using Sublinear Space

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this