Fast construction of nets in low dimensional metrics, and their applications

Sariel Har-Peled; Manor Mendel

doi:10.1145/1064092.1064117

Fast construction of nets in low dimensional metrics, and their applications

Sariel Har-Peled, Manor Mendel

Siebel School of Computing and Data Science

Research output: Contribution to conference › Paper › peer-review

Abstract

We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.

Original language	English (US)
Pages	150-158
Number of pages	9
DOIs	https://doi.org/10.1145/1064092.1064117
State	Published - 2005
Event	21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy Duration: Jun 6 2005 → Jun 8 2005

Other

Other	21st Annual Symposium on Computational Geometry, SCG'05
Country/Territory	Italy
City	Pisa
Period	6/6/05 → 6/8/05

Keywords

Approximate distance oracle
Approximate nearest neighbor search
Compact representation scheme
Doubling metrics
Spanners
Well separated pair decomposition

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Online availability

10.1145/1064092.1064117

Library availability

Discover UIUC Full Text

Cite this

@conference{19531a2fee2944ef9745acb374485507,

title = "Fast construction of nets in low dimensional metrics, and their applications",

abstract = "We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.",

keywords = "Approximate distance oracle, Approximate nearest neighbor search, Compact representation scheme, Doubling metrics, Spanners, Well separated pair decomposition",

author = "Sariel Har-Peled and Manor Mendel",

year = "2005",

doi = "10.1145/1064092.1064117",

language = "English (US)",

pages = "150--158",

note = "21st Annual Symposium on Computational Geometry, SCG'05 ; Conference date: 06-06-2005 Through 08-06-2005",

}

TY - CONF

T1 - Fast construction of nets in low dimensional metrics, and their applications

AU - Har-Peled, Sariel

AU - Mendel, Manor

PY - 2005

Y1 - 2005

N2 - We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.

AB - We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.

KW - Approximate distance oracle

KW - Approximate nearest neighbor search

KW - Compact representation scheme

KW - Doubling metrics

KW - Spanners

KW - Well separated pair decomposition

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

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

U2 - 10.1145/1064092.1064117

DO - 10.1145/1064092.1064117

M3 - Paper

AN - SCOPUS:33244493557

SP - 150

EP - 158

T2 - 21st Annual Symposium on Computational Geometry, SCG'05

Y2 - 6 June 2005 through 8 June 2005

ER -

Fast construction of nets in low dimensional metrics, and their applications

Abstract

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this