Better ε-dependencies for offline approximate nearest neighbor search, euclidean minimum spanning trees, and ε-kernels

Sunil Arya, Timothy M. Chan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recently, Arya, da Fonseca, and Mount [STOC 2011, SODA 2012] made notable progress in improving the ε- dependencies in the space/query-time tradeoffs for (1 + ε)-factor approximate nearest neighbor search in fixeddimensional Euclidean spaces. However, ε-dependencies in the preprocessing time were not considered, and so their data structures cannot be used to derive faster algorithms for offline proximity problems. Known algorithms for many such problems, including approximate bichromatic closest pair (BCP) and approximate Euclidean minimum spanning trees (EMST), typically have factors near (1/ε)d/2±O(1) in the running time when the dimension d is a constant. We describe a technique that breaks the (1/ε)d/2 barrier and yields new results for many well-known proximity problems, including: an O((1/ε)d/3+O(1)n)-time randomized algorithm for approximate BCP, an O((1/ε)d/3+O(1)n log n)-time algorithm for approximate EMST, and an O(n log n + (1/ε)d/3+O(1)n)-time algorithm to answer n approximate nearest neighbor queries on n points. Using additional bit-packing tricks, we can shave off the log n factor for EMST, and even move most of the "-factors to a sublinear term. The improvement arises from a new time bound for exact "discrete Voronoi diagrams", which were previously used in the construction of ε-kernels (or extent-based coresets), a well-known tool for another class of fundamental problems. This connection leads to more results, including: a streaming algorithm to maintain an approximate diameter in O((1/ε)d/3+O(1)) time per point using O((1/ε)d/2+O(1)) space, and a streaming algorithm to maintain an ε;- kernel in O((1/ε)d/4+O(1)) time per point using O((1/ε)d=2+O(1)) space. Copyright is held by the owner/author(s).

Original languageEnglish (US)
Title of host publicationProceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014
PublisherAssociation for Computing Machinery
Pages416-425
Number of pages10
ISBN (Print)9781450325943
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event30th Annual Symposium on Computational Geometry, SoCG 2014 - Kyoto, Japan
Duration: Jun 8 2014Jun 11 2014

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other30th Annual Symposium on Computational Geometry, SoCG 2014
CountryJapan
CityKyoto
Period6/8/146/11/14

Keywords

  • Bichromatic closest pair
  • Coresets
  • Minimum spanning tree
  • Nearest neighbor
  • ε-dependencies

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Better ε-dependencies for offline approximate nearest neighbor search, euclidean minimum spanning trees, and ε-kernels'. Together they form a unique fingerprint.

  • Cite this

    Arya, S., & Chan, T. M. (2014). Better ε-dependencies for offline approximate nearest neighbor search, euclidean minimum spanning trees, and ε-kernels. In Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014 (pp. 416-425). (Proceedings of the Annual Symposium on Computational Geometry). Association for Computing Machinery. https://doi.org/10.1145/2582112.2582161