{"id":"arxiv/2603.21148","url":"https://arxiv.org/abs/2603.21148","tags":["cs.DS","cs.CG","math.MG"],"score":0,"title":"Fast Nearest Neighbor Search for $\\ell_p$ Metrics","domain":"cs.DS","source":"arxiv","authors":["Robert Krauthgamer","Nir Petruschka"],"reviews":0,"subject":"cs.DS","summary":"The Nearest Neighbor Search (NNS) problem asks to design a data structure that preprocesses an $n$-point dataset $X$ lying in a metric space $\\mathcal{M}$, so that given a query point $q \\in \\mathcal{M}$, 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-22","reactions":{}}