Detta papper tar upp problemet med att hitta närmaste granne (eller en av R-nearest grannar) av ett frågeobjekt q i en databas med n objekt. I motsats till de flesta befintliga metoder, kan vi bara komma åt det "dolda" utrymme där objekten lever genom en likhet orakel. Oraklet, givet två referensobjekt och ett frågeobjekt, returnerar referensobjektet närmast frågeobjektet. Orakeln försöker att modellera beteendet hos mänskliga användare, kapabla att göra uttalanden om likhet, men inte att tilldela meningsfulla numeriska värden till avstånd mellan objekt. Med hjälp av en sådan orakel, det bästa vi kan hoppas på är att få, för varje objekt u i databasen, en sorterad lista över de andra objekten enligt deras avstånd till u. Vi kallar position objekt v i denna lista rang v med avseende på u. Svårigheten att söka med hjälp av ett sådant orakel beror på de icke-homogeniteter i det underliggande utrymmet. Vi använder två olika karakteriseringar av det underliggande utrymmet för att fånga denna egenskap. Den första, rank förvrängning, relaterar parvis leden till den genomsnittliga skillnaden i leden w.r.t. Andra föremål (en mer exakt definition ges i avsnitt II). I det andra, kombinatoriska ramverket (ett begrepp från [1], [2]), definieras ungefärliga triangelskillnader i leden (en mer exakt definition ges i avsnitt II). Ungefärligt, definierar den en multiplikativ faktor D genom vilken triangeln ojämlikhet på leden kan kränkas. Med hjälp av insikterna från dessa idéer utvecklar vi en hierarkisk sökalgoritm som bygger en datastruktur, vilket gör att vi kan hämta närmaste granne med hög sannolikhet i O(D 3 log 2 n log n D 3 ) frågor. Lärandet kräver att man frågar O(nD 3 log 2 n log n D 3 ) frågor totalt och vi behöver lagra O(n log 2 n/ log(2D) bitar totalt. Vi tillhandahåller också en ungefärlig närmaste grannsökningsalgoritm. Slutligen visar vi en lägre gräns för  och (D log n D 2 + D 2 ) genomsnittligt antal frågor i sökfasen för randomiserade algoritmer när svaren på alla möjliga frågor i inlärningsfasen ges. Vi introducerar också rankkänsliga hashfunktioner som ger samma hashvärde för "liknande" objekt baserat på rankvärdet av objekten som erhålls från likheten oraklet. Som en tillämpning av RSH, visar vi att vi kan hämta en av (1 +  på) r-nearest granne av en frågepunkt i n  på utvärderingar av hash-funktionen, där  till bara beror på  till och rank distorsion.
I REF visar vi en lägre gräns som visar att våra system är (nästan) effektiva.
Approximate Nearest Neighbor Search through Comparisons
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}