Vi presenterar ett nytt tillvägagångssätt för den ungefärliga K-nearest grannessökning baserad på navigator små världsgrafer med kontrollerbar hierarki (Hierarkical NSW, HNSW). Den föreslagna lösningen är helt grafbaserad, utan behov av ytterligare sökstrukturer (vanligtvis används vid grov sökning i de mest närliggande graftekniker). Hierarkiska NSW bygger stegvis en flerskiktsstruktur bestående av en hierarkisk uppsättning av närhetsgrafer (lager) för inhägnade undergrupper av de lagrade elementen. Det maximala skikt i vilket ett element finns väljs slumpmässigt med en exponentiellt sönderfallande sannolikhetsfördelning. Detta gör det möjligt att producera grafer liknande de tidigare studerade Navigable Small World (NSW) strukturer samtidigt som de dessutom har länkar åtskilda av sina karakteristiska avstånd skalor. Starta sökningen från det övre lagret tillsammans med att använda skalan separation ökar prestandan jämfört med NSW och möjliggör en logaritmisk komplexitet skalning. Ytterligare sysselsättning av en heurist för att välja närhet graf grannar avsevärt ökar prestanda vid hög recall och vid mycket klusterade data. Prestandautvärderingen har visat att det föreslagna allmänna metriska indexet för rymdsökning i hög grad kan överträffa tidigare metoder med enbart vektorer med öppen källkod. Likhet av algoritmen till hoppa lista struktur möjliggör enkel balanserad distribuerat genomförande. Index Termer-Graph och träd sökstrategier, artificiell intelligens, informationssökning och hämtning, informationslagring och hämtning, informationsteknik och system, sökprocess, grafer och nätverk, datastrukturer, närmaste grannsökning, big data, ungefärlig sökning, likhetssökning Ç Y. A. Malkov är med
Malkov m.fl. REF bygga en hierarkisk graf struktur för att påskynda närmaste grannsökning.
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
{'venue': 'IEEE Transactions on Pattern Analysis and Machine Intelligence', 'journal': 'IEEE Transactions on Pattern Analysis and Machine Intelligence', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Medicine']}