Vi visar förekomsten av en Locality-Sensitive Hashing (LSH) familj för vinkelavstånd som ger en ungefärlig nära granne Sök algoritm med asymptotiskt optimal körtid exponenten. Till skillnad från tidigare algoritmer med denna egenskap (t.ex. sfärisk LSH [1, 2]) är vår algoritm också praktisk och förbättrar i praktiken det välstuderade hyperplanet LSH [3]. Vi introducerar också en multiprobeversion av denna algoritm och genomför experimentell utvärdering av verkliga och syntetiska datamängder. Vi kompletterar ovanstående positiva resultat med en finkornig lägre gräns för kvaliteten på alla LSH-familjer för vinkelavstånd. Vår nedre gräns innebär att ovanstående LSH-familj uppvisar en kompromiss mellan utvärderingstid och kvalitet som är nära optimal för en naturlig klass av LSH-funktioner.
En ny LSH familj för vinkelavstånd på enheten sfär motiverade utvecklingen av FALCONN biblioteket REF.
Practical and Optimal LSH for Angular Distance
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}