Locality Sensitive Hashing in Hyperbolic Space
Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, Cheng Xin · 2026
Read Locality Sensitive Hashing in Hyperbolic Space by Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, Cheng Xin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19724.txt.
Introduction
Deng and co-authors build the first locality sensitive hashing scheme made for hyperbolic space. Such hashing speeds up near-neighbor search in high-dimensional data. Close points should land in the same bucket more often than far ones. For the hyperbolic plane they base the method on hyperplane rounding. For higher dimensions they first reduce the space to the plane. They also show that the known Euclidean lower bound carries over. Their bounds tie hash quality to the distance stretch factor.
Catalog record
| CREATOR | Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, Cheng Xin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47980 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.19724
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Locality Sensitive Hashing in Hyperbolic Space Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, Cheng Xin Abstract For a metric space ( X , d ) (X,d) , a family ℋ \mathcal{H} of locality sensitive hash functions is called ( r , c r , p 1 , p 2 ) (r,cr,p_{1},p_{2}) sensitive if a randomly chosen function h ∈ ℋ h\in\mathcal{H} has probability at least p 1 p_{1} (at most p 2 p_{2} ) to map any a , b ∈ X a,b\in X in the same hash bucket if d ( a , b ) ≤ r d(a,b)\leq r (or d ( a , b ) ≥ c r d(a,b)\geq 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 , c r , p 1 , p 2 ) (r,cr,p_{1},p_{2}) -sensitive hash function enables approximate nearest neighbor search (i.e., returning a point within distance c r cr from a query q q if there exists a point within distance r r from q q ) with space O ( n 1 + ρ ) O(n^{1+\rho}) and query time O ( n ρ ) O(n^{\rho}) where ρ = log 1 / p 1 log 1 / p 2 \rho=\frac{\log 1/p_{1}}{\log 1/p_{2}} . But LSH for hyperbolic spaces ℍ d \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 ) (d=2) , we show a construction achieving ρ ≤ 1 / c \rho\leq 1/c , based on the hyperplane rounding scheme. For general hyperbolic spaces ( d ≥ 3 ) (d\geq 3) , we use dimension reduction from ℍ d \mathbb{H}^{d} to ℍ 2 \mathbb{H}^{2} and the 2D hyperbolic LSH to get ρ ≤ 1.59 / c \rho\leq 1.59/c . On the lower bound side, we show that the lower bound on ρ \rho of Euclidean LSH extends to the hyperbolic setting via local isometry, therefore giving ρ ≥ 1 / c 2 \rho\geq 1/c^{2} . Department of Computer Science, Rutgers University, [email protected] Department of Computer Science, Rutgers University, [email protected][0000-0001-5083-6082] Department of Mathematics, Rutgers University, [email protected] Department of Mathematics, Rutgers University, [email protected] Department of Computer Science, Rutgers University, [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10010061.10010063¡/concept_id¿ ¡concept_desc¿Theory of computation Computational geometry¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10010061.10010068¡/concept_id¿ ¡concept_desc¿Theory of computation Random projections and metric embeddings¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010055.10010060¡/concept_id¿ ¡concept_desc¿Theory of computation Nearest neighbor algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Computational geometry ccs Theory of computation Random projections and metric embeddings ccs Theory of computation Nearest neighbor algorithms keywords Locality Sensitive Hashing, Hyperbolic Geometry, Dimension Reduction, Approximate Nearest Neighbor Search † † runningauthor: C. Deng, J. Gao, K. Lu, F. Luo, C. Xin † † copyright: Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo and Cheng Xin † † related-version: Full Version : URL to related version † † funding: The authors would like to acknowledge funding support from NSF through CCF-2118953, DMS-2311064, DMS-2220271, IIS-2229876, CNS-2515159. † † editors: Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri † † event-title: 42nd International Symposium on Computational Geometry (SoCG 2026) † † event-shorttitle: SoCG 2026 † † event-acronym: SoCG † † year: 2026 † † event-date: June 2–5, 2026 † † event-location: New Brunswick, NJ, USA † † event-logo: socg-logo.pdf † † series-volume: 367 † † articleno: XX 1 Introduction Locality Sensitive Hashing (LSH) is a hashing scheme in which similar items are more likely to hash to the same bucket. Indyk and Motwani, in their seminal work [ 25 , 24 ] , developed LSH for general metric spaces and provided hash function constructions for the Hamming distance. The LSH framework provides an efficient data structure for the Approximate Nearest Neighbor Search (ANNS) problem, which is particularly challenging in the high-dimensional regimes. Since then, LSH has been developed for various similarity measures such as \ell_{1} [ 3 , 34 ] , \ell_{2} [ 18 , 4 ] , \ell_{p} [ 18 ] , cosine similarity [ 15 ] , Jaccard similarity [ 10 , 11 ] , angular (spherical) distances [ 46 ] , etc. With support for similarity search, data independence, mild dependence on data dimension, and simplicity in implementation, LSH serves as an algorithmic tool for classical problems such as clustering, near-duplicate detection, and efficient information retrieval for very large datasets. LSH has also been used widely in database and machine learning pipelines in industry [ 21 , 12 , 16 , 43 , 41 , 17 , 31 , 2 , 7 ] . For a nice survey, please refer to [ 4 ] . Hyperbolic geometry is a non-Euclidean geometry. It drops the parallel postulate of Euclidean geometry. In hyperbolic geometry, for any line and a point not on that line, there are at least two distinct lines through the point that do not intersect the original line. Hyperbolic geometry has received increasing attention in modern data analysis because it naturally models hierarchical, tree-like, and exponentially branching structures that arise throughout science and technology. Unlike Euclidean spaces, where volume grows polynomially, hyperbolic spaces exhibit exponential volume growth, matching the combinatorial growth of hierarchies, taxonomies, knowledge graphs, and high-dimensional networks with latent tree-like structure. This geometric compatibility yields embeddings with dramatically reduced distortion: objects that are far apart in a hierarchy can be faithfully separated, and geodesics efficiently capture ancestry, flow, and community structure. As a result, hyperbolic embeddings now underpin state-of-the-art methods in network representation learning, hierarchical clustering, and discrete geometric data analysis [ 37 , 23 , 20 , 47 , 19 , 13 , 14 , 48 , 29 , 45 ] . It is also the most important space representing the negative curvature phenomena arising from complex geometric situations [ 33 , 44 ] . Namely, according to Gromov’s hyperbolization program [ 22 ] , spaces with complicated topology tend to resemble spaces with negative curvature. Hyperbolic geometry provides the fundamental model for negatively curved spaces, offering the canonical framework in which their curvature and geometric behavior are understood. Moreover, the hyperbolic plane offers an unusually tractable analytic structure: its constant negative curvature provides explicit formulas for distance, geodesics, convexity, and isometries, enabling efficient optimization for machine-learning tasks. Its rich isometry group and uniformization properties are directly linked to complex analysis and conformal representations, providing tools that scale from theoretical guarantees to practical algorithms for dimensionality reduction, visualization, and manifold learning. These applications provide strong motivation for developing efficient algorithms in hyperbolic space, and in this paper, we study locality-sensitive hashing in hyperbolic space, a topic that, to our best knowledge, has not been studied before. 1.1 LSH Framework We first recall the formal definitions on LSH and the Approximate Nearest Neighbor Search (ANNS) problem. Definition 1 (Locality Sensitive Hashing) . Consider a metric space (X,d) 1 1 1 LSH is well-defined with a general dissimilarity measure, i.e., the triangle inequality does not necessarily hold. However, the approximate nearest neighbor search problem is typically studied in a metric space. Thus, we define LSH within the same context.