DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.66

Fast Nearest Neighbor Search for 𝓁_p Metrics

Authors: Robert Krauthgamer and Nir Petruschka

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

The Nearest Neighbor Search (NNS) problem asks to design a data structure that preprocesses an n-point dataset X lying in a metric space ℳ, so that given a query point q ∈ ℳ, one can quickly return a point of X minimizing the distance to q. The efficiency of such a data structure is evaluated primarily by the amount of space it uses and the time required to answer a query. We focus on the fast query-time regime, which is crucial for modern large-scale applications, where datasets are massive and queries must be processed online, and is often modeled by query time poly(d log n) when ℳ is a d-dimensional normed space. Our main result is such a randomized data structure for NNS in 𝓁_p^d spaces, p > 2, that achieves p^{O(1) + log log p} approximation with fast query time and poly(dn) space. Our data structure improves, or is incomparable to, the state-of-the-art for the fast query-time regime from [Bartal and Gottlieb, TCS 2019] and [Krauthgamer, Petruschka and Sapir, FOCS 2025].

Cite as

Robert Krauthgamer and Nir Petruschka. Fast Nearest Neighbor Search for 𝓁_p Metrics. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{krauthgamer_et_al:LIPIcs.SoCG.2026.66,
  author =	{Krauthgamer, Robert and Petruschka, Nir},
  title =	{{Fast Nearest Neighbor Search for 𝓁\underlinep Metrics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{66:1--66:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.66},
  URN =		{urn:nbn:de:0030-drops-258737},
  doi =		{10.4230/LIPIcs.SoCG.2026.66},
  annote =	{Keywords: Nearest neighbor search, metric embeddings, 𝓁\underlinep norm}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.66

Lipschitz Decompositions of Finite 𝓁_{p} Metrics

Authors: Robert Krauthgamer and Nir Petruschka

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

Lipschitz decomposition is a useful tool in the design of efficient algorithms involving metric spaces. While many bounds are known for different families of finite metrics, the optimal parameters for n-point subsets of 𝓁_p, for p > 2, remained open, see e.g. [Naor, SODA 2017]. We make significant progress on this question and establish the bound β = O(log^{1-1/p} n). Building on prior work, we demonstrate applications of this result to two problems, high-dimensional geometric spanners and distance labeling schemes. In addition, we sharpen a related decomposition bound for 1 < p < 2, due to Filtser and Neiman [Algorithmica 2022].

Cite as

Robert Krauthgamer and Nir Petruschka. Lipschitz Decompositions of Finite 𝓁_{p} Metrics. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{krauthgamer_et_al:LIPIcs.SoCG.2025.66,
  author =	{Krauthgamer, Robert and Petruschka, Nir},
  title =	{{Lipschitz Decompositions of Finite 𝓁\underline\{p\} Metrics}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.66},
  URN =		{urn:nbn:de:0030-drops-232182},
  doi =		{10.4230/LIPIcs.SoCG.2025.66},
  annote =	{Keywords: Lipschitz decompositions, metric embeddings, geometric spanners}
}

Search Results

Documents authored by Petruschka, Nir

Fast Nearest Neighbor Search for 𝓁_p Metrics

Abstract

Cite as

Lipschitz Decompositions of Finite 𝓁_{p} Metrics

Abstract

Cite as

Thanks for your feedback!

Could not send message