Vi studerar lägre gränser för lokal sensitiv hashing (LSH) i den starkaste inställningen: punktuppsättningar i {0,1} d under hammingavståndet. Kom ihåg att H sägs vara en (r, cr, p, q)-känslig hash familj om alla par x, y  till {0, 1} d med dist(x, y) ≤ r har sannolikhet åtminstone p kollision under en slumpmässigt vald h  på H, medan alla par x, y 0, 1} d med dist(x, y) ≥ cr har sannolikhet som mest q kollision. Vanligtvis anser man d → ∞, med c > 1 fast och q avgränsad från 0. För dess tillämpningar till ungefärlig närmaste granne sökning i höga dimensioner, är kvaliteten på en LSH familj H styrs av hur liten dess ρ parameter ρ = ln(1/p) / ln(1/q) är som en funktion av parametern c. Den seminal papper av Indyk och Motwani [1998] visade att för varje c ≥ 1, den extremt enkla familjen H = {x → x i : i [d]} uppnår ρ ≤ 1/c. Den enda kända nedre gränsen, på grund av Motwani et al. [2007], är att ρ måste vara minst (e 1/c − 1)/(e 1/c + 1) ≥.46/c (minus o d (1) ). Bidraget till den här artikeln är tvåfaldigt. (1) Vi visar den "optimala" nedre gränsen för ρ: det måste vara minst 1/c (minus o d (1) ). Vårt bevis är mycket enkelt, efter nästan omedelbart från observationen att bullerstabiliteten hos en booleansk funktion vid tidpunkten t är en log-convex funktion av t. (2) Vi höjer och diskuterar följande fråga: varken tillämpningen av LSH till närmaste granne sökning eller den kända LSH nedre gränser hålla som anges om q parametern är liten. Här betyder "tiny" q = 2 − (d), ett parameterintervall vi tror är naturligt.
O'Donnell, Wu och Zhou REF drog åt konstanterna i exponenten av LSH nedre gränsen.
Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
{'venue': 'TOCT', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}