Locality Sensitive Hashing in Hyperbolic Space

Abstract

For a metric space $(X,d)$, a family $\mathcal{H}$ of locality sensitive hash functions is called $(r,cr,p_1,p_2)$ sensitive if a randomly chosen function $h\in \mathcal{H}$ has probability at least $p_1$ (at most $p_2$) to map any $a,b\in X$ in the same hash bucket if $d(a,b)\le r$ (or $d(a,b)\ge cr$). Locality Sensitive Hashing (LSH) is one of the most popular techniques for approximate nearest-neighbor search in high-dimensional spaces, and has been studied extensively for Hamming, Euclidean, and spherical geometries. An $(r,cr,p_1,p_2)$-sensitive hash function enables approximate nearest neighbor search (i.e., returning a point within distance $cr$ from a query $q$ if there exists a point within distance $r$ from $q$) with space $O(n^{1+\ddot{I}})$ and query time $O(n^{\ddot{I}})$ where $\ddot{I}=\frac{\log 1/p_1}{\log 1/p_2}$. But LSH for hyperbolic spaces ${\mathbb{H}}^d$ remains largely unexplored. In this work, we present the first LSH construction native to hyperbolic space. For the hyperbolic plane $(d=2)$, we show a construction achieving $\ddot{I}\le 1/c$, based on the hyperplane rounding scheme. For general hyperbolic spaces $(d\ge 3)$, we use dimension reduction from ${\mathbb{H}}^d$ to ${\mathbb{H}}^2$ and the 2D hyperbolic LSH to get $\ddot{I}\le 1.59/c$. On the lower bound side, we show that the lower bound on $\ddot{I}$ of Euclidean LSH extends to the hyperbolic setting via local isometry, therefore giving $\ddot{I}\ge 1/c^2$.

22 pages, 8 figures, socg 2026 paper