{"id":"https://openalex.org/W7140088592","doi":"https://doi.org/10.48550/arxiv.2603.19724","title":"Locality Sensitive Hashing in Hyperbolic Space","display_name":"Locality Sensitive Hashing in Hyperbolic Space","publication_year":2026,"publication_date":"2026-03-20","ids":{"openalex":"https://openalex.org/W7140088592","doi":"https://doi.org/10.48550/arxiv.2603.19724"},"language":null,"primary_location":{"id":"doi:10.48550/arxiv.2603.19724","is_oa":true,"landing_page_url":"https://doi.org/10.48550/arxiv.2603.19724","pdf_url":null,"source":{"id":"https://openalex.org/S4306400194","display_name":"arXiv (Cornell University)","issn_l":null,"issn":null,"is_oa":true,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I205783295","host_organization_name":"Cornell University","host_organization_lineage":["https://openalex.org/I205783295"],"host_organization_lineage_names":[],"type":"repository"},"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":null,"is_accepted":false,"is_published":false,"raw_source_name":null,"raw_type":"article"},"type":"preprint","indexed_in":["datacite"],"open_access":{"is_oa":true,"oa_status":"green","oa_url":"https://doi.org/10.48550/arxiv.2603.19724","any_repository_has_fulltext":true},"authorships":[{"author_position":"first","author":{"id":"https://openalex.org/A5006452312","display_name":"Chengyuan Deng","orcid":"https://orcid.org/0000-0002-2586-3430"},"institutions":[],"countries":[],"is_corresponding":true,"raw_author_name":"Deng, Chengyuan","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"middle","author":{"id":"https://openalex.org/A5130363550","display_name":"Jie Gao","orcid":null},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Gao, Jie","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"middle","author":{"id":"https://openalex.org/A5130402745","display_name":"Kevin Lu","orcid":null},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Lu, Kevin","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"middle","author":{"id":"https://openalex.org/A5130408664","display_name":"Feng Luo","orcid":null},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Luo, Feng","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"last","author":{"id":"https://openalex.org/A5007764603","display_name":"Cheng Xin","orcid":"https://orcid.org/0009-0003-7577-2080"},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Xin, Cheng","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]}],"institutions":[],"countries_distinct_count":0,"institutions_distinct_count":5,"corresponding_author_ids":["https://openalex.org/A5006452312"],"corresponding_institution_ids":[],"apc_list":null,"apc_paid":null,"fwci":null,"has_fulltext":false,"cited_by_count":0,"citation_normalized_percentile":null,"cited_by_percentile_year":null,"biblio":{"volume":null,"issue":null,"first_page":null,"last_page":null},"is_retracted":false,"is_paratext":false,"is_xpac":false,"primary_topic":{"id":"https://openalex.org/T10627","display_name":"Advanced Image and Video Retrieval Techniques","score":0.9171000123023987,"subfield":{"id":"https://openalex.org/subfields/1707","display_name":"Computer Vision and Pattern Recognition"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},"topics":[{"id":"https://openalex.org/T10627","display_name":"Advanced Image and Video Retrieval Techniques","score":0.9171000123023987,"subfield":{"id":"https://openalex.org/subfields/1707","display_name":"Computer Vision and Pattern Recognition"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T11106","display_name":"Data Management and Algorithms","score":0.018200000748038292,"subfield":{"id":"https://openalex.org/subfields/1711","display_name":"Signal Processing"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T10191","display_name":"Robotics and Sensor-Based Localization","score":0.009800000116229057,"subfield":{"id":"https://openalex.org/subfields/2202","display_name":"Aerospace Engineering"},"field":{"id":"https://openalex.org/fields/22","display_name":"Engineering"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}}],"keywords":[{"id":"https://openalex.org/keywords/locality-sensitive-hashing","display_name":"Locality-sensitive hashing","score":0.6707000136375427},{"id":"https://openalex.org/keywords/hyperbolic-geometry","display_name":"Hyperbolic geometry","score":0.636900007724762},{"id":"https://openalex.org/keywords/hash-function","display_name":"Hash function","score":0.5917999744415283},{"id":"https://openalex.org/keywords/hyperplane","display_name":"Hyperplane","score":0.5515999794006348},{"id":"https://openalex.org/keywords/dynamic-perfect-hashing","display_name":"Dynamic perfect hashing","score":0.5486999750137329},{"id":"https://openalex.org/keywords/hyperbolic-space","display_name":"Hyperbolic space","score":0.5394999980926514},{"id":"https://openalex.org/keywords/metric-space","display_name":"Metric space","score":0.43709999322891235},{"id":"https://openalex.org/keywords/dimension","display_name":"Dimension (graph theory)","score":0.41620001196861267},{"id":"https://openalex.org/keywords/hyperbolic-tree","display_name":"Hyperbolic tree","score":0.3880999982357025}],"concepts":[{"id":"https://openalex.org/C33923547","wikidata":"https://www.wikidata.org/wiki/Q395","display_name":"Mathematics","level":0,"score":0.7576000094413757},{"id":"https://openalex.org/C74270461","wikidata":"https://www.wikidata.org/wiki/Q1625299","display_name":"Locality-sensitive hashing","level":4,"score":0.6707000136375427},{"id":"https://openalex.org/C206352148","wikidata":"https://www.wikidata.org/wiki/Q209306","display_name":"Hyperbolic geometry","level":3,"score":0.636900007724762},{"id":"https://openalex.org/C99138194","wikidata":"https://www.wikidata.org/wiki/Q183427","display_name":"Hash function","level":2,"score":0.5917999744415283},{"id":"https://openalex.org/C68693459","wikidata":"https://www.wikidata.org/wiki/Q657586","display_name":"Hyperplane","level":2,"score":0.5515999794006348},{"id":"https://openalex.org/C122907437","wikidata":"https://www.wikidata.org/wiki/Q5318999","display_name":"Dynamic perfect hashing","level":5,"score":0.5486999750137329},{"id":"https://openalex.org/C83677898","wikidata":"https://www.wikidata.org/wiki/Q1878538","display_name":"Hyperbolic space","level":2,"score":0.5394999980926514},{"id":"https://openalex.org/C198043062","wikidata":"https://www.wikidata.org/wiki/Q180953","display_name":"Metric space","level":2,"score":0.43709999322891235},{"id":"https://openalex.org/C114614502","wikidata":"https://www.wikidata.org/wiki/Q76592","display_name":"Combinatorics","level":1,"score":0.4316999912261963},{"id":"https://openalex.org/C33676613","wikidata":"https://www.wikidata.org/wiki/Q13415176","display_name":"Dimension (graph theory)","level":2,"score":0.41620001196861267},{"id":"https://openalex.org/C118615104","wikidata":"https://www.wikidata.org/wiki/Q121416","display_name":"Discrete mathematics","level":1,"score":0.40380001068115234},{"id":"https://openalex.org/C97654310","wikidata":"https://www.wikidata.org/wiki/Q574023","display_name":"Hyperbolic tree","level":4,"score":0.3880999982357025},{"id":"https://openalex.org/C77553402","wikidata":"https://www.wikidata.org/wiki/Q13222579","display_name":"Upper and lower bounds","level":2,"score":0.3788999915122986},{"id":"https://openalex.org/C176217482","wikidata":"https://www.wikidata.org/wiki/Q860554","display_name":"Metric (unit)","level":2,"score":0.37700000405311584},{"id":"https://openalex.org/C187062812","wikidata":"https://www.wikidata.org/wiki/Q6322840","display_name":"K-independent hashing","level":5,"score":0.3635999858379364},{"id":"https://openalex.org/C28719098","wikidata":"https://www.wikidata.org/wiki/Q44946","display_name":"Point (geometry)","level":2,"score":0.3625999987125397},{"id":"https://openalex.org/C2778572836","wikidata":"https://www.wikidata.org/wiki/Q380933","display_name":"Space (punctuation)","level":2,"score":0.34040001034736633},{"id":"https://openalex.org/C14036430","wikidata":"https://www.wikidata.org/wiki/Q3736076","display_name":"Function (biology)","level":2,"score":0.33180001378059387},{"id":"https://openalex.org/C129782007","wikidata":"https://www.wikidata.org/wiki/Q162886","display_name":"Euclidean geometry","level":2,"score":0.33160001039505005},{"id":"https://openalex.org/C67388219","wikidata":"https://www.wikidata.org/wiki/Q207440","display_name":"Hash table","level":3,"score":0.31540000438690186},{"id":"https://openalex.org/C70984080","wikidata":"https://www.wikidata.org/wiki/Q2619102","display_name":"Hyperbolic manifold","level":3,"score":0.29280000925064087},{"id":"https://openalex.org/C186450821","wikidata":"https://www.wikidata.org/wiki/Q17295","display_name":"Euclidean space","level":2,"score":0.2728999853134155},{"id":"https://openalex.org/C82673646","wikidata":"https://www.wikidata.org/wiki/Q2246553","display_name":"Hyperbolic triangle","level":4,"score":0.26170000433921814},{"id":"https://openalex.org/C2779808786","wikidata":"https://www.wikidata.org/wiki/Q6664603","display_name":"Locality","level":2,"score":0.25279998779296875},{"id":"https://openalex.org/C120174047","wikidata":"https://www.wikidata.org/wiki/Q847073","display_name":"Euclidean distance","level":2,"score":0.25270000100135803}],"mesh":[],"locations_count":1,"locations":[{"id":"doi:10.48550/arxiv.2603.19724","is_oa":true,"landing_page_url":"https://doi.org/10.48550/arxiv.2603.19724","pdf_url":null,"source":{"id":"https://openalex.org/S4306400194","display_name":"arXiv (Cornell University)","issn_l":null,"issn":null,"is_oa":true,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I205783295","host_organization_name":"Cornell University","host_organization_lineage":["https://openalex.org/I205783295"],"host_organization_lineage_names":[],"type":"repository"},"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":null,"is_accepted":false,"is_published":null,"raw_source_name":null,"raw_type":"article"}],"best_oa_location":{"id":"doi:10.48550/arxiv.2603.19724","is_oa":true,"landing_page_url":"https://doi.org/10.48550/arxiv.2603.19724","pdf_url":null,"source":{"id":"https://openalex.org/S4306400194","display_name":"arXiv (Cornell University)","issn_l":null,"issn":null,"is_oa":true,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I205783295","host_organization_name":"Cornell University","host_organization_lineage":["https://openalex.org/I205783295"],"host_organization_lineage_names":[],"type":"repository"},"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":null,"is_accepted":false,"is_published":false,"raw_source_name":null,"raw_type":"article"},"sustainable_development_goals":[{"display_name":"Sustainable cities and communities","score":0.422254741191864,"id":"https://metadata.un.org/sdg/11"}],"awards":[],"funders":[],"has_content":{"grobid_xml":false,"pdf":false},"content_urls":null,"referenced_works_count":0,"referenced_works":[],"related_works":[],"abstract_inverted_index":{"For":[0,150,168],"a":[1,6,22,98,104,110,157],"metric":[2],"space":[3,118],"$(X,":[4],"d)$,":[5],"family":[7],"$\\mathcal{H}$":[8],"of":[9,61,205],"locality":[10],"sensitive":[11,20],"hash":[12,45,89],"functions":[13],"is":[14,59],"called":[15],"$(r,":[16,85],"cr,":[17,86],"p_1,":[18,87],"p_2)$":[19],"if":[21,47,107],"randomly":[23],"chosen":[24],"function":[25,90],"$h\\in":[26],"\\mathcal{H}$":[27],"has":[28,74],"probability":[29],"at":[30],"least":[31],"$p_1$":[32],"(at":[33],"most":[34,63],"$p_2$)":[35],"to":[36,147,181,188,209],"map":[37],"any":[38],"$a,":[39],"b\\in":[40],"X$":[41],"in":[42,70],"the":[43,62,142,151,164,184,193,200,210],"same":[44],"bucket":[46],"$d(a,":[48,52],"b)\\leq":[49],"r$":[50],"(or":[51],"b)\\geq":[53],"cr$).":[54],"Locality":[55],"Sensitive":[56],"Hashing":[57],"(LSH)":[58],"one":[60],"popular":[64],"techniques":[65],"for":[66,78,130],"approximate":[67,92],"nearest-neighbor":[68],"search":[69,95],"high-dimensional":[71],"spaces,":[72],"and":[73,81,120,183],"been":[75],"studied":[76],"extensively":[77],"Hamming,":[79],"Euclidean,":[80],"spherical":[82],"geometries.":[83],"An":[84],"p_2)$-sensitive":[88],"enables":[91],"nearest":[93],"neighbor":[94],"(i.e.,":[96],"returning":[97],"point":[99,111],"within":[100,112],"distance":[101,113],"$cr$":[102],"from":[103,115,179],"query":[105,121],"$q$":[106],"there":[108],"exists":[109],"$r$":[114],"$q$)":[116],"with":[117],"$O(n^{1+\u03c1})$":[119],"time":[122],"$O(n^\u03c1)$":[123],"where":[124],"$\u03c1=\\frac{\\log":[125],"1/p_1}{\\log":[126],"1/p_2}$.":[127],"But":[128],"LSH":[129,144,187,207],"hyperbolic":[131,148,152,170,186,211],"spaces":[132,171],"$\\mathbb{H}^d$":[133,180],"remains":[134],"largely":[135],"unexplored.":[136],"In":[137],"this":[138],"work,":[139],"we":[140,155,175,197],"present":[141],"first":[143],"construction":[145,158],"native":[146],"space.":[149],"plane":[153],"$(d=2)$,":[154],"show":[156,198],"achieving":[159],"$\u03c1\\leq":[160,190],"1/c$,":[161],"based":[162],"on":[163,203],"hyperplane":[165],"rounding":[166],"scheme.":[167],"general":[169],"$(d":[172],"\\geq":[173],"3)$,":[174],"use":[176],"dimension":[177],"reduction":[178],"$\\mathbb{H}^2$":[182],"2D":[185],"get":[189],"1.59/c$.":[191],"On":[192],"lower":[194,201],"bound":[195,202],"side,":[196],"that":[199],"$\u03c1$":[204],"Euclidean":[206],"extends":[208],"setting":[212],"via":[213],"local":[214],"isometry,":[215],"therefore":[216],"giving":[217],"$\u03c1\\geq":[218],"1/c^2$.":[219]},"counts_by_year":[],"updated_date":"2026-05-05T08:41:31.759640","created_date":"2026-03-24T00:00:00"}