Hölder homeomorphisms and approximate nearest neighbors

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten

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

2 Scopus citations

Abstract

We study bi-Hölder homeomorphisms between the unit spheres of finite-dimensional normed spaces and use them to obtain better data structures for high-dimensional Approximate Near Neighbor search (ANN) in general normed spaces. Our main structural result is a finite-dimensional quantitative version of the following theorem of Daher (1993) and Kalton (unpublished). Every d-dimensional normed space X admits a small perturbation Y such that there is a bi-Hölder homeomorphism with good parameters between the unit spheres of Y and Z, where Z is a space that is close to ℓ d 2 . Furthermore, the bulk of this article is devoted to obtaining an algorithm to compute the above homeomorphism in time polynomial in d. Along the way, we show how to compute efficiently the norm of a given vector in a space obtained by the complex interpolation between two normed spaces. We demonstrate that, despite being much weaker than bi-Lipschitz embeddings, such homeomorphisms can be efficiently utilized for the ANN problem. Specifically, we give two new data structures for ANN over a general d-dimensional normed space, which for the first time achieve approximation d o(1) , thus improving upon the previous general bound O(√d) that is directly implied by John's theorem.

Original languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages159-169
Number of pages11
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October
ISSN (Print)0272-5428

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
CountryFrance
CityParis
Period10/7/1810/9/18

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Complex interpolation
  • John's theorem
  • Near neighbor search

Fingerprint Dive into the research topics of 'Hölder homeomorphisms and approximate nearest neighbors'. Together they form a unique fingerprint.

  • Cite this

    Andoni, A., Naor, A., Nikolov, A., Razenshteyn, I., & Waingarten, E. (2018). Hölder homeomorphisms and approximate nearest neighbors. In M. Thorup (Ed.), Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 (pp. 159-169). [8555102] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2018-October). IEEE Computer Society. https://doi.org/10.1109/FOCS.2018.00024