View PDF

Abstract:The Approximate Near Neighbor (ANN) problem is a cornerstone of high-dimensional data analysis. While Locality Sensitive Hashing (LSH) has been the classical paradigm, recent work has investigated Locality Sensitive Filtering (LSF), which can afford greater expressivity by allowing asymmetric regions to independently control queries and data updates. In its full generality, however, this framework can obscure the essential algorithmic ideas beneath substantial technical complexity.
In this work, we bridge classical LSH and modern LSF by providing a self-contained, streamlined treatment of angular distance on the unit sphere under symmetric Gaussian filters. Although specialized, this canonical setting -- monotonically equivalent to the widely used cosine similarity -- captures all key aspects of the problem, delivering a "guided tour" of the core mechanisms of locality-sensitive filtering and allowing us to expose all fundamental algorithmic and probabilistic ingredients, while retaining transparent notation and pedagogical clarity.
More precisely, we develop a treatment of Spherical-LSF that makes explicit the connection between the probabilistic behavior of Gaussian filters and the performance of the resulting data structure. Using elementary calculus, we derive sharp probability bounds and obtain a transparent proof of asymptotic optimality among schemes whose filter distribution is fixed independently of the input dataset. We further exploit the specific structure of Gaussian filters to obtain an efficient implementation while avoiding much of the technical machinery required by the general LSF framework.
Overall, our results offer a self-contained and accessible entry point to locality-sensitive filtering, while providing a unified view of its main probabilistic and algorithmic principles.

Submission history

From: Alessandro Straziota [view email]
[v1] Mon, 27 Apr 2026 11:14:16 UTC (452 KB)
[v2] Mon, 10 Aug 2026 12:06:23 UTC (232 KB)