Locality Sensitive Hashing in Hyperbolic Space

Abstract

Locality Sensitive Hashing (LSH) is a central technique for approximate nearest-neighbor search, but its classical theory is developed primarily for Hamming, Euclidean, and spherical geometries. This paper studies LSH in hyperbolic space, a natural model for hierarchical and negatively curved data. For the hyperbolic plane, we construct a native hyperbolic LSH family based on random geodesic partitions and obtain a performance exponent bounded by (1/c). For higher-dimensional hyperbolic spaces, we combine hyperbolic dimension reduction with the two-dimensional construction to obtain efficient LSH schemes. We also prove lower-bound behavior by relating hyperbolic geometry locally to Euclidean geometry.

Key Contributions

• Hyperbolic LSH construction: Introduces a native LSH scheme for the hyperbolic plane using random geodesics.
• Higher-dimensional extension: Combines dimension reduction from (\mathbb{H}^d) to (\mathbb{H}^2) with the two-dimensional LSH construction.
• Theoretical bounds: Establishes upper bounds for the LSH performance exponent and lower-bound phenomena inherited from local Euclidean structure.
• Algorithmic motivation: Connects approximate nearest-neighbor search to hierarchical, tree-like, and non-Euclidean data representations.

Citation

Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, and Cheng Xin. Locality Sensitive Hashing in Hyperbolic Space. In 42nd International Symposium on Computational Geometry (SoCG 2026), LIPIcs 367, 39:1-39:19, 2026.

BibTeX Citation

@inproceedings{deng2026hyperboliclsh,
  title={Locality Sensitive Hashing in Hyperbolic Space},
  author={Chengyuan Deng and Jie Gao and Kevin Lu and Feng Luo and Cheng Xin},
  booktitle={42nd International Symposium on Computational Geometry (SoCG 2026)},
  series={Leibniz International Proceedings in Informatics (LIPIcs)},
  volume={367},
  pages={39:1--39:19},
  year={2026},
  doi={10.4230/LIPIcs.SoCG.2026.39}
}

Links