What question did this study set out to answer?

This research aims to develop a fast and efficient data structure for nearest neighbor search in high-dimensional L_p metric spaces.

May 29, 2026Open Access

Fast Nearest Neighbor Search for 𝓁ₚ Metrics

Key Points

This research aims to develop a fast and efficient data structure for nearest neighbor search in high-dimensional L_p metric spaces.
Developed a randomized data structure for nearest neighbor search in L_p^d spaces where p > 2.
Evaluated efficiency based on query time and space requirements.
Compared performance with existing state-of-the-art methods.
Achieved an approximation of p^{O(1) + log log p} for nearest neighbor queries.
Provided fast query time modeled as poly(d log n) with space complexity of poly(dn).
Outperformed or was comparable to previous methods in fast query-time regimes.

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 𝓁ₚᵈ 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.

Bookmark

View Full Paper