Defnyddir dod o hyd i ddibyniaethau swyddogaethol mewn data mewn amrywiol feysydd dadansoddi data: rheoli cronfa ddata, glanhau data, peirianneg wrthdroi cronfeydd data ac archwilio data. Yr ydym eisoes wedi cyhoeddi am y dibyniaethau eu hunain Anastasia Birillo a Nikita Bobrov. Y tro hwn, mae Anastasia, un o raddedigion y Ganolfan Gyfrifiadureg eleni, yn rhannu datblygiad y gwaith hwn fel rhan o'r gwaith ymchwil a amddiffynnodd yn y ganolfan.
Dewis tasg
Wrth astudio yn y ganolfan CS, dechreuais astudio cronfeydd data yn fanwl, sef chwilio am ddibyniaethau swyddogaethol a gwahaniaethol. Roedd y pwnc hwn yn ymwneud â phwnc fy ngwaith cwrs yn y brifysgol, felly wrth weithio ar y gwaith cwrs, dechreuais ddarllen erthyglau am wahanol ddibyniaethau mewn cronfeydd data. Ysgrifennais adolygiad o'r maes hwn - un o fy rhai cyntaf yn Saesneg a'i gyflwyno i gynhadledd SEIM-2017. Roeddwn yn hapus iawn pan glywais ei bod wedi'i derbyn wedi'r cyfan, a phenderfynais ymchwilio'n ddyfnach i'r pwnc. Nid yw'r cysyniad ei hun yn newydd - dechreuwyd ei ddefnyddio yn ôl yn y 90au, ond hyd yn oed nawr fe'i defnyddir mewn llawer o feysydd.
Yn ystod fy ail semester yn y ganolfan, dechreuais brosiect ymchwil i wella algorithmau ar gyfer dod o hyd i ddibyniaethau swyddogaethol. Bu'n gweithio arno ar y cyd â myfyriwr graddedig o Brifysgol Talaith St. Petersburg Nikita Bobrov yn JetBrains Research.
Cymhlethdod cyfrifiadol chwilio am ddibyniaethau swyddogaethol
Y brif broblem yw cymhlethdod cyfrifiannol. Mae nifer y dibyniaethau lleiaf posibl a dibwys wedi'i gyfyngu uwchlaw'r gwerth 
lle 
— nifer priodoleddau tabl. Mae amser gweithredu'r algorithmau yn dibynnu nid yn unig ar nifer y priodoleddau, ond hefyd ar nifer y rhesi. Yn y 90au, gallai algorithmau chwilio cyfraith ffederal ar gyfrifiadur pen desg arferol brosesu setiau data sy'n cynnwys hyd at 20 o nodweddion a degau o filoedd o resi mewn hyd at sawl awr. Mae algorithmau modern sy'n rhedeg ar broseswyr aml-graidd yn canfod dibyniaethau ar gyfer setiau data sy'n cynnwys cannoedd o briodoleddau (hyd at 200) a channoedd o filoedd o resi mewn tua'r un amser. Fodd bynnag, nid yw hyn yn ddigon: mae amser o'r fath yn annerbyniol ar gyfer y rhan fwyaf o gymwysiadau byd go iawn. Felly, rydym wedi datblygu dulliau i gyflymu algorithmau presennol.
Cynlluniau caching ar gyfer croestoriadau rhaniad
Yn rhan gyntaf y gwaith, fe wnaethom ddatblygu cynlluniau caching ar gyfer dosbarth o algorithmau sy'n defnyddio'r dull croestoriad rhaniad. Set o restrau yw rhaniad ar gyfer priodoledd, lle mae pob rhestr yn cynnwys rhifau llinell gyda'r un gwerthoedd ar gyfer priodoledd penodol. Gelwir pob rhestr o'r fath yn glwstwr. Mae llawer o algorithmau modern yn defnyddio rhaniadau i benderfynu a yw dibyniaeth yn cael ei chynnal ai peidio, sef, maent yn cadw at y lema: Dibyniaeth 
a gynhelir os 
. Yma 
dynodir rhaniad a defnyddir y cysyniad o faint rhaniad - nifer y clystyrau sydd ynddo. Algorithmau sy'n defnyddio rhaniadau, pan fydd y ddibyniaeth yn cael ei dorri, yn ychwanegu priodoleddau ychwanegol i ochr chwith y ddibyniaeth, ac yna ei ailgyfrifo, gan berfformio gweithrediad croestoriad rhaniadau. Gelwir y llawdriniaeth hon yn arbenigo yn yr erthyglau. Ond fe wnaethom sylwi y gellir ailddefnyddio rhaniadau ar gyfer dibyniaethau a fyddai ond yn cael eu cadw ar ôl ychydig o gylchoedd o arbenigedd, a all leihau amser rhedeg yr algorithmau yn sylweddol, gan fod y gweithrediad croestoriad yn ddrud.
Felly, cynigiom hewristig yn seiliedig ar Shannon Entropi ac Ansicrwydd Ginny, yn ogystal â'n metrig, y gwnaethom ei alw'n Entropi Gwrthdro. Mae'n addasiad bychan o Shannon Entropi ac yn cynyddu wrth i unigrywiaeth y set ddata gynyddu. Mae'r hewristig arfaethedig fel a ganlyn:
Yma 
— graddau unigrywiaeth y rhaniad a gyfrifwyd yn ddiweddar 
Ac 
yw canolrif y graddau o unigrywiaeth ar gyfer priodoleddau unigol. Profwyd y tri metrig a ddisgrifir uchod fel metrig unigrywiaeth. Gallwch hefyd sylwi bod dau addasydd yn yr hewristig. Mae'r cyntaf yn nodi pa mor agos yw'r rhaniad presennol i'r allwedd gynradd ac yn caniatáu ichi storio'r rhaniadau hynny sy'n bell o'r allwedd bosibl i raddau mwy. Mae'r ail addasydd yn eich galluogi i fonitro deiliadaeth storfa ac felly'n eich annog i ychwanegu mwy o raniadau i'r storfa os oes lle am ddim ar gael. Roedd datrysiad llwyddiannus y broblem hon yn ein galluogi i gyflymu algorithm PYRO 10-40%, yn dibynnu ar y set ddata. Mae'n werth nodi mai'r algorithm PYRO yw'r mwyaf llwyddiannus yn y maes hwn.
Yn y ffigur isod gallwch weld canlyniadau cymhwyso'r hewristig arfaethedig o'i gymharu â dull caching darn arian-fflip sylfaenol. Mae'r echelin X yn logarithmig.
Ffordd amgen o storio rhaniadau
Yna fe wnaethom gynnig ffordd amgen o storio rhaniadau. Mae rhaniadau yn set o glystyrau, ac mae pob un ohonynt yn storio niferoedd tuples gyda gwerthoedd union yr un fath ar gyfer nodweddion penodol. Gall y clystyrau hyn gynnwys dilyniannau hir o rifau tuple, er enghraifft, os yw'r data mewn tabl wedi'i drefnu. Felly, cynigiwyd cynllun cywasgu ar gyfer storio rhaniadau, sef storio gwerthoedd mewn clystyrau o raniadau yn ysbeidiol:
$$display$$pi(X) = {{ underbrace{1, 2, 3, 4, 5}_{Cyfwng cyntaf}, underbrace{7, 8}_{Ail egwyl}, 10}}\ downarrow{ Cywasgu} \ pi(X) = {{ underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Roedd y dull hwn yn gallu lleihau'r defnydd o gof yn ystod gweithrediad yr algorithm TONE o 1 i 25%. Mae algorithm TONE yn algorithm clasurol ar gyfer chwilio am gyfreithiau ffederal; mae'n defnyddio rhaniadau yn ystod ei waith. Fel rhan o'r arfer, dewiswyd yr algorithm TANE, gan ei bod yn llawer haws gweithredu storfa egwyl ynddo nag, er enghraifft, yn PYRO er mwyn gwerthuso a yw'r dull arfaethedig yn gweithio. Cyflwynir y canlyniadau a gafwyd yn y ffigur isod. Mae'r echelin X yn logarithmig.
Cynhadledd ADBIS-2019
Yn seiliedig ar ganlyniadau'r ymchwil, ym mis Medi 2019 cyhoeddais erthygl yn y 23ain Gynhadledd Ewropeaidd ar Ddatblygiadau mewn Cronfeydd Data a Systemau Gwybodaeth (ADBIS-2019). Yn ystod y cyflwyniad, nodwyd y gwaith gan Bernhard Thalheim, person arwyddocaol ym maes cronfeydd data. Roedd canlyniadau'r ymchwil yn sail i'm traethawd hir yn y radd meistr mewn mathemateg a mecaneg ym Mhrifysgol Talaith St Petersburg, pan weithredwyd y ddau ddull arfaethedig (celcio a chywasgu) yn y ddau algorithm: TANE a PYRO. Ar ben hynny, dangosodd y canlyniadau fod y dulliau arfaethedig yn gyffredinol, oherwydd ar y ddau algorithm, gyda'r ddau ddull, gwelwyd gostyngiad sylweddol yn y defnydd o gof, yn ogystal â gostyngiad sylweddol yn amser gweithredu'r algorithmau.
Ffynhonnell: hab.com
