Kupeza kudalira kwa data kumagwiritsidwa ntchito m'magawo osiyanasiyana osanthula deta: kasamalidwe ka database, kuyeretsa deta, uinjiniya wa reverse database, ndi kufufuza deta. Tasindikiza kale za odalira okha. Anastasia Birillo ndi Nikita Bobrov. Panthawiyi, Anastasia, womaliza maphunziro a Computer Science Center chaka chino, akugawana chitukuko cha polojekitiyi, yomwe adayiteteza pakatikati.
Kusankha ntchito
Ndikuphunzira ku CS Center, ndinayamba kuphunzira mozama, makamaka, kupeza zodalira ndi zosiyana. Mutuwu unali wokhudzana ndi maphunziro anga aku yunivesite, kotero ndikugwira ntchito, ndinayamba kuwerenga nkhani zokhudzana ndi kudalira kosiyanasiyana m'malo osungira. Ndinalemba ndemanga ya gawo ili - imodzi mwazoyamba zanga m'Chingerezi ndikuzipereka ku msonkhano wa SEIM-2017. Ndinasangalala kwambiri atavomerezedwa ndipo ndinaganiza zozama za mutuwo. Lingaliro palokha silatsopano - lakhalapo kuyambira m'ma 90s - koma likugwirabe ntchito m'magawo ambiri lero.
Mu semester yanga yachiwiri pakatikati, ndidayamba ntchito yofufuza kuti ndisinthe ma aligorivimu kuti ndipeze zomwe zimadalira. Ndinagwirapo ntchito ndi Nikita Bobrov, wophunzira womaliza maphunziro pa yunivesite ya St. Petersburg State, pa JetBrains Research.
Kuchulukirachulukira kwa kufunafuna kudalira kwa magwiridwe antchito
Vuto lalikulu ndi computational zovuta. Chiwerengero cha kudalira zotheka kochepa komanso kosawerengeka kumachepa kuchokera pamwamba 
kumene 
- chiwerengero cha mawonekedwe a tebulo. Nthawi yoyendetsa ma algorithms sizitengera kuchuluka kwa zikhumbo komanso kuchuluka kwa mizere. M'zaka za m'ma 90s, ma algorithms ozindikira malamulo aboma pa PC wamba amatha kukonza ma dataset okhala ndi ma 20 ndi mizere makumi masauzande kwa maola angapo. Ma aligorivimu amakono omwe amayendetsa ma processor amitundu yambiri amazindikira kudalira kwa ma dataset okhala ndi mazana ambiri (mpaka 200) ndi mizere mazana masauzande pafupifupi nthawi imodzi. Komabe, izi ndizosakwanira: nthawi yotereyi ndiyosavomerezeka pazogwiritsa ntchito zenizeni zenizeni. Chifukwa chake, tidapanga njira zofulumizitsa ma algorithm omwe alipo.
Ma caching schemes a partition intersection
M'gawo loyamba la pepalalo, tidapanga ma caching a kalasi ya ma algorithms pogwiritsa ntchito njira yogawa magawo. Kugawa kwa chikhalidwe ndi mndandanda wa mindandanda, pomwe mndandanda uliwonse uli ndi manambala amizere okhala ndi zikhalidwe zomwezo za chikhalidwe chomwe wapatsidwa. Mndandanda uliwonse wotere umatchedwa masango. Ma algorithms ambiri amakono amagwiritsa ntchito magawo kuti adziwe ngati kudalira kumagwira ntchito, ndiko kuti, amatsatira lemma iyi: Kudalira. 
imasungidwa ngati 
. Pano 
Kugawa kumatanthauzidwa ndi , ndipo lingaliro la kukula kwa magawo - chiwerengero cha masango mkati mwake - amagwiritsidwa ntchito. Ma aligorivimu omwe amagwiritsa ntchito magawo amawonjezera zina kumanzere kwa kudalira pamene kudalira kwaphwanyidwa, kenaka muwerengenso pochita opareshoni ya mphambano yogawa. Opaleshoniyi imatchulidwa m'nkhani ngati specialization. Komabe, tawona kuti magawo a zodalira zomwe zidzasungidwa pambuyo pa maulendo angapo apadera amatha kugwiritsidwanso ntchito mwakhama, zomwe zingathe kuchepetsa kwambiri nthawi yogwiritsira ntchito ma aligorivimu, chifukwa ntchito ya mphambano ndi yokwera mtengo.
Chifukwa chake, tidapereka lingaliro lachidziwitso chotengera Shannon entropy ndi kusatsimikizika kwa Gini, komanso metric yathu, yomwe timayitcha Inverse Entropy. Ndikusinthidwa pang'ono kwa Shannon entropy ndipo kumawonjezeka pamene kusiyanasiyana kwa deta kumawonjezeka. Cholinga cha heuristic ndi motere:
ndi 
- kuchuluka kwapadera kwa magawo omwe awerengedwa posachedwa 
ndi 
ndiye wapakati wa madigiri apadera amunthu payekha. Ma metric onse atatu omwe tafotokozawa adayesedwa ngati ma metrics apadera. Titha kudziwanso kuti heuristic imaphatikizapo zosintha ziwiri. Yoyamba ikuwonetsa momwe gawo lapano liliri pafupi ndi kiyi yoyamba ndipo limalola kusungitsa magawo ambiri kutali ndi kiyi ya ofuna kusankha. Chosintha chachiwiri chimayang'anira kusungidwa kwa cache, motero kulimbikitsa kuwonjezera magawo ambiri ku cache malo akapezeka. Kuthetsa bwino vutoli kunalola kuti PYRO algorithm ifulumire ndi 10-40% kutengera deta. Ndizofunikira kudziwa kuti algorithm ya PYRO ndiye yopambana kwambiri m'derali.
Chithunzi chomwe chili m'munsichi chikuwonetsa zotsatira za kugwiritsa ntchito njira yomwe ikuyembekezeredwa kuyerekeza ndi njira yosungiramo zoyambira potengera kutembenuka kwandalama. X-axis ndi logarithmic.
Njira ina yosungira magawo
Kenako tinapanga njira ina yosungira ma partitions. Magawo ndi magulu amagulu, omwe aliyense amasunga manambala a tuple okhala ndi mikhalidwe yofananira pamikhalidwe ina. Maguluwa amatha kukhala ndi manambala aatali otsatizana, mwachitsanzo, ngati deta yomwe ili patebulo yayitanitsa. Chifukwa chake, tidakonza chiwembu chophatikizira chosungira magawo, mwachitsanzo, kusungirako kwakanthawi kwamitengo mumagulu ogawa:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}\ downarrow{Compression}\ pi(X) = {{underbrace{$, 1, underbrace{7},{5} 8}_{Second~interval}, 10}}$$display$$
Njirayi inatha kuchepetsa kukumbukira kukumbukira panthawi ya kuphedwa kwa TANE algorithm ndi 1 mpaka 25%. Ma aligorivimu a TANE ndi njira yachikale yofufuzira madera omveka; imagwiritsa ntchito magawo panthawi yogwira ntchito. Pazolinga zothandiza, algorithm ya TANE idasankhidwa chifukwa kukhazikitsa kusungirako kwakanthawi kunali kosavuta kuposa, mwachitsanzo, mu PYRO kuwunika kuthekera kwa njira yomwe yaperekedwa. Zotsatira zikuwonetsedwa mu chithunzi pansipa. X-axis ndi logarithmic.
Msonkhano wa ADBIS-2019
Kutengera zotsatira za kafukufukuyu, ndidasindikiza nkhani mu Seputembara 2019. Pamsonkhano wa 23 wa European Conference on Advances in Databases and Information Systems (ADBIS-2019), ntchitoyi inazindikiridwa ndi Bernhard Thalheim, wodziwika bwino pazambiri. Zotsatira zafukufuku zinapanga maziko a zolemba zanga za pulogalamu ya Master mu Faculty of Mathematics and Mechanics ku St. Petersburg State University, pamene njira zonse zomwe zaperekedwa (caching and compression) zinakhazikitsidwa muzolemba zonse ziwiri: TANE ndi PYRO. Zotsatira zake zidawonetsa kuti njira zomwe zikuperekedwazo ndi zapadziko lonse lapansi, popeza ma algorithms onsewa adawonetsa kuchepa kwakukulu kwakugwiritsa ntchito kukumbukira komanso kuchepetsa kwambiri nthawi yopha.
Source: www.habr.com
