Maišos naudojimas yra pagrindinė daugelio internetinių duomenų bazių, pvz., bibliotekos katalogo ar el. prekybos svetainės, operacija. Maišos funkcija generuoja kodus, kurie tiesiogiai nustato vietą, kurioje bus saugomi duomenys. Taigi, naudojant šiuos kodus, lengviau rasti ir gauti duomenis.
Tačiau kadangi tradicinės maišos funkcijos kodus generuoja atsitiktinai, kartais du duomenų vienetai gali būti maišomi su ta pačia verte. Tai sukelia susidūrimus – ieškodamas vieno elemento vartotojas atkreipia dėmesį į daug duomenų su ta pačia maišos verte. Norint rasti tinkamą, užtrunka daug ilgiau, todėl paieška lėtėja ir našumas sumažėja.
Tam tikri maišos funkcijų tipai, vadinami tobulomis maišos funkcijomis, yra skirti pateikti duomenis taip, kad būtų išvengta susidūrimų. Tačiau juos sukurti kiekvienam duomenų rinkiniui užtrunka daug laiko ir apskaičiuojant reikia daugiau laiko nei tradicinėms maišos funkcijoms.
Kadangi maiša naudojama daugelyje programų, nuo duomenų bazės indeksavimo iki duomenų glaudinimo iki kriptografijos, greitos ir veiksmingos maišos funkcijos yra labai svarbios. Taigi mokslininkai iš MIT ir kitur nusprendė išsiaiškinti, ar jie galėtų panaudoti mašininį mokymąsi, kad sukurtų geresnes maišos funkcijas.
Jie nustatė, kad tam tikrose situacijose naudojant išmoktus modelius, o ne tradicines maišos funkcijas, gali atsirasti perpus mažiau susidūrimų. Šie išmokti modeliai sukuriami duomenų rinkinyje paleidžiant mašininio mokymosi algoritmą, kad būtų užfiksuotos konkrečios charakteristikos. Komandos eksperimentai taip pat parodė, kad išmokti modeliai dažnai buvo efektyvesni skaičiavimo požiūriu nei tobulos maišos funkcijos.
„Šiame darbe mes nustatėme, kad kai kuriose situacijose galime rasti geresnį kompromisą tarp maišos funkcijos skaičiavimo ir susidūrimų, su kuriais susidursime. Tokiose situacijose maišos funkcijos skaičiavimo laikas gali būti šiek tiek padidintas, tačiau tuo pačiu metu jos susidūrimai gali labai sumažėti“, – sako Ibrahimas Sabekas, kompiuterių mokslo ir dirbtinio intelekto MIT duomenų sistemų grupės postdoc. Laboratorija (CSAIL).
Jų tyrimas, kuris bus pristatytas 2023 m. tarptautinėje labai didelių duomenų bazių konferencijoje, parodo, kaip maišos funkcija gali būti sukurta taip, kad būtų žymiai pagreitinta paieška didžiulėje duomenų bazėje. Pavyzdžiui, jų technika galėtų pagreitinti skaičiavimo sistemas, kurias mokslininkai naudoja DNR, aminorūgščių sekoms ar kitai biologinei informacijai saugoti ir analizuoti.
Sabekas yra bendras šio straipsnio autorius su Elektros inžinerijos ir informatikos katedros (EECS) absolventu Kapilu Vaidya. Prie jų prisijungia bendraautoriai Dominick Horn, Miuncheno technikos universiteto magistrantas; Andreasas Kipfas, MIT postdoc; Michaelas Mitzenmacheris, Harvardo Johno A. Paulsono inžinerijos ir taikomųjų mokslų mokyklos kompiuterių mokslų profesorius; ir vyresnysis autorius Timas Kraska, MIT EECS docentas ir duomenų, sistemų ir AI laboratorijos direktorius.
Sumaišyti
Atsižvelgiant į duomenų įvestį arba raktą, tradicinė maišos funkcija generuoja atsitiktinį skaičių arba kodą, atitinkantį lizdą, kuriame bus saugomas tas raktas. Paprastas pavyzdys: jei į 10 lizdų reikia įdėti 10 klavišų, funkcija kiekvienai įvestiei generuotų sveikąjį skaičių nuo 1 iki 10. Labai tikėtina, kad du klavišai atsidurs tame pačiame lizde ir sukels susidūrimus.
Puikios maišos funkcijos suteikia alternatyvą be susidūrimų. Tyrėjai suteikia šiai funkcijai papildomų žinių, pvz., apie laiko tarpsnių, į kuriuos turi būti įdėta, skaičių. Tada jis gali atlikti papildomus skaičiavimus, kad išsiaiškintų, kur įdėti kiekvieną klavišą, kad būtų išvengta susidūrimų. Tačiau šie papildomi skaičiavimai apsunkina funkcijos kūrimą ir sumažina jos efektyvumą.
„Mums buvo įdomu, jei žinome daugiau apie duomenis – kad jie bus gauti iš tam tikro platinimo – ar galime panaudoti išmoktus modelius maišos funkcijai sukurti, kuri iš tikrųjų gali sumažinti susidūrimų skaičių? Vaidya sako.
Duomenų paskirstymas rodo visas galimas duomenų rinkinio reikšmes ir tai, kaip dažnai kiekviena reikšmė atsiranda. Paskirstymas gali būti naudojamas apskaičiuojant tikimybę, kad tam tikra reikšmė yra duomenų pavyzdyje.
Tyrėjai paėmė nedidelį pavyzdį iš duomenų rinkinio ir naudojo mašininį mokymąsi, kad apytiksliai apskaičiuotų duomenų pasiskirstymo formą arba duomenų paskirstymą. Tada išmoktas modelis naudoja aproksimaciją, kad nuspėtų rakto vietą duomenų rinkinyje.
Jie nustatė, kad išmoktus modelius buvo lengviau sukurti ir juos paleisti greičiau nei tobulas maišos funkcijas ir kad jie sukėlė mažiau susidūrimų nei naudojant tradicines maišos funkcijas, jei duomenys paskirstomi nuspėjamu būdu. Tačiau jei duomenys nenuspėjamai paskirstomi, nes tarpai tarp duomenų taškų per daug skiriasi, naudojant išmoktus modelius gali atsirasti daugiau susidūrimų.
„Galime turėti daug duomenų įvesties, o tarpai tarp nuoseklių įvesties duomenų labai skiriasi, todėl gana sunku išmokti modelį, leidžiantį užfiksuoti šių įvesties duomenų pasiskirstymą“, – aiškina Sabekas.
Mažiau susidūrimų, greitesni rezultatai
Kai duomenys buvo paskirstomi nuspėjamai, išmokti modeliai gali sumažinti susidūrimo raktų santykį duomenų rinkinyje nuo 30 procentų iki 15 procentų, palyginti su tradicinėmis maišos funkcijomis. Jie taip pat sugebėjo pasiekti geresnį pralaidumą nei tobulos maišos funkcijos. Geriausiais atvejais išmokti modeliai sutrumpino veikimo laiką beveik 30 procentų.
Tyrinėdami išmoktų modelių naudojimą maišai, mokslininkai taip pat nustatė, kad pralaidumui didžiausią įtaką turėjo antrinių modelių skaičius. Kiekvienas išmoktas modelis sudarytas iš mažesnių linijinių modelių, kurie apytiksliai apskaičiuoja skirtingų duomenų dalių pasiskirstymą. Naudojant daugiau antrinių modelių, išmoktas modelis sukuria tikslesnį apytikslį apskaičiavimą, tačiau tam reikia daugiau laiko.
„Esant tam tikram submodelių slenksčiui, jūs gaunate pakankamai informacijos, kad sukurtumėte aproksimaciją, kurios jums reikia maišos funkcijai. Tačiau po to tai nepadės didesnio susidūrimų mažinimo“, – sako Sabekas.
Remdamiesi šia analize, mokslininkai nori naudoti išmoktus modelius, kad sukurtų kitų tipų duomenų maišos funkcijas. Jie taip pat planuoja ištirti išmoktą maišą duomenų bazėms, į kurias galima įterpti arba ištrinti duomenis. Kai duomenys atnaujinami tokiu būdu, modelis turi atitinkamai keistis, tačiau modelio keitimas išlaikant tikslumą yra sudėtinga problema.
„Norime paskatinti bendruomenę naudoti mašininį mokymąsi pagrindinėse duomenų struktūrose ir algoritmuose. Bet kokia pagrindinė duomenų struktūra suteikia mums galimybę naudoti mašininį mokymąsi, kad užfiksuotume duomenų ypatybes ir pagerintume našumą. Dar daug ką galime ištirti“, – sako Sabekas.
„Maišos ir indeksavimo funkcijos yra daugelio duomenų bazės funkcijų pagrindas. Atsižvelgiant į vartotojų ir naudojimo atvejų įvairovę, nėra vieno visiems tinkančio maišymo, o išmokti modeliai padeda pritaikyti duomenų bazę konkrečiam vartotojui. Šis dokumentas yra puiki subalansuota šių naujų metodų pagrįstumo analizė. Jame puikiai kalbama apie privalumus ir trūkumus, taip pat padeda mums suprasti, kada galima tikėtis, kad tokie metodai veiks gerai“, – sako Murali Narayanaswamy. pagrindinis „Amazon“ mašininio mokymosi mokslininkas, kuris nedalyvavo šiame darbe. „Tokių patobulinimų tyrinėjimas yra įdomi mokslinių tyrimų sritis tiek akademinėje bendruomenėje, tiek pramonėje, o šiame darbe parodytas griežtumas yra labai svarbus, kad šie metodai turėtų didelį poveikį.
Šį darbą iš dalies palaikė „Google“, „Intel“, „Microsoft“, JAV nacionalinis mokslo fondas, JAV oro pajėgų tyrimų laboratorija ir JAV oro pajėgų dirbtinio intelekto greitintuvas.
