Närmaste granne söker efter stora databaser i högdimensionella utrymmen är i sig svårt på grund av förbannelsen av dimensionalitet. En smak av approximation är därför nödvändig för att praktiskt lösa problemet med närmaste granne sökande. I detta papper föreslår vi en ny men ändå enkel indexeringsschema, HD-Index, för att lösa problemet med ungefärlig k-nearest granne frågor i massiva högdimensionella databaser. HD-Index består av en uppsättning nya hierarkiska strukturer som kallas RDB-träd byggda på Hilbert nycklar databasobjekt. Bladen på RDB-träden lagrar distanser av databasobjekt för att referensobjekt, vilket möjliggör effektiv beskärning med hjälp av avståndsfilter. Förutom triangulär ojämlikhet, använder vi också Ptolemaic ojämlikhet för att producera bättre lägre gränser. Experiment på massiva (upp till miljarder skalor) högdimensionella (upp till 1000+) datauppsättningar visar att HD-Index är effektivt, effektivt och skalbart.  Kategorier och ämnesdeskriptorer Närmaste granne (NN) sökning är ett grundläggande problem med applikationer i informationssökning, datautvinning, multimedia och vetenskapliga databaser, sociala nätverk, för att nämna några. Med tanke på en frågepunkt q, NN problemet är att identifiera ett objekt o från en datauppsättning av objekt D sådan att q är närmast o än något annat objekt. En användbar förlängning är att identifiera k-nearest grannar (kNN), dvs en beställd uppsättning av toppk närmaste objekt {o1,. ................................................................ Även om det finns en mängd skalbara metoder för att effektivt besvara NN-frågor i små och medelstora utrymmen [9–12, 14, 20, 21, 28, 55, 61], skalas de inte graciöst med ökningen av dimensionaliteten i datauppsättningen. Under det strikta kravet att svaret som returnerades skulle vara helt korrekt, problemet med * Författaren var anställd på American Express Big Data Labs under inlämnandet av detta arbete. † Arbetet gjordes medan författarna var studenter vid Indian Institute of Technology Kanpur, och de bidrog lika mycket. hög dimensionalitet i likhet sökningar, ofta fruktade som "förbannelsen av dimensionalitet" [14], gör dessa metoder värdelösa i jämförelse med en enkel linjär scanning av hela databasen [71]. I många praktiska tillämpningar kan dock ett sådant strikt krav på korrekthet offras för att mildra dimensionalitetsförbannelsen och uppnå praktiska körtider [26, 64, 66]. En webbscale sökning efter liknande bilder, t.ex., Google Images (www.google.com/imghp), Tineye (www.tineye.com), RevIMG (www.revimg.com), kanske bäst exemplifierar ett sådant program. Dessutom är en enda fråga ofta bara ett mellanliggande steg och aggregeringar av resultat över många sådana frågor krävs för den övergripande hämtningsprocessen. Till exempel, i bildsökning, i allmänhet flera bild keypoints söks. Den strikta noggrannheten hos en enda bild keypoint sökning är därför inte så kritisk eftersom den totala aggregering generellt kan tolerera små fel. Med denna avkoppling omvandlas NN- och kNN-problemen till ANN (ungefär närmaste grannar) respektive kANN-problem, där ett fel kontrolleras av en parameter c som definierar approximationsförhållandet (definieras formellt i Def. 1), är tillåtet. De återvunna föremålen o = {o 1,. .., o k } är sådan att deras avstånd från q är som mest c gånger avståndet för de faktiska närmaste objektet(s) o = {o1,. ....., o k } respektive............................................................................................. Den lokalkänsliga hashingen (LSH) familjen [34] är en av de mest populära metoderna för att effektivt svara på kANN frågor i sub-linjär tid. Dessa metoder är dock inte skalbara på grund av kravet på stort utrymme för att bygga indexet som är super-linjär i storleken på datauppsättningen [24]. Även om det har skett många förbättringar på senare tid [26, 44, 65] i den ursprungliga LSH-metoden i syfte att minska indexeringsutrymmet, kräver de asymptotiskt fortfarande superlinjärt utrymme och skalas därför inte till mycket stora datamängder. Ett nytt förslag, SRS [64], tar upp detta problem genom att införa ett linjärt index samtidigt som hög effektivitet bibehålls och är den senaste tekniken i denna klass av tekniker. En anmärkningsvärd praktisk begränsning av dessa tekniker med teoretiska garantier är att felet mäts med hjälp av approximationsförhållandet c. Eftersom uppgiften är att identifiera en beställd uppsättning k närmaste objekt till en frågepunkt q, är rangen vid vilken ett objekt hämtas betydande. Eftersom c kännetecknas av egenskaperna hos förhållandet mellan avstånd mellan punkter i en vektorutrymme, en låg (nära till 1) approximation förhållande garanterar inte alltid liknande relativ beställning av de hämtade objekt. Detta problem förvärras med ökad dimensionalitet mot, eftersom avstånden tenderar att förlora sin betydelse, och bli mer och mer lik varandra [14]. Matematiskt, lim mot→ņ dmax d min = 1 där dmax och dmin är de maximala och minsta parvisa avstånden mellan en ändlig uppsättning n punkter. Därför är det inte förvånande att c snabbt närmar sig 1 för extremt högdimensionella utrymmen (dimensionellitet ≥ 100). Således, medan c kan 1 arXiv:1804.06829v2 [cs.DB]
Nyligen infördes HD-Index REF som genererade Hilbert nycklar till dataset objekt och även lagrade avstånden mellan objekten till varandra för att effektivt beskära resultaten baserat på distansfilter.
HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}