2026-07-20T05:45:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25845 2026-06-23T12:59:25Z ddc:004 open_access

Locality Sensitive Hashing in Hyperbolic Space Deng, Chengyuan Gao, Jie Lu, Kevin Luo, Feng Xin, Cheng Locality Sensitive Hashing Hyperbolic Geometry Dimension Reduction Approximate Nearest Neighbor Search 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 ℍ^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 ρ ≤ 1/c, based on the hyperplane rounding scheme. For general hyperbolic spaces (d ≥ 3), we use dimension reduction from ℍ^d 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². Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chengyuan Deng and Jie Gao and Kevin Lu and Feng Luo and Cheng Xin 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.39 urn:nbn:de:0030-drops-258454 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.39 eng https://creativecommons.org/licenses/by/4.0/legalcode