Að finna hagnýtar ósjálfstæði í gögnum er notað á ýmsum sviðum gagnagreiningar: gagnagrunnsstjórnun, gagnahreinsun, gagnagrunnsöfugþróun og gagnakönnun. Við höfum þegar birt um ósjálfstæðin sjálf Anastasia Birillo og Nikita Bobrov. Að þessu sinni deilir Anastasia, sem er útskrifuð frá Tölvufræðisetrinu í ár, þróun þessa verks sem hluta af rannsóknarvinnunni sem hún varði við miðstöðina.
Verkefnaval
Meðan ég stundaði nám við CS miðstöðina fór ég að rannsaka gagnagrunna ítarlega, nefnilega leitina að virkni- og mismunaháðum. Þetta efni var tengt viðfangsefni námskeiða minna við háskólann, svo á meðan ég vann að námskeiðinu fór ég að lesa greinar um ýmis ósjálfstæði í gagnagrunnum. Ég skrifaði umsögn um þetta svæði - eitt af mínum fyrstu á ensku og lagði það fyrir SEIM-2017 ráðstefnuna. Ég var mjög ánægð þegar ég komst að því að hún var samþykkt eftir allt saman og ákvað að kafa dýpra í efnið. Hugmyndin sjálf er ekki ný - það byrjaði að nota það aftur á 90s, en jafnvel núna er það notað á mörgum sviðum.
Á annarri önn minni í miðstöðinni byrjaði ég á rannsóknarverkefni til að bæta reiknirit til að finna hagnýtar ósjálfstæði. Hún vann að því ásamt St. Petersburg State University útskriftarnema Nikita Bobrov við JetBrains Research.
Reiknileg flókið leit að starfrænum ósjálfstæðum
Aðalvandamálið er flækjustig í reikningum. Fjöldi mögulegra lágmarks og óléttar ósjálfstæðis er takmarkaður að ofan af gildinu hvar — fjöldi töflueiginleika. Rekstrartími reikniritanna fer ekki aðeins eftir fjölda eiginda heldur einnig af fjölda raða. Á tíunda áratugnum gátu alríkislögleitaralgrím á venjulegri borðtölvu unnið úr gagnasettum sem innihéldu allt að 90 eiginleika og tugþúsundir raða á allt að nokkrum klukkustundum. Nútíma reiknirit sem keyra á fjölkjarna örgjörvum greina ósjálfstæði gagnasetta sem samanstanda af hundruðum eiginda (allt að 20) og hundruðum þúsunda raða á um það bil sama tíma. Hins vegar er þetta ekki nóg: slíkur tími er óviðunandi fyrir flest raunveruleg forrit. Þess vegna þróuðum við aðferðir til að flýta fyrir núverandi reikniritum.
Skyndiminni kerfi fyrir gatnamót skipting
Í fyrsta hluta vinnunnar þróuðum við skyndiminniskerfi fyrir flokk reiknirita sem nota skiptingjaskurðaraðferðina. Skipting fyrir eigind er safn lista, þar sem hver listi inniheldur línunúmer með sömu gildum fyrir tiltekna eigind. Hver slíkur listi er kallaður klasi. Mörg nútíma reiknirit nota skipting til að ákvarða hvort ósjálfstæði sé haldið eða ekki, þau fylgja nefnilega lemmanum: Ósjálfstæði haldið ef . Hérna skilrúm er tilnefnt og hugtakið skiptingarstærð notað - fjöldi klasa í því. Reiknirit sem nota skipting, þegar ósjálfstæði er brotið, bæta við viðbótareigindum til vinstri hliðar á ósjálfstæði, og þá endurreikna það, framkvæma skurðaðgerð skiptinganna. Þessi aðgerð er kölluð sérhæfing í greinunum. En við tókum eftir því að skipting fyrir ósjálfstæði sem aðeins yrði haldið eftir eftir nokkrar umferðir sérhæfingar er hægt að endurnýta með virkum hætti, sem getur dregið verulega úr keyrslutíma reikniritanna, þar sem gatnamótaaðgerðin er dýr.
Þess vegna lögðum við til heuristic sem byggir á Shannon entropy og Ginny Uncertainty, auk mæligildis okkar, sem við kölluðum Reverse Entropy. Það er lítilsháttar breyting á Shannon Entropy og eykst eftir því sem sérstaða gagnasafnsins eykst. Fyrirhuguð heuristic er sem hér segir:
Hér — hversu sérstöðu nýlega reiknaða skiptingin er Og er miðgildi stigs sérstöðu fyrir einstaka eiginleika. Allir þrír mælikvarðar sem lýst er hér að ofan voru prófaðir sem sérstöðumælikvarði. Þú getur líka tekið eftir því að það eru tveir breytir í heuristic. Sú fyrsta gefur til kynna hversu nálægt núverandi skipting er aðallyklinum og gerir þér kleift að vista í meira mæli þá skipting sem eru langt frá hugsanlegum lykli. Annar breytirinn gerir þér kleift að fylgjast með skyndiminni og hvetur þar með til að bæta fleiri skiptingum við skyndiminni ef laust pláss er til staðar. Árangursrík lausn þessa vandamáls gerði okkur kleift að flýta PYRO reikniritinu um 10-40%, allt eftir gagnapakkanum. Þess má geta að PYRO reikniritið er farsælast á þessu sviði.
Á myndinni hér að neðan geturðu séð niðurstöðurnar af því að beita fyrirhugaðri heuristic samanborið við grunnmynt-flip skyndiminni nálgun. X-ásinn er lógaritmískur.
Önnur leið til að geyma skipting
Við lögðum síðan til aðra leið til að geyma skipting. Skipting er sett af þyrpingum, sem hver um sig geymir fjölda tuples með sömu gildum fyrir ákveðna eiginleika. Þessir þyrpingar geta innihaldið langar raðir af túllutölum, til dæmis ef gögnum í töflu er raðað. Þess vegna lögðum við til samþjöppunarkerfi til að geyma skipting, nefnilega millibilsgeymslu á gildum í þyrpingum skiptinga:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First interval}, underbrace{7, 8}_{Second interval}, 10}}\ downarrow{ Compression} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Með þessari aðferð tókst að draga úr minnisnotkun meðan á TANE reikniritinu stóð úr 1 í 25%. TANE reikniritið er klassískt reiknirit til að leita að alríkislögum; það notar skipting við vinnu sína. Sem hluti af æfingunni var TANE reikniritið valið, þar sem það var mun auðveldara að innleiða millibilsgeymslu í því en td í PYRO til að meta hvort fyrirhuguð nálgun virkar. Niðurstöðurnar sem fengust eru sýndar á myndinni hér að neðan. X-ásinn er lógaritmískur.
Ráðstefna ADBIS-2019
Byggt á niðurstöðum rannsóknarinnar birti ég grein í september 2019 á 23. Evrópuráðstefnu um framfarir í gagnasöfnum og upplýsingakerfum (ADBIS-2019). Á kynningunni vakti athygli Bernhard Thalheim, merkur einstaklingur á sviði gagnagrunna. Rannsóknarniðurstöðurnar lágu til grundvallar ritgerð minni í meistaranámi í stærðfræði og vélfræði við St. Petersburg State University, þar sem báðar fyrirhugaðar nálganir (skyndiminni og þjöppun) voru innleiddar í báðum reikniritunum: TANE og PYRO. Ennfremur sýndu niðurstöðurnar að fyrirhugaðar nálganir eru alhliða, þar sem á báðum reikniritunum, með báðum aðferðunum, kom fram marktæk minnkun á minnisnotkun, auk marktækrar minnkunar á notkunartíma reikniritanna.
Heimild: www.habr.com