A na-eji ịchọta ndabere ọrụ na data na mpaghara dị iche iche nke nyocha data: njikwa nchekwa data, ihicha data, nchekwa data ntụgharị injinia na nyocha data. Anyị ebipụtalarị banyere ịdabere n'onwe ha Anastasia Birillo na Nikita Bobrov. N'oge a, Anastasia, onye gụsịrị akwụkwọ na Science Science Center nke afọ a, na-ekerịta mmepe nke ọrụ a dịka akụkụ nke ọrụ nyocha ọ gbachitere na etiti ahụ.
Nhọrọ ọrụ
Mgbe m na-amụ ihe na CS center, m malitere ịmụ ọdụ data na omimi, ya bụ, ịchọ ọrụ na ịdabere na ọdịiche. Isiokwu a metụtara isiokwu nke ọrụ nkuzi m na mahadum, yabụ mgbe m na-arụ ọrụ nkuzi, amalitere m ịgụ akụkọ gbasara ndabere dị iche iche na ọdụ data. Edere m nyocha nke mpaghara a - otu n'ime nke mbụ m na Bekee ma nyefee ya na ogbako SEIM-2017. Enwere m nnọọ obi ụtọ mgbe m chọpụtara na a nabatara ya ka emechara, ma kpebie ịbanye n'ime isiokwu ahụ. Echiche ahụ n'onwe ya abụghị ihe ọhụrụ - ọ malitere iji azụ azụ na 90s, ma ọbụna ugbu a, a na-eji ya n'ọtụtụ ebe.
N'ime semester nke abụọ m na etiti, amalitere m ọrụ nyocha iji melite algọridim maka ịchọta ndabere ọrụ. Ọ na-arụkọ ọrụ na ya na St. Petersburg State University gụsịrị akwụkwọ na-amụrụ Nikita Bobrov na JetBrains Research.
Mgbakọ mgbagwoju anya nke ịchọ ndabere ọrụ
Nsogbu bụ isi bụ mgbagwoju anya mgbakọ. Ọnụọgụ nke ndabere pere mpe na nke na-abụghị nke pere mpe nwere ike ịnwe oke site na uru ahụ 
ebe 
- ọnụ ọgụgụ nke tebụl àgwà. Oge ọrụ nke algọridim na-adabere ọ bụghị nanị na ọnụ ọgụgụ nke àgwà, kamakwa na ọnụ ọgụgụ nke ahịrị. N'ime 90s, algọridim nchọ iwu gọọmentị etiti na PC desktọpụ oge niile nwere ike hazie nhazi data nwere ihe ruru njirimara 20 na iri puku kwuru iri puku ahịrị n'ime ruo ọtụtụ awa. Algọridim ọgbara ọhụrụ na-agba ọsọ na ọtụtụ isi nhazi na-achọpụta ndabere maka nhazi data nke nwere ọtụtụ narị njirimara (ruo 200) na narị puku ahịrị n'otu oge. Otú ọ dị, nke a ezughị: oge dị otú ahụ adịghị anabata maka ọtụtụ ngwa ngwa ụwa. Ya mere, anyị mepụtara ụzọ iji mee ka algọridim dị ugbu a dị ngwa.
Atụmatụ caching maka nkwụsị nkebi
N'akụkụ mbụ nke ọrụ ahụ, anyị mepụtara atụmatụ caching maka otu klas nke algọridim na-eji usoro nkwụsị nkebi. Nkebi maka njirimara bụ ndepụta nke ndepụta, ebe ndepụta ọ bụla nwere nọmba ahịrị nwere otu ụkpụrụ maka àgwà enyere. Ndepụta nke ọ bụla dị otú ahụ ka a na-akpọ ụyọkọ. Ọtụtụ algọridim ọgbara ọhụrụ na-eji akụkụ iji chọpụta ma ọ bụ ịdabere na ya ma ọ bụ na ejighị ya, ya bụ, ha na-agbaso lemma: Dependency. 
ejidere ma ọ bụrụ 
. Ebe a 
A na-ahọpụta nkebi ma jiri echiche nke oke nkebi mee ihe - ọnụ ọgụgụ nke ụyọkọ dị na ya. Algorithms na-eji partitions, mgbe ndabere na-emebi emebi, tinye ndị ọzọ àgwà n'akụkụ aka ekpe nke ndabere, wee recalculate ya, na-arụ ọrụ nke intersection nke partitions. A na-akpọ ọrụ a ọkachamara na isiokwu. Ma anyị chọpụtara na partitions maka adabere na a ga-ejigide mgbe a ole na ole agba nke iche iche nwere ike na-arụsi ọrụ ike reused, nke nwere ike budata ibelata ọsọ oge nke algọridim, ebe ọ bụ na intersection ọrụ dị oke ọnụ.
Ya mere, anyị tụrụ aro ka heuristic dabere na Shannon Entropy na Ginny Uncertainty, yana metric anyị, nke anyị kpọrọ Reverse Entropy. Ọ bụ ntakịrị mgbanwe nke Shannon Entropy ma na-abawanye ka ihe pụrụ iche nke nhazi data na-abawanye. Usoro heuristic a tụrụ aro bụ nke a:
ọ bụ 
- ogo nke iche nke nkebi gbakọrọ na nso nso a 
na 
bụ etiti nke ogo nke iche maka njirimara onye ọ bụla. A nwalere metrik atọ niile akọwara n'elu dị ka metric pụrụ iche. Ị nwekwara ike chọpụta na e nwere ihe abụọ modifiers na heuristic. Nke mbụ na-egosi ka nso nkebi dị ugbu a si dị nso na isi igodo ma na-enye gị ohere ịchekwaa oke akụkụ ndị ahụ dị anya site na igodo nwere ike. Ihe ngbanwe nke abụọ na-enye gị ohere ileba anya n'ime oghere ma si otú a na-akwado ịgbakwunye akụkụ ndị ọzọ na cache ma ọ bụrụ na ohere efu dị. Ngwọta nke ọma nke nsogbu a mere ka anyị mee ngwa ngwa PYRO algọridim site na 10-40%, dabere na dataset. Ọ dị mma ịmara na algọridim nke PYRO bụ ihe ịga nke ọma na mpaghara a.
N'ọnụọgụgụ dị n'okpuru, ị nwere ike ịhụ nsonaazụ nke itinye usoro heuristic a tụrụ aro ma e jiri ya tụnyere usoro nchekwa mkpụrụ ego na-atụgharị. Axis X bụ logarithmic.
Ụzọ ọzọ iji chekwaa nkebi
Anyị tụpụtara ụzọ ọzọ iji chekwaa nkebi. Nkebi bụ ụyọkọ ụyọkọ, nke ọ bụla n'ime ha na-echekwa ọnụọgụ nke tuples nwere ụkpụrụ otu maka ụfọdụ àgwà. Ụyọkọ ndị a nwere ike ịnwe ogologo usoro nke nọmba tuple, dịka ọmụmaatụ ma ọ bụrụ na akwadoro data dị na tebụl. Ya mere, anyị tụrụ aro mkpakọ atụmatụ maka ịchekwa partitions, ya bụ etiti oge nchekwa ụkpụrụ na ụyọkọ nke partitions:
$$ ngosi$$pi(X) = {{n'okpuru ihe nkwado{1, 2, 3, 4, 5}_{Nke mbụ}, n'okpuru brace{7, 8}_{n'oge nke abụọ}, 10}} \ mgbaka ala { mkpakọ} \ pi(X) = {{n'okpuru ihe nkwado{$, 1, 5}_{Mbụ~n'etiti}, n'okpuru nkwado{7, 8}_{Second~interval}, 10}}$$ ngosi$$
Usoro a nwere ike ibelata oriri ebe nchekwa n'oge ọrụ nke TANE algọridim site na 1 ruo 25%. TANE algọridim bụ ihe kpochapụwo algọridim maka ịchọ iwu gọọmenti etiti ọ na-eji nkebi n'oge ọrụ ya. Dị ka akụkụ nke omume ahụ, a họọrọ TANE algọridim, ebe ọ bụ na ọ dị mfe iji mejuputa nchekwa oge na ya karịa, dịka ọmụmaatụ, na PYRO iji nyochaa ma usoro a tụrụ aro na-arụ ọrụ. E gosipụtara nsonaazụ enwetara na foto dị n'okpuru. Axis X bụ logarithmic.
Nzukọ ADBIS-2019
Dabere na nsonaazụ nyocha ahụ, na Septemba 2019 m bipụtara otu akụkọ na 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). N'oge ngosi ahụ, Bernhard Thalheim, onye dị ịrịba ama na ngalaba nke ọdụ data, kwuru ọrụ ahụ. Nsonaazụ nyocha ahụ hiwere ntọala nke akwụkwọ m na nzere nna ukwu na mgbakọ na mwepụ na injinia na Mahadum St. Ọzọkwa, nsonaazụ gosipụtara na ụzọ ndị a tụrụ aro bụ nke zuru ụwa ọnụ, ebe ọ bụ na algọridim abụọ ahụ, na ụzọ abụọ ahụ, a hụrụ mbelata dị ukwuu na oriri ebe nchekwa, yana mbelata dị ukwuu na oge ọrụ nke algọridim.
isi: www.habr.com
