Home Bookmarks Papers Blog

Fast Construction of Nets in Low Dimensional Metrics, and Their Applications

Sariel Har-Peled and Manor Mendel.

We present a near linear time algorithm for constructing hierarchical nets for a finite metric space with low doubling dimension. As an applications of this, we show how one can construct well-separated pairs decomposition of such a space with linear number of pairs. Furthermore, we show how one can construct, in near linear time, a data-structure of near linear size, for answering approximate nearest neighbor queries in polylogarithmic time. This improves several recent results on those problems.

Postscript, PDF.
SiCOMP version

SoCG 05 talk slides.
slides source.
Man-Cho Anthony So read the paper carefully and figured out some missing details about how to maintain the friends list. Here is his writeup. Thanks Anthony!
@string{SICOMP = "SIAM J. Comput."}

  author       = {S. {Har-Peled} and M. Mendel},
  title        = {Fast Construction of Nets in Low Dimensional
                  Metrics, and Their Applications},
  journal      = SICOMP,
  year         = 2006,
  volume       = 35,
  number       = 5,
  pages        = {1148--1184}

Last modified: Mon Jun 26 09:50:03 CDT 2006