For a metric space (X, d), a family ℋ of locality sensitive hash functions is called (r, cr, p₁, p₂) sensitive if a randomly chosen function h ∈ ℋ has probability at least p₁ (at most p₂) to map any a, b ∈ X in the same hash bucket if d (a, b) ≤ r (or d (a, b) ≥ 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₁, p₂) -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+ρ) and query time O (n^ρ) where ρ = (log 1/p₁) / (log 1/p₂). But LSH for hyperbolic spaces ℍᵈ 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 ρ ≤ 1/c, based on the hyperplane rounding scheme. For general hyperbolic spaces (d ≥ 3), we use dimension reduction from ℍᵈ to ℍ² and the 2D hyperbolic LSH to get ρ ≤ 1. 59/c. On the lower bound side, we show that the lower bound on ρ of Euclidean LSH extends to the hyperbolic setting via local isometry, therefore giving ρ ≥ 1/c².
Deng et al. (Thu,) studied this question.