Alla par likhetssökning är ett problem där en uppsättning dataobjekt ges och uppgiften är att hitta alla par av objekt som har likhet över en viss tröskel för en given likhet mått-av-intresse. När antalet punkter eller dimensionalitet är högt, standard lösningar misslyckas med att skala graciöst. Ungefärliga lösningar som Locality Sensitive Hashing (LSH) och dess Bayesian varianter (BayesLSH och BayesLSHLite) lindrar problemet i viss utsträckning och ger en betydande upptrappning jämfört med traditionella indexbaserade metoder. BayesLSH används för beskärning av kandidatutrymmet och beräkning av ungefärlig likhet, medan BayesLSHLite bara kan beskära kandidaterna, men likhet måste beräknas exakt på de ursprungliga uppgifterna. Där det alltid finns en explicit uppgiftsrepresentation och exakt likhetsberäkning inte är för dyr, kan BayesLSH-Lite användas för att aggressivt beskära kandidater och ge betydande snabbhet utan att förlora för mycket på kvalitet. Förlusten av kvalitet är dock högre i BayesLSH-varianten, där explicit uppgiftsrepresentation inte finns tillgänglig, snarare är det bara en hashskiss som finns tillgänglig och likheten måste uppskattas ungefär. I detta arbete ser vi över LSH-problemet från en Frequentist inställning och formulera sekventiella tester för sammansatta hypoteser (likhet större än eller mindre än tröskelvärdet) som kan utnyttjas av sådana LSH algoritmer för adaptivt beskärning kandidater aggressivt. Vi föreslår en vanilj sekventiell sannolikhetskvot test (SPRT) metod baserad på denna idé och två nya varianter. Vi utvidgar dessa varianter till fallet där ungefärlig likhet måste beräknas med hjälp av fast bredd sekventiell konfidensintervall generering teknik. Vi jämför dessa nya varianter med SPRT varianten och BayesLSH / Bayes-LSHLite varianter och visar att de kan ge hårdare kvalitativa garantier över BayesLSH / BayesLSHLite - en toppmodern metod - samtidigt som upp till 2,1x snabbare än en traditionell SPRT och 8,8x snabbare än AllPairs.
Chakrabarti m.fl. REF antog stegvisa hypotestester på LSH på adaptivt beskärda kandidater aggressivt och ger strängare kvalitativa garantier jämfört med BayesLSH.
Sequential Hypothesis Tests for Adaptive Locality Sensitive Hashing
{'venue': "WWW '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}