2026-07-20T05:11:24Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:25873 2026-06-23T12:59:59Z ddc:004 open_access
Fast Nearest Neighbor Search for 𝓁_p Metrics Krauthgamer, Robert Petruschka, Nir Nearest neighbor search metric embeddings 𝓁_p norm 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]. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Robert Krauthgamer and Nir Petruschka 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.66 urn:nbn:de:0030-drops-258737 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.66 eng https://creativecommons.org/licenses/by/4.0/legalcode