{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicbnfz6n5rgfxs72e4jyptkoozydatke6ruv5rzfbnu6dqcub6r3m",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhp6seuv46n2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.19724v1",
  "publishedAt": "2026-03-23T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Chengyuan Deng",
    "Jie Gao",
    "Kevin Lu",
    "Feng Luo",
    "Cheng Xin"
  ],
  "textContent": "**Authors:** Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, Cheng Xin\n\nFor 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)\\leq r$ (or $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, 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+ρ})$ and query time $O(n^ρ)$ where $ρ=\\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 $ρ\\leq 1/c$, based on the hyperplane rounding scheme. For general hyperbolic spaces $(d \\geq 3)$, we use dimension reduction from $\\mathbb{H}^d$ to $\\mathbb{H}^2$ and the 2D hyperbolic LSH to get $ρ\\leq 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 $ρ\\geq 1/c^2$.",
  "title": "Locality Sensitive Hashing in Hyperbolic Space"
}