Ungefärlig sökning på närmaste granne (ANN) i högdimensionellt utrymme har blivit ett grundläggande paradigm i många tillämpningar. Nyligen har Locality Sensitive Hashing (LSH) och dess varianter erkänts som de mest lovande lösningarna på ANN-sökning. De senaste LSH-metoderna har dock en nackdel: tillgången till kandidatobjekt kräver ett stort antal slumpmässiga I/O-operationer. För att garantera kvaliteten på returnerade resultat bör tillräckliga föremål kontrolleras, vilket skulle innebära en enorm I/O-kostnad. För att ta itu med detta föreslår vi en ny metod, som heter Sorting Keys-LSH (SK-LSH), som minskar antalet sidåtkomster genom att lokalt arrangera kandidatobjekt. Vi definierar först en ny åtgärd för att utvärdera avståndet mellan den sammansatta hashtangenterna på två punkter. Därefter skapas en linjär ordningsrelation på uppsättningen sammansatta hashtangenter, och motsvarande datapunkter kan sorteras därefter. Därför kan datapunkter som ligger nära varandra enligt avståndsmåttet lagras lokalt i en indexfil. Under ANN-sökningen är endast ett begränsat antal disksidor bland få indexfiler nödvändiga för att få tillgång till tillräcklig kandidatgenerering och verifiering, vilket inte bara avsevärt minskar svarstiden utan också förbättrar riktigheten av de returnerade resultaten. Vår uttömmande empiriska studie över flera verkliga datauppsättningar visar den överlägsna effektiviteten och noggrannheten hos SK-LSH för ANN-sökningen, jämfört med toppmoderna metoder, inklusive LSB, C2LSH och CK-Means.
I REF presenterar författarna SK-LSH, där de föreslår en ny linjär ordning på de indexfiler som lagras på den externa lagringen baserat på deras Zorderkoder.
SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}