Den senaste tidens införande av inlärda index har rubbat grunden för det decennier gamla området för indexering av datastrukturer. Att kombinera, eller till och med ersätta, klassiska designelement som B-tree noder med maskininlärningsmodeller har visat sig ge enastående förbättringar av datasystemens rymdavtryck och tidseffektivitet. Dessa nya tillvägagångssätt är emellertid baserade på heuristik, vilket gör att de saknar garantier både i tid och rymdbehov. Vi föreslår Piecewise Geometriska Modellindex (kort sagt PGM-index), som uppnår garanterad I/O-optimalitet i frågeoperationer, lär sig ett optimalt antal linjära modeller, och dess säregna rekursiva konstruktion gör det till en rent inlärd datastruktur, snarare än en hybrid av traditionella och inlärda index (såsom RMI och FITing-tree). Vi visar experimentellt att PGM-indexet förbättrar utrymmet för det mest kända inlärda indexet, dvs.. FIT-träd, med 63,3% och av B-trädet med mer än fyra storleksordningar, samtidigt uppnå samma eller ännu bättre frågetid effektivitet. Vi kompletterar detta resultat genom att föreslå tre varianter av PGM-indexet som tar upp några nyckelfrågor som uppstår i designen av moderna big datasystem. För det första utformar vi ett komprimerat PGM-index som ytterligare minskar dess koncisa rymdavtryck genom att utnyttja repetitiviteten i de lärda linjära modellerna som det består av. För det andra utformar vi ett PGM-index som anpassar sig till distributionen av frågeoperationerna, vilket resulterar i det första kända distributionsmedvetna inlärda indexet hittills. Slutligen föreslår vi, med tanke på flexibiliteten i de kompromisser som erbjuds i rymdtid, det multicriteria PGM-index vars specialitet är att effektivt automatiskt justera sig på några sekunder över hundratals miljoner nycklar till de eventuellt föränderliga rymdtidsbegränsningar som följer av användningen.
PGM-index REF utökar det inlärda indexet för att optimera strukturen med avseende på givna kompromisser mellan rum och tid.
The PGM-index: a multicriteria, compressed and learned approach to data indexing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}