Ny fitadiavana fiankinan-doha amin'ny angon-drakitra dia ampiasaina amin'ny sehatra isan-karazany amin'ny famakafakana angon-drakitra: fitantanana angon-drakitra, fanadiovana angon-drakitra, engineering reverse database ary fikarohana data. Efa navoakanay ny momba ny fiankinan-doha Anastasia Birillo sy Nikita Bobrov. Amin'ity indray mitoraka ity, i Anastasia, nahazo diplaoma tao amin'ny Foiben'ny Siansa Informatika tamin'ity taona ity, dia mizara ny fivoaran'ity asa ity ho ampahany amin'ny asa fikarohana narovany tao amin'ny foibe.
Fantenana asa
Raha nianatra tao amin'ny foibe CS aho dia nanomboka nandalina lalina ny angon-drakitra, izany hoe ny fitadiavana ny fiankinan-doha amin'ny asa sy ny fahasamihafana. Ity lohahevitra ity dia mifandraika amin'ny lohahevitry ny fianarana any amin'ny oniversite, ka raha niasa tamin'ny fianarana aho dia nanomboka namaky lahatsoratra momba ny fiankinan-doha isan-karazany amin'ny tahiry. Nanoratra famerenana momba ity faritra ity aho - iray amin'ireo voalohany amin'ny teny anglisy ary natolotra tamin'ny fihaonambe SEIM-2017. Faly be aho rehefa fantatro fa nekena izy, ary nanapa-kevitra ny handalina lalindalina kokoa ny lohahevitra. Ny foto-kevitra mihitsy dia tsy vaovao - nanomboka nampiasaina tamin'ny taona 90, fa na dia amin'izao fotoana izao dia ampiasaina amin'ny faritra maro.
Nandritra ny semester faharoa tao amin'ny foibe, dia nanomboka tetik'asa fikarohana aho hanatsarana ny algorithm amin'ny fitadiavana fiankinan-doha miasa. Niara-niasa tamin'i Nikita Bobrov, mpianatra nahazo diplaoma avy amin'ny Oniversiten'i St. Petersburg, tao amin'ny JetBrains Research izy.
Ny fahasarotan'ny kajy amin'ny fitadiavana fiankinan-doha miasa
Ny olana lehibe dia ny fahasarotan'ny kajy. Ny isan'ny fiankinan-doha kely indrindra sy tsy misy dikany dia voafetra amin'ny sanda etsy ambony 
izay 
— isan'ny toetran'ny latabatra. Ny fotoana fiasan'ny algorithm dia tsy miankina amin'ny isan'ny toetra, fa amin'ny isan'ny andalana ihany koa. Tamin'ny taona 90, ny algorithm fikarohana lalàna federaly amin'ny PC desktop mahazatra dia afaka manodina ny angon-drakitra misy toetra hatramin'ny 20 sy andalana an'aliny ao anatin'ny ora maromaro. Ny algorithm maoderina mandeha amin'ny processeur maro-fototra dia mahita ny fiankinan-doha amin'ny angon-drakitra misy toetra an-jatony (hatramin'ny 200) sy andalana an'hetsiny ao anatin'ny fotoana mitovy. Na izany aza, tsy ampy izany: ny fotoana toy izany dia tsy azo ekena ho an'ny ankamaroan'ny fampiharana amin'izao tontolo izao. Noho izany, namolavola fomba fiasa hanafaingana ny algorithm efa misy izahay.
Tetika caching ho an'ny sampanan-dalana
Ao amin'ny tapany voalohany amin'ny asa dia namolavola tetika caching izahay ho an'ny kilasy algorithm izay mampiasa ny fomba fizarazarana. Ny fizarazarana ho an'ny toetra iray dia andiana lisitra, izay misy lisitra tsirairay misy laharan-tsipika mitovy sanda ho an'ny toetra iray. Ny lisitra tsirairay toy izany dia antsoina hoe cluster. Algorithm maoderina maro no mampiasa fizarazarana mba hamaritana raha misy fiankinan-doha na tsia, izany hoe mifikitra amin'ny lemma: Dependency 
natao raha 
. Eto 
fizarazarana no voatondro ary ampiasaina ny hevitra momba ny haben'ny fizarazarana - ny isan'ny cluster ao anatiny. Algorithm izay mampiasa partitions, rehefa voahitsakitsaka ny fiankinan-doha, dia ampio toetra fanampiny amin'ny ilany havia amin'ny fiankinan-doha, ary avy eo dia avereno fikajiana izany, manatanteraka ny fiasan'ny intersection ny partitions. Ity asa ity dia antsoina hoe specialization ao amin'ny lahatsoratra. Saingy nahatsikaritra izahay fa ny fizarazarana ho an'ny fiankinan-doha izay hotazonina ihany aorian'ny fihodinana vitsivitsy amin'ny fanasokajiana dia azo ampiasaina amin'ny fomba mavitrika, izay mety hampihena be ny fotoana fiasan'ny algorithm, satria lafo ny fandidiana.
Noho izany, nanolotra heuristika mifototra amin'ny Shannon Entropy sy Ginny Uncertainty izahay, ary koa ny metric, izay nantsoinay Reverse Entropy. Fanovana kely amin'ny Shannon Entropy izany ary mitombo rehefa mitombo ny maha-tokana ny angon-drakitra. Ny heuristic natolotra dia toy izao manaraka izao:
izany 
- haavon'ny maha-tokana ny fisarahana kajy vao haingana 
ary 
dia ny median'ny ambaratongan'ny maha-tokana ho an'ny toetra tsirairay. Ireo metrika telo voalaza etsy ambony dia nosedraina ho metrika tokana. Azonao atao ihany koa ny manamarika fa misy fanovana roa ao amin'ny heuristic. Ny voalohany dia manondro ny halehiben'ny fizarazarana amin'izao fotoana izao amin'ny lakile voalohany ary ahafahanao mitahiry bebe kokoa ireo fizarazarana izay lavitra ny fanalahidy mety. Ny modifier faharoa dia ahafahanao manara-maso ny fibodoana cache ary noho izany dia mamporisika ny fampidirana partitions bebe kokoa amin'ny cache raha misy toerana malalaka. Ny vahaolana mahomby amin'ity olana ity dia namela anay hanafaingana ny algorithm PYRO amin'ny 10-40%, arakaraka ny angon-drakitra. Tsara ny manamarika fa ny algorithm PYRO no mahomby indrindra amin'ity sehatra ity.
Ao amin'ny sary etsy ambany ianao dia afaka mahita ny vokatry ny fampiharana ny heuristika natolotra raha oharina amin'ny fomba fiasa caching coin-flip fototra. Ny axe X dia logarithmic.
Fomba hafa hitahirizana partitions
Avy eo dia nanolotra fomba hafa hitehirizana partitions izahay. Ny fizarazarana dia andiana cluster, izay samy mitahiry ny isan'ny tuple misy sanda mitovy amin'ny toetra sasany. Mety misy filaharana lava amin'ny isa tuple ireo cluster ireo, ohatra raha misy baiko ny angona ao anaty latabatra. Noho izany, nanolotra tetika famatrarana ho an'ny fitehirizana fizarazarana izahay, izany hoe ny fitahirizana ny soatoavina amin'ny clusters partitions:
$$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$$
Ity fomba ity dia afaka mampihena ny fanjifana fahatsiarovana mandritra ny fiasan'ny TANE algorithm amin'ny 1 ka hatramin'ny 25%. Ny algorithm TANE dia algorithm mahazatra amin'ny fikarohana ny lalàna federaly; Ao anatin'ny fanao dia nofidina ny algorithm TANE, satria mora kokoa ny mampihatra ny fitehirizana elanelam-potoana ao aminy noho ny, ohatra, ao amin'ny PYRO mba hanombanana raha mahomby ny fomba fiasa naroso. Ny vokatra azo dia aseho amin'ny sary etsy ambany. Ny axe X dia logarithmic.
Fihaonambe ADBIS-2019
Araka ny vokatry ny fikarohana dia namoaka lahatsoratra aho tamin'ny Septambra 2019 tamin'ny fihaonambe Eoropeana faha-23 momba ny fandrosoana amin'ny angona sy ny rafitra fampahalalana (ADBIS-2019). Nandritra ny famelabelarana dia nanamarika ny asa i Bernhard Thalheim, olona manan-danja eo amin'ny sehatry ny angon-drakitra. Ny valin'ny fikarohana no fototry ny disertation nataoko tao amin'ny mari-pahaizana maîtrise momba ny matematika sy ny mekanika tao amin'ny Oniversiten'i St. Petersburg State, izay nampiharina tamin'ny algorithm roa tonta ny soso-kevitra (caching sy compression): TANE sy PYRO. Ankoatr'izay, ny valiny dia naneho fa ny fomba fiasa natolotra dia manerana izao rehetra izao, satria amin'ny algorithms roa, miaraka amin'ireo fomba roa ireo, dia nisy fihenam-bidy lehibe tamin'ny fanjifana fahatsiarovana, ary koa ny fihenan'ny fotoana fiasan'ny algorithm.
Source: www.habr.com
