Ett lokalkänsligt hashsystem är en fördelning på en familj F av hashfunktioner som fungerar på en samling av objekt, så att för två objekt x, y, där sim(x, y) [0, 1] är någon likhetsfunktion definieras på samlingen av objekt. Ett sådant system leder till en kompakt representation av objekt så att likhet av objekt kan uppskattas från sina kompakta skisser, och också leder till effektiva algoritmer för ungefärlig närmaste grannsökning och kluster. Min-wise oberoende permutationer ger en elegant konstruktion av en sådan lokalitet känslig hashing system för en samling av undergrupper med den inställda likheten åtgärd sim(A, B) =  på A och B. Vi visar att avrundningsalgoritmer för LP och SDP som används i samband med approximationsalgoritmer kan ses som lokalkänsliga hashsystem för flera intressanta samlingar av objekt. Baserat på denna insikt skapar vi nya lokalkänsliga hashsystem för: 1. En samling vektorer med avståndet mellan u och v mätt med  till ( u, v)/π, där  på ( u, v) är vinkeln mellan u och v. Detta ger ett skissschema för att uppskatta cosinuslikviditetsmåttet mellan två vektorer, samt ett enkelt alternativ till minvisa oberoende permutationer för att uppskatta uppsättningen likhet. 2. Utgångspunkten är följande: En samling fördelningar på n-punkter i ett metriska utrymme, med avstånd mellan fördelningar uppmätta med Earth Mover Distance (EMD), (ett populärt avståndsmått i grafik och vision). Våra hashfunktioner kartfördelningar till punkter i det metriska utrymmet så att, för distributioner P och Q, ≤ O(log n log log n) · EMD(P, Q).
REF tillämpade en omvandling till f och g så att avståndet mellan dem begränsas av W 1 (f, g) och över av O(log n log n)W 1 (f, g).
Similarity estimation techniques from rounding algorithms
{'venue': "STOC '02", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}