Vi tar ett första steg mot en rigorös asymptotisk analys av grafbaserade metoder för att hitta (ungefär) närmaste grannar i högdimensionella utrymmen, genom att analysera komplexiteten i (randomized) giriga promenader på ungefärlig nära granne grafen. För slumpmässiga datamängder av storlek n = 2 o(d) på den d-dimensionella Euclidean enhetssfären, med hjälp av nära granngrafer kan vi på ett påvisbart sätt lösa det ungefärliga närmaste grannproblemet med approximationsfaktor c > 1 i frågetid n ρq+o(1) och utrymme n 1+ρs+o(1), för godtyckliga ρ q, ρ s ≥ 0 tillfredsställande Graph-baserad nära granne sökning är särskilt konkurrenskraftig med hash-baserade metoder för små c och nära-linjära minne, och i denna regim den asymptotiska skalningen av en girig graf-baserad sökning matchar den senaste optimala hash-baserade kompromisser av Andoni-Laarhoven-RazenshteynWaingarten [6]. Vi studerar vidare hur avvägningsskalan när datamängden är av storlek n = 2 (d), och analyserar asymptotiska komplexiteter vid tillämpning av dessa resultat till lattice sikting. Nyckelord och fraser (ungefär) närmaste granne problem, nära granne grafer, localitykänslig hashing, locality känsliga filter, likhetssökning Digital Object Identifier 10.4230/LIPICs.TBD.2018.1 Närmaste grannsökning. Ett viktigt datorproblem inom olika forskningsområden, såsom maskininlärning, mönsterigenkänning, datakompression och avkodning [17, 27, 28, 41, 34, 49], är närmaste granne problem: med tanke på en d-dimensionell datauppsättning D  på kardinalitet n, utforma en datastruktur och preprocess D på ett effektivt sätt så att, när senare en frågevektor q  på R d, kan vi snabbt hitta närmaste punkt till q i D (t.ex. för Euclidean metrisken). Eftersom den exakta (sämsta-fallet) versionen av detta problem lider av "förbannelsen av dimensionalitet" [31], en gemensam avkoppling av detta problem är den ungefärliga närmaste granne (ANN) problem: med tanke på att den exakta närmaste granne i datauppsättningen D ligger på avstånd som mest r från q, designa en effektiv algoritm som finner ett element p  på avstånd som mest c · r från q, för en given approximationsfaktor c > 1. Vi kommer att hänvisa till detta problem som (c, r)-ANN. Eftersom en naiv linjär sökning trivialt leder till en O(d · n) tidsalgoritm för att lösa både de exakta och ungefärliga problemen nära grannen, är målet att utforma en datastruktur för vilken frågor kan besvaras korrekt i tid n ρ+o(1) med ρ < 1. Här kommer vi bara att överväga scenarier där d skalor med n-for fast d, det är välkänt att man kan uppnå godtyckligt små frågeexponenter ρ = o(1) [9]. Vi antar vidare w.l.o.g. att n ≥ 2 O( d/ log d) - om d är större, kan vi först utföra en slumpmässig projektion för att minska datamängdens effektiva dimensionalitet, samtidigt som mellanpunktsavstånd bibehålls [32]. [31, 24, 3, 5]. Med hjälp av hashfunktioner med egenskapen att närliggande vektorer är mer benägna att kartläggas till samma hash värde, bygger man flera hash tabeller med hinkar som innehåller vektorer med samma hash värde. Frågar sedan q bearbetas av computing h(q), slå upp vektorer p  på D med samma hash värde h(p) = h(q), och med tanke på dessa vektorer som kandidat nära grannar, för var och en av de förhandsberäknade hash tabeller. Även om ett stort antal randomiserade haschtabeller ofta krävs för att få en bra återkallningsfrekvens, gör dessa uppslag i alla hashtabeller är ofta fortfarande betydligt snabbare än en linjär sökning genom listan. Medan LSH kräver att varje punkt ska kartläggas till exakt en hash hink i varje hash tabell, den senaste lokalitetskänslig filtrering (LSF) [13, 6, 22] slappnar av detta villkor: för varje hash filter och varje punkt i datamängden, bestämmer vi självständigt om vi lägger till denna punkt till denna filter hink eller inte. Detta kan innebära att vissa punkter läggs till fler filter än andra, och filter inte nödvändigtvis bildar en partitionering av utrymmet. Frågor besvaras genom att överväga filter som matchar frågan, och gå igenom alla vektorer i dessa hinkar. För det speciella fallet med det ungefärliga närmaste grannproblemet där datamängden ligger på sfären, är många effektiva partitionsbaserade metoder kända baserat på att använda slumpmässiga hyperplan [20], regelbundna polytoper [50, 4, 33, 37], och sfäriska kapsyler [3, 5, 13, 35, 6]. För slumpmässiga datamängder av storlek n = 2 o(d), både korspolytop LSH [4] och sfärisk LSF [13] uppnå optimal asymptotisk skalning av frågekomplexiteten för hashbaserade metoder. Spherical LSF erbjuder ytterligare optimala tids-rymd-avsättningar mellan fråge- och uppdaterings- och rymdkomplex [6], medan cross-polytope LSH verkar prestera bättre i praktiken [4, 48, 10]. Inga optimala resultat är kända för datauppsättningar av storlek n = 2 (d), men sfäriska LSF överträffar på ett tillfredsställande sätt cross-polytope LSH i vissa regimer [13]. Ett annat sätt att närma sig det närbelägna problemet inbegriper att bygga närmaste granngrafer, där hörnen motsvarar punkter p  och D i datamängden, och en kant mellan två hörn visar att dessa punkter är ungefärliga nära grannarna [19, 29, 43, 46, 21, 23, 26, 30, 51]. Eftersom en fråga q, man börjar vid en godtycklig nod p  på D, och upprepade gånger försök att hitta hörn p, ansluten till p i grafen genom en kant, som är närmare q än den nuvarande kandidaten nära granne p. När denna process avslutas, den resulterande vektorn är antingen en lokal eller ett globalt minimum, dvs.. en falsk positiv eller den sanna närmaste granne till q. Om grafen är tillräckligt väl ansluten, kan vi hoppas att lösa (A)NN problem med hög sannolikhet i en iteration - annars kan vi börja om med en ny slumpmässig p  på D, och hoppas på framgång i ett rimligt antal försök. Jämfört med LSH och LSF, som ofta kräver lagring ganska några extra data som beskriver hash tabeller / filter, och för vilka kostnaden för att datorhasch eller hitta lämpliga filter är vanligtvis icke-försumbar, närmaste granne graf metod har mycket mindre overhead: för varje vektor p  på D, behöver man bara lagra sina närmaste grannar i en lista, och uppslag kräver inga ytterligare beräkningar förutom jämförelser mellan frågan q och datapunkter p  på D i dessa listor för att hitta närmare grannar. I praktiken kan grafbaserade metoder därför vara effektivare än hashbaserade metoder, även om asymptotiska analyser tyder på annat, enbart på grund av de låga omkostnaderna för grafbaserade metoder. Förutom den vanliga närmaste granne grafen metoden att ansluta varje vertex till sina närmaste grannar [26, 25], är olika heuristiska graf-baserade metoder ytterligare kända baserat på att lägga anslutningar i grafen mellan punkter som inte är necessaily nära grannar [47, 40, 18]. Detta kan till exempel inbegripa flera långa, djupa länkar i grafen mellan avlägsna punkter, för att garantera att varje par av noder är ansluten Thijs Laarhoven 1:3 genom en kort väg [40]. Med hjälp av hierarkiska grafer [39, 18] där hörn är partitionerade i flera lager ytterligare verkar underlätta prestanda av graf-baserade metoder, även om dessa förbättringar verkar vara rent heuristiska. Jämförelse av olika metoder. För att ta reda på vilken metod för att hitta närmaste grannar i högdimensionella utrymmen är objektivt bäst, ett självklart tillvägagångssätt skulle vara att genomföra dessa metoder, testa dem mot realistiska datamängder, och jämföra deras konkreta prestanda. Olika bibliotek med implementationer av närliggande metoder är öppet tillgängliga online [16, 48, 44, 25, 18], och nyligen Aumüller-Bernhardsson-Faithfull presenterade en grundlig jämförelse av olika metoder för närmaste granne sökning på olika allmänt använda datamängder och avståndsmått [15, 10]. De slutliga slutsatserna är bland annat att LSH-baserade FALCONN och grafbaserade NMSLib och KGraph för närvarande verkar vara de mest konkurrenskraftiga metoderna för sina bedömda datamängder. Praktiska jämförelser har helt klart olika nackdelar, eftersom den praktiska prestandan ofta beror på många ytterligare variabler, såsom specifika egenskaper hos datamängden och graden av optimering av genomförandet - bättre resultat på vissa datamängder kan inte alltid översättas väl till andra datamängder med ytterligare optimerade implementationer. Dessutom kan vissa metoder skala bättre som dimensionalitet och storlek av datamängden ökar, och det är svårt att exakt förutsäga asymptotiskt beteende från praktiska experiment. En andra metod för att jämföra olika metoder skulle vara att titta på deras teoretiska, beprövade asymptotiska prestanda som storleken på datamängden n och dimension d tenderar till oändlighet. Täta gränser på prestanda skulle göra det möjligt för oss att extrapolera till godtyckliga datauppsättningar, men för många algoritmer som får så snäva asymptotiska gränser verkar utmanande. Även om för partition-baserade metoder, vid det här laget den asymptotiska prestandan verkar vara någorlunda väl förstådd, graf-baserade algoritmer är mestadels baserade på obevisade heuristik, och är inte lika väl förstådd teoretiskt. Detta är särskilt oroande på grund av effektiviteten i vissa grafbaserade tillvägagångssätt, och därför är en naturlig fråga: hur väl håller grafbaserade tillvägagångssätt upp mot partitionsbaserade metoder i höga dimensioner? Är det bara de låga overhead av graf-baserade metoder som gör det möjligt för dem att konkurrera med hash-baserade metoder? Eller kommer dessa grafbaserade metoder att förbli konkurrenskraftiga även för enorma datamängder? Heuristiska metoder är teoretiska. Vi påpekar vidare att tidigare har teoretiska analyser av heuristiska metoder nära grannen inte bara bidragit till en bättre förståelse av dessa metoder, utan också till att göra dessa metoder mer praktiska. Korspolytop LSH, som används i FALCONN [48], föreslogs ursprungligen som en snabb heuristisk metod utan bevisade asymptotiska garantier [50]. Först senare upptäcktes att denna metod är teoretiskt överlägsen även andra metoder [4, 33], och kan göras ännu mer praktisk. Nyligen erhölls även för hyperkub LSH [50] förbättrade teoretiska garantier [37], och den heuristiska LSH-skogsmetoden [12] gjordes också "teoretisk" med bevisbara prestandagarantier i höga dimensioner [8]. Målen för en teoretisk analys av grafbaserade metoder är därför tvåfaldiga: att förstå deras asymptotiska prestanda bättre, och att hitta sätt att ytterligare förbättra dessa metoder i praktiken. Vi tar ett första steg mot en bättre teoretisk förståelse av grafbaserade tillvägagångssätt för (ungefär) närmaste granne problem, genom att noggrant analysera den asymmetriska prestandan hos den grundläggande giriga närmaste granne grafen tillvägagångssätt. Vi visar att för slumpmässiga datamängder på Euclidean enhet sfären och för godtycklig approximation faktorer c > 1, detta diagram-baserade tidsrymd kompromisser för ungefärliga nära grannar metod bevisligen uppnår asymptotiska frågeexponenter ρ < 1. Vi visar vidare hur man får effektiva tids-rymd kompromisser, genom att göra relaterade nära granne graf antingen mer ansluten (mer utrymme, bättre frågetid) eller mindre ansluten (mindre utrymme, sämre frågetid). Sparse datauppsättningar. I det fall data som på enheten sfär 1 har storlek n = 2 o(d), och en ovanligt nära granne ligger på avstånd r = 2/c, de kompromisser vi får för att hitta en sådan nära vektor till en slumpmässig frågevektor styrs av följande förhållande. Teorem 1 (tid-rymd-avsättningar för glesa data). För c > 1 och ρ q, ρ s ≥ 0 som uppfyller det finns en grafbaserad (c, r)-ANN datastruktur för datamängder av storlek n = 2 o(d) på sfären med utrymme n 1+ρs+o(1) och frågetid n ρq+o(1). Minimera frågekomplexiteten i denna asymptotiska analys motsvarar inställningen ρ s = 1 2, i vilket fall ρ q = c 2 / (2c 2 − 1). Observera att, till skillnad från i olika hash-baserade konstruktioner, det finns en naturlig gräns för maximal utrymme komplexitet graf-baserade metoder: vi kan inte lagra mer än n grannar per vertex. Vår analys dock tyder på att när man gör en girig sökning i grafen, lagring mer än ε n grannar per vertex inte ytterligare förbättra frågan komplexitet, jämfört med att börja om på en slumpmässig ny vertex. För att jämföra ovanstående avvägningar med hash-baserade resultat, kom ihåg att i [6] fick författarna hash-baserade tidsrymd kompromisser definieras av följande ojämlikhet: Även om i de flesta fall den optimala 2 hash-baserade kompromisser från (3) är strikt överlägsen den graf-baserade kompromisser från Theorem (1), Vi noterar att i systemet med små approximationsfaktorer c  på 1 och nära-linjära utrymme ρ s  och 0, d.v.s. när det inte finns någon ovanligt nära granne och vi vill bara använda något mer utrymme än vad som krävs för att lagra inmatningslistan, båda ojämlikheter ovan översätta till: Här o(1) försvinner som ρs → 0 och c → 1. Så för verkligt slumpmässiga fall utan någon planterad, ovanligt nära grannar, och när man använder en begränsad mängd minne, grafbaserade metoder är asymptotiskt lika kraftfull för att hitta (ungefär) närmaste grannar som optimala hash-baserade metoder. Med andra ord kommer grafbaserade metoder i detta system att förbli konkurrenskraftiga med hashbaserade metoder även när datamängderna blir mycket stora och dimensionaliteten ytterligare ökar. På den negativa sidan, vår analys tyder på att när det finns en ovanligt nära (planterad) granne till frågan, eller när vi kan använda mycket mer utrymme än den mängd som krävs för att lagra datamängden, de mest kända hash-baserade metoder är överlägsen den grundläggande graf-baserade metod som analyseras i detta papper. Detta kan orsakas antingen av att vår analys inte är tight, den ansedda algoritmen inte är så optimerad, eller på grund av grafbaserad 1 Observera att det nära granne problem på Euclidean enhet sfären är av särskilt intresse på grund av minskningen från nära granne problem i alla R d (under 2-normen) att lösa det sfäriska fallet [7]. Dessutom, med hjälp av standard reduceringar resultaten för 2-normen översätta till resultat för R d med 1-normen också. 2 Inom en viss undersökningsmodell visade sig de hashbaserade kompromisserna från (3) vara optimala i [6]. närmar sig helt enkelt att inte kunna dra lika stor nytta av sådana ovanliga omständigheter. Observera återigen att hashbaserade metoder effektivt kan använda mycket stora mängder utrymme, med ett stort antal finkorniga hash tabeller / partitioner, medan grafbaserade metoder verkar begränsas genom att använda som mest n 2 utrymme. Vi antar därför att den sämre asymptotiska prestandan för "onormala" problemfall är inneboende i grafbaserade metoder. Täta datamängder. För inställningar där datamängden består av n = 2 (d) punkter som dras jämnt på måfå från enhetssfären, beror den asymptotiska prestandan hos nästan grannsökningen inte bara på avståndet till den (planterade) närmaste grannen, utan också på densiteten hos datasetet, d.v.s. Den exakta relationen mellan d och n Motiverad av konkreta datamängder som vanligen används i praktiken, analyserar vi konkret fallet (log n)/d  på 1/5 och visar att de resulterande kompromisserna för exakt närmaste granne problem utan planterade grannar är betydligt bättre än hyperplan LSH [20], jämförbar med eller bättre än cross-polytope LSH [4, 48] och sfärisk cap LSH [5]; men något värre än sfärisk LSF [13, 6]. Den överlägsna asymptotiska prestandan jämfört med FALCONN för realistiska täta datauppsättningar tyder på att grafbaserade tillvägagångssätt kan förbli konkurrenskraftiga med de mest praktiska hashbaserade tillvägagångssätten, även när dimensionaliteten ytterligare ökar. Olika öppna problem återstår att få en bättre teoretisk (och praktisk) förståelse av olika närliggande tekniker, särskilt relaterade till grafbaserade metoder. Vi anger några återstående öppna problem nedan: Även om vår analys för "små steg" (se bilaga A) är tight, vi antog att efteråt vi antingen omedelbart hitta den planterade närmaste granne som en av grannarna i grafen, eller vi misslyckas och börja om från en ny slumpmässig nod. Detta verkar ganska pessimistiskt, och kanske kan komplexiteten förbättras ytterligare med en stramare analys, utan att ändra den underliggande algoritmen eller grafkonstruktionen. Andra heuristiska närmaste granne graf tillvägagångssätt verkar prestera ännu bättre i praktiken, och ett öppet problem är att noggrant analysera dem och se om de översätter till förbättrad asymptotik också. En praktisk nackdel med att använda närmaste granne grafer är att uppdatera datastrukturen (i synnerhet: infoga nya datapunkter) kan vara ganska kostsamt, särskilt i jämförelse med hash-baserade konstruktioner. För att göra datastrukturen både effektiv och dynamisk, skulle man helst också få bättre gränser för införandet komplexitet. I hashbaserad litteratur har fallet med glesa datamängder utan tvekan nästan "lösts" med övre gränser som matchar nedre gränser (inom en viss modell). Är det möjligt att hitta liknande nedre gränser för graf-baserade nära grannsökning? Hashbaserade och grafbaserade tillvägagångssätt skulle kunna betraktas som kompletterande lösningar på samma problem, eftersom de värsta problemfallen för den ena metoden är de bästa fallfallen för den andra. Kan båda teknikerna kombineras, så att kanske ännu bättre värsta-fall-garantier kan erhållas för högdimensionella datamängder? Utgångspunkt. Resten av detta dokument är organiserat enligt följande. I avsnitt 2 presenterar vi preliminära resultat och notation. I avsnitt 3 beskrivs de problem som behandlas i detta dokument. Avsnitt 4 analyserar komplexiteten i att hitta nära grannar med en girig graf sökning, och Avsnitt 5 och 6 anser asymptotik för glesa och täta datamängder, respektive. Bilagorna innehåller bevis och diskuterar ansökan om lattice sikting. Diagram-baserade tid-rymd kompromisser för ungefärligt nära grannar 2 Preliminärer Låt · betecknar Euclidean norm, och låt ·, · betecknar standard prick produkten. Vi skriver för Euclidean unit sfär i R d. Vi skriver X  och χ(X ) för att beteckna att den slumpmässiga variabeln X provtas från sannolikhetsfördelningen χ över den inställda X, och vi skriver U(X ) för den enhetliga fördelningen över X. Med tanke på en vektor x (skriven i fetstil), skriver vi vidare x i = x, e i för ith koordinat av x. Vi betecknar riktade grafer med G = (V, A) där V betecknar uppsättningen hörn, och A V × V betecknar uppsättningen riktade bågar. En riktad graf kallas symmetrisk om symmetriska riktade grafer också kan ses som oriktade grafer G = (V, E) där kanterna är oordnade undergrupper av V i storlek 2. Låt C x,α = {u  till S d-1 : u, x ≥ α} betecknar det sfäriska locket centrerat på x  på S d-1 av "höjd" α  och låt C(α) beteckna dess volym i förhållande till hela enheten sfären. Låt W x,α,y,β = C x,α  på C y,β med x, y  på S d-1 och α, β på 0, 1) betecknar skärningspunkten mellan två sfäriska kapsyler, och låt dess volym i förhållande till volymen av enheten sfär betecknas W (α, β, γ), där γ = x, y är cosinus för vinkeln mellan x och y. Vi kommer också att kalla de senare föremålen kilar. Volymerna av dessa objekt motsvarar sannolikheterna på sfären enligt följande: De asymptotiska relativa volymerna av sfäriska kapsyler och kilar kan uppskattas enligt följande, såsom tidigare visats i t.ex. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Lemma 2 (Volym av en sfärisk mössa). Låt oss α  på (0, 1). Därefter: Lemma 3 (Volym av en kil). Låt α-, β-, γ-(0,1). Därefter: För kilen kan volymen alternativt beskrivas (upp till polynomiska faktorer i d) som volymen av ett sfäriskt lock med höjd δ = α 2 +β 2 −2αβγ 1−γ 2. I figur 1 motsvarar detta det minsta avståndet från punkter i W x,α,y,β till ursprunget, dvs. avståndet från skärningspunkten mellan de blå och röda linjerna i denna projektion av sfären till ursprunget. Om γ ≥ α β med α ≤ β, blir detta avstånd från ursprunget δ = β och i så fall har man i huvudsak C x,α  på C y,β C y,β. Vi kommer att använda olika egenskaper hos dessa kilar, och vi anger några av dem nedan. För α-, β-, γ-, (0, 1)- och γ- < min-bevis. För 1. resultatet följer genom att ta derivat w.r.t. α, β, γ i den "asymptotiska delen" av W (dvs. Ignorera termen d.(1) och observera att dessa derivat alltid är negativa, negativa respektive positiva. För 2. vi tar derivatan w.r.t. β av W (α, β, β) och observera att detta derivat alltid är negativt. Följande lemma beskriver vidare att om vi lägger till en liten mängd "slack" till en av variablerna, då volymen av den resulterande kilen kommer fortfarande att vara mycket lik volymen av kilen med de ursprungliga parametrarna - om slack är liten, då förlorar vi bara som mest en polynom faktor i volymen. Bevis. Detta följer av att skriva ut de vänstra sidorna, dra ut faktorerna W (α, β, γ), och notera att den återstående faktorn (1 ± ε d ) d för vissa uttryck ε d är som mest polynomial i d, på grund av villkoren på γ och α, β, γ är konstant i d. För graf-baserat tillvägagångssätt i detta papper, där punkter är anslutna till sin närmaste granne och vi utför en promenad på denna graf från en slumpmässig nod, är det omöjligt att lösa värsta fall av (ungefärlig) närmaste grannsökning. Förslag 6 (Värsta fallets datamängder). För nära granne graf närmar sig, där (i) varje vertex är endast ansluten till ett antal av dess närmaste grannar, och (ii) frågor besvaras genom att utföra en girig sökning på denna graf för att få bättre uppskattningar, är det omöjligt att lösa värsta fall (ungefärlig) nära grann fall i sublinjär tid. Diagrambaserade tid-rymd-avsättningar för ungefärliga nära grannar Bevis. Som ett potentiellt värsta fall problem exempel på en sådan strategi, överväga en fråga q. e 1, en planterad närmaste granne p *. e 1 nära till frågan, och låt alla andra punkter p  på D \ {p * } tillfredsställa p  på −e 1. Sedan den förbehandlade nära granne grafen kommer att bestå av en stor ansluten komponent som innehåller punkterna D \ {p * }, och en isolerad vertex p *, som kan ha utgående kanter, men har inga ömsesidiga vänner. Med sannolikhet 1 - 1/n, börjar vid en slumpmässig vertex och utför en promenad på denna (riktad) graf kommer därför inte att ge den sanna närmaste granne p *, medan alla andra hörn är endast ungefärliga lösningar med mycket höga approximativa faktorer; genom att i huvudsak inställning p * = q, kan vi garantera att inte ens någon rimlig ungefärlig lösning kommer att hittas. Även om det kan vara möjligt att justera algoritmen och/eller den underliggande grafen så att även sådana värsta fall fortfarande kan lösas effektivt, kommer vi därför att fokusera på genomsnittliga fall, slumpmässiga fall definieras nedan. Genom hela, Vi kommer att anta att punkter p D är oberoende och jämnt fördelade på enheten sfären, utom (potentiellt) en planterad närmaste granne p *  på D som ligger mycket nära frågevektorn q. Alternativt kan detta tolkas som att ta en enhetligt slumpmässig p * U(D), och välja frågevektorn som q = p * + e för en kort felvektor e. Med tanke på ett sådant problem instans, vi vill återställa p * med icke-försumbar sannolikhet. Observera att det näraliggande problemet på den euklideiska enhetssfären, som anses här, är av särskilt intresse som en sådan lösning tillåter en till den euklideiska nära granne problem i alla R d med hjälp av tekniker av Andoni-Razenshteyn [7]. Dessutom är det välkänt att med hjälp av standard reduceringar, resultaten för 2 - normen översätta till resultat för R d med 1 - normen också. Effektiva algoritmer för enheten sfären därför översätta till lösningar för många andra problem också. För q  på U (D), och datauppsättningar efter en jämnt slumpmässig fördelning, med överväldigande sannolikhet den (icke-planterade) näst närmaste granne p  och D \ {p * } till q har inre produkt p, q = μ (1 + o(1)) och ligger på avstånd q − p = 2.1 − μ) (1 + o(1)) från q, med μ uppfyller: Det naturliga scenariot att överväga för slumpmässiga ANN fall är då att låta c · r = μ, så att den enda planterade närmaste granne ligger på avstånd r = μ / c från målet, och så att detta planterade nära grannen ligger en faktor c närmare q än alla andra punkter i datamängden. Dessa problemfall undersöktes också i t.ex. [4, 6]. Sparse datauppsättningar. Vi kommer att hänvisa till datamängder av storlek n = 2 o(d) (med andra ord: d =  på (log n)) som glesa datamängder. För dessa fall, den förväntade (icke-planterade) närmaste granne avståndet är μ = ε 2 + o(1) och den planterade närmaste granne som vi vill återhämta sig därför ligger på avstånd r = ε 2/c (1 + o(1)) från målet. Observera att fallet n = 2 o(d/ log d) alltid kan reduceras till n = 2  till (d/ log d) genom en slumpmässig projektion på ett mindre dimensionerat utrymme, vilket ungefär bibehåller alla parvisa avstånd mellan punkter i datamängden [32]. Täta datamängder. Vi kommer att hänvisa till datamängder av storlek n = 2  på (d) (d =  på (log n)) som täta datamängder. I detta fall, med överväldigande sannolikhet närmaste granne till en slumpmässigt vald frågepunkt q på sfären kommer att ligga på avstånd c · r = μ < ε 2 från q, och för (c, r)-ANN den planterade närmaste granne skulle därför ligga på avstånd r = μ/c. För det begränsande fallet av c → 1, vill vi återställa en vektor på avstånd μ. Observera att "dimensionalitetens förbannelse" [31] inte nödvändigtvis gäller för genomsnittliga täta datamängder - att hitta exakt närmaste grannar för slumpmässiga täta datamängder kan ofta göras i sublinjär tid [35, 13]. Graph-based neargrann search Närmaste granne graf och motsvarande nära granne söka algoritm vi kommer att analysera är mycket lik en girig sökning i k-nearest granne graf, dvs... mycket lik KGraphs infallsvinkel. Kom ihåg att den riktade k-nearest granne grafen G = (V, A) har vertex ställa V = D, och en båge går från p till p iff p tillhör k närmaste punkter till p i D. Med tanke på en fråga q, söker efter en närmaste vektor i denna graf görs vanligen som beskrivs i Algoritm 1, med ε = 0, och med B (p) ange uppsättningen grannar att p i denna graf. Observera att för stora k = n  med 1) är denna graf nästan symmetrisk. Tillståndet av att tillhöra k närmaste grannar är dock något opraktiskt att arbeta med analytiskt, och så vi kommer att använda följande något annorlunda graf (och söka algoritm) istället. Definition 7 (det α-nära granndiagrammet). Låt α 0, 1), och låt D  till S d-1. Vi definierar den α-nära granngrafen som den oriktade grafen G = (V, E) med vertex-uppsättningen V = D, och med en kant mellan p, p och E om och endast om p, p ≥ α. Parametern α motsvarar ungefär (en funktion av) k: stor α motsvarar små k, och små α till stora k. Asymmetriskt kan det ungefärliga förhållandet mellan k och α anges genom följande enkla samband k  på n · C(α). Den största skillnaden är att istället för att fixera k och variera det nödvändiga avståndet mellan punkter för en kant, vi fixerar en gräns på avståndet mellan två anslutna punkter i grafen, och därför kommer vi att ha små variationer i antalet grannar k från vertex till vertex. Lägg märke till likheten med sfäriskt lock LSH [5] och i synnerhet sfäriskt LSF [13, 6]: vi använder i huvudsak n slumpmässiga sfäriska filter centrerade runt våra datapunkter, och vi lägger till vektorer för att filtrera hinkar på samma sätt som i sfäriskt LSF: om den inre produkten med filtervektorn p är tillräckligt stor, lägger vi till punkten till denna skopa B(p). Men i andan av graf-baserade metoder söker vi efter en väg på närmaste granne graf som slutar på närmaste granne som i Algoritm 1, snarare än att kontrollera ett antal filter nära frågepunkten för att se om närmaste granne finns i någon av dessa. För att behandla en fråga q, vi först prov en jämnt slumpmässig punkt p  på U(D). Sedan går vi igenom dess grannar B(p) för att se om någon av dessa vektorer p  på B(p) är närmare q än p. I så fall använder vi detta som vår nya p ← p, och vi återigen se om någon av dess grannar är närmare q. Vi upprepar detta förfarande tills inga fler vektorer i B(p) är närmare q än p sig själv, i vilket fall p är vår uppskattning för den verkliga närmaste granne p * till q. Detta kan (p = p * ) eller inte (p = p * ) faktiskt vara den sanna närmaste granne till q, och för att få en högre framgångsfrekvens vi upprepar processen flera gånger, varje gång med början från en slumpmässig punkt p  på U (D). Medan fokus ligger på att minimera frågetiden, Algoritmer 2-3 visar också hur man gör uppdateringar av denna datastruktur, när vektorer infogas i D eller tas bort från D. Dessa delar av algoritmen kan mycket väl förbättras, och en viktig öppen fråga är att göra uppdateringar (särskilt tillägg) så effektiva som partitionsbaserade metoder, såsom i [6]. För att få bevisbara asymptotiska komplexiteter för detta tillvägagångssätt för (ungefär) närmaste granne problem, kommer vi att bevisa följande resultat i bilaga A för något värde γ max : • Små steg: Om p  på D uppfyller p, q γ max, sedan med icke-försumbar sannolikhet d kommer vi att hitta en något närmare granne p  på B(p) till q. • Giant språng: Om p  på D uppfyller p, q  till γ max, sannolikheten för att omedelbart hitta den exakta närmaste granne p * i hinken B (p) är större än vissa givna bundna. Graf-baserade tid-rymd kompromisser för ungefärliga nära grannar om inte framsteg då Algoritmer för att fråga α-nära granne graf med en frågepunkt q, och för att infoga / ta bort punkter från denna datastruktur. Här γ * är den (förväntade) inre produkten mellan q och dess sanna närmaste granne. Initialisera datastrukturen görs genom att välja α  på (0, 1) och till exempel anropa Infoga (p) för alla p  på D för att konstruera grafen adjacency hinkar B (p). Punkten p D betecknar den nuvarande nära granne uppskattningen för frågan q, och vi vill göra framsteg antingen genom att hitta en något närmare granne p  på B(p) när p är långt från q (vänster), eller hitta den exakta närmaste granne p *  på B(p) till frågan q när p redan är ganska nära q (höger). Tröskelvärdet för att separera dessa två fall är γmax. • Små steg (vänster). Om strömmen nära grannen p har inre produkt p, q = γ γmax med q, då förväntar vi oss att flera punkter p  och D \ {p * } fortfarande finns som ligger (lite) närmare q än p, och vi hoppas att åtminstone en av dem är en α-nära granne till p också. Eftersom en närmare granne i B(p) till q per definition ligger i W p,α,q, p,q ( skärningspunkten mellan de fasta sfäriska kapsylerna), och datamängden antas vara jämnt slumpmässig på sfären, sannolikheten för att hitta minst en sådan närmare granne är proportionell till n · W (α, γ, γ). • Stora språng (höger). När vi hittar en nära granne p till q med inre produkt p, q  på γmax, skulle vi vilja visa att i nästa steg, kommer vi att hitta p *  på B (p) med en viss (liten) sannolikhet. Förutsatt att p * är jämnt fördelat på Cq,γ *, Detta motsvarar sannolikheten att p *  till Wp,γ max,q,γ * ( skärningspunkten mellan de fasta sfäriska kapsylerna), konditionerade på händelsen p *  till Cq,γ * (den högra sfäriska kapsylen). Denna sannolikhet är därför proportionell mot W (α, γ *, γmax)/C (γ * ). • Randomisering: Eftersom "stora språng" ofta kan misslyckas, hävdar vi att start över vid slumpmässiga noder ett tillräckligt stort antal gånger leder till en konstant framgång sannolikhet. Vi bevisar att antalet hörn i varje hink, och på varje gång genom grafen, kan begränsas av små multiplar av deras förväntade värden. • Fråga komplexitet: Med hjälp av dessa resultat, vi härleder gränser på tiden komplexitet för att svara på frågor, med och utan att börja om vid slumpmässiga noder i grafen. • Utrymme komplexitet: På samma sätt, eftersom antalet kanter i grafen kan begränsas på lämpligt sätt, vi få snäva gränser på den nödvändiga utrymme komplexitet.  5 Asymptotik för glesa datauppsättningar På grund av rymdbegränsningar har härledningen av asymptotiken på de olika kostnaderna för grafbaserade nära granne söker efter stora d flyttats till bilaga B. Dess härledning består huvudsakligen av att noggrant skriva ut de kostnader som anges i föregående sats, och göra serie Theorem 9 (Komplexiteter för glesa data). Låt n = 1/C(μ) = 2 o(d) och låt α = σ · μ. Låt γ * = 1 − 1/c 2 betecknar den inre produkten mellan frågan och den (planterade) närmaste granne. Med hjälp av den α-NNG med α = ε·μ med γ * ( (γ * ) 2 / (1 + (γ * ) 2 ), 1), med stor sannolikhet kan vi lösa det glesa problemet nära grannen i flera iterationer med följande komplexiteter: Att ange frågetiden komplexitet av Time = n ρq+o(1) och utrymmet komplexitet av Space = n 1+ρs+o(1), avvägningen mellan dessa kostnader kan uttryckas med hjälp av följande ojämlikhet: Som beskrivs i inledningen, för c 1 och ρ s → 0, ovanstående villkor på ρ q skalor som ρ q ≥ 1 + 4 c − 1) 2 + O (c − 1) 4 ), vilket motsvarar skalningen nära c = 1 för optimal partition-bas nära grannmetoden [6]. För större c och när du använder mer utrymme, detta diagram-baserade tidsrymd kompromisser för ungefärlig nära grannar kompromiss-off är inte bättre än de bästa hash-baserade metoder - genom att ersätta ρs (1 − ρ s ) ≤ 1 2, vi får nödvändig (men inte tillräcklig) villkor ρ q ≥ c 2 / (2c 2 − 1), som visar att frågan komplexitet aldrig minskar bortom ε n, även för stora c. Denna oförmåga att "vinst" från stora approximativa faktorer kan vara inneboende i graf-baserade metoder, eller åtminstone till den giriga graf-baserade metod som beaktas i detta papper. För den "balanserade" avvägningen av ρ q = ρ s = ρ översätts villkoret på exponenterna till: För små c 1 leder detta till den asymptotiska skalningen ρ = 1 − 4 c − 1) 2 + O(c − 1) 3 ), vilket är något värre än den optimala hashbaserade avvägningen av [5, 6] Asymptotika för täta datauppsättningar För datauppsättningar av storlek n = 2  på (d), gäller inte asymptotikerna från föregående avsnitt; dessa antog att μ = 1 − n −2/d = o(1). I vissa tillämpningar är relationen d =  på (log n) mer exakt, och utan tvekan även om t.ex. d =  till (log n log log n) växer snabbare än log n, asymptotik för sparse regim kan vara ganska optimistisk; log log n termer anses då "stor", även om för realistiska parametrar log log n kan lika gärna anses konstant. I bilaga C har vi utfört en fallstudie för en applikation där μ = 1 − n −2/d = 1 2, så att n  på 2 d/5. Detta exempel är motiverat av algoritmer för att lösa svåra lattice-problem och kryptoanalyserande lattice-baserade kryptosystem, som tidigare har förbättrats med hjälp av andra (hash-baserade) metoder nära grannen [34, 14, 13]. Jämförbara resultat kan hålla för andra applikationer också; GloVe datamängd [45] innehåller n = 1.2M  och 2 20 vektorer i d = 100 dimensioner, vilket motsvarar n 2 d/5, medan SIFT har datamängd [2] har n = 1M vektorer i d = 128 dimensioner, vilket motsvarar n 2 0.35 d. Slutsatserna om jämförelsen av graf-baserade nära granne söker tekniker med hash-baserade metoder (i bilaga C) kan därför tillämpas på andra datamängder och applikationer också. Observera att eftersom de exakta avvägningarna beror på många parametrar (se Theorem 1), anger vi inte ett huvudresultat här, och hänvisa läsaren till bilaga C för en specifik fallanalys för lattice sikting. För godtyckliga densiteter och målvinklar är detta en fråga om att skriva ut uttrycken från Theorem 1 och titta på den asymptotiska skalningen av de olika kostnaderna.
Det enda teoretiska dokument vi känner till är REF med tanke på det glesa systemet d log n. Det nuvarande dokumentet skiljer sig åt i flera viktiga aspekter, även om det använder en liknande inställning.