දත්තවල ක්රියාකාරී පරායත්තතා සෙවීම දත්ත විශ්ලේෂණයේ විවිධ ක්ෂේත්‍රවල භාවිතා වේ: දත්ත සමුදා කළමනාකරණය, දත්ත පිරිසිදු කිරීම, දත්ත සමුදා ප්‍රතිලෝම ඉංජිනේරු සහ දත්ත ගවේෂණය. අපි දැනටමත් යැපීම් ගැන ප්‍රකාශ කර ඇත Anastasia Birillo සහ Nikita Bobrov. මෙවර, මෙම වසරේ පරිගණක විද්‍යා මධ්‍යස්ථානයේ උපාධිධාරිනියක වන ඇනස්ටේෂියා, එම මධ්‍යස්ථානයේදී ඇය ආරක්ෂා කළ පර්යේෂණ කාර්යයේ කොටසක් ලෙස මෙම කාර්යයේ වර්ධනය බෙදා ගනී.
කාර්යය තේරීම
CS මධ්‍යස්ථානයේ අධ්‍යයනය කරන අතරතුර, මම දත්ත සමුදායන් ගැඹුරින් අධ්‍යයනය කිරීමට පටන් ගතිමි, එනම් ක්රියාකාරී සහ වෙනස් පරායත්තතා සෙවීම. මෙම මාතෘකාව විශ්ව විද්‍යාලයේ මගේ පාඨමාලා මාතෘකාවට සම්බන්ධ වූ අතර, එම පාඨමාලාවේ වැඩ කරන අතරතුර, දත්ත සමුදායේ විවිධ පරායත්තතා පිළිබඳ ලිපි කියවීමට පටන් ගතිමි. මම මෙම ප්‍රදේශය පිළිබඳ සමාලෝචනයක් ලිව්වෙමි - මගේ පළමු එක ඉංග්‍රීසියෙන් එය SEIM-2017 සමුළුවට ඉදිරිපත් කළා. සියල්ලට පසු ඇයව පිළිගෙන ඇති බව දැනගත් විට මම ඉතා සතුටට පත් වූ අතර මාතෘකාව ගැඹුරින් සොයා බැලීමට තීරණය කළෙමි. සංකල්පයම අලුත් නොවේ - එය 90 දශකයේ නැවත භාවිතා කිරීමට පටන් ගත් නමුත් දැන් පවා එය බොහෝ ප්රදේශ වල භාවිතා වේ.
මධ්‍යස්ථානයේ මගේ දෙවන අධ්‍යයන වාරය තුළදී, මම ක්රියාකාරී පරායත්තතා සොයා ගැනීම සඳහා ඇල්ගොරිතම වැඩිදියුණු කිරීම සඳහා පර්යේෂණ ව්‍යාපෘතියක් ආරම්භ කළෙමි. ඇය JetBrains Research හි ශාන්ත පීටර්ස්බර්ග් රාජ්‍ය විශ්ව විද්‍යාලයේ උපාධිධාරී ශිෂ්‍යාවක් වන Nikita Bobrov සමඟ එක්ව එය මත වැඩ කළාය.
ක්රියාකාරී පරායත්තතා සෙවීමේ පරිගණක සංකීර්ණත්වය
ප්රධාන ගැටළුව වන්නේ ගණනය කිරීමේ සංකීර්ණත්වයයි. හැකි අවම සහ සුළු නොවන පරායත්තතා ගණන ඉහත අගයෙන් සීමා වේ කොහෙද - වගු ගුණාංග ගණන. ඇල්ගොරිතම වල මෙහෙයුම් කාලය රඳා පවතින්නේ ගුණාංග ගණන මත පමණක් නොව, පේළි ගණන මත ය. 90 දශකයේ දී, සාමාන්‍ය ඩෙස්ක්ටොප් පරිගණකයක ෆෙඩරල් නීති සෙවුම් ඇල්ගොරිතම මගින් 20 attributes දක්වා සහ පේළි දස දහස් ගණනක් අඩංගු දත්ත කට්ටල පැය කිහිපයක් දක්වා සැකසීමට හැකි විය. බහු-core ප්‍රොසෙසර මත ක්‍රියාත්මක වන නවීන ඇල්ගොරිතම මගින් උපලක්ෂණ සිය ගණනකින් (200 දක්වා) සහ පේළි සිය දහස් ගණනකින් සමන්විත දත්ත කට්ටල සඳහා පරායත්තතා හඳුනා ගනී. කෙසේ වෙතත්, මෙය ප්රමාණවත් නොවේ: බොහෝ සැබෑ ලෝකයේ යෙදුම් සඳහා එවැනි කාලයක් පිළිගත නොහැකිය. එබැවින්, පවතින ඇල්ගොරිතම වේගවත් කිරීම සඳහා අපි ප්රවේශයන් සකස් කළෙමු.
කොටස් මංසන්ධි සඳහා හැඹිලි යෝජනා ක්රම
කාර්යයේ පළමු කොටසේදී, අපි කොටස් ඡේදනය කිරීමේ ක්රමය භාවිතා කරන ඇල්ගොරිතම පන්තියක් සඳහා හැඹිලි යෝජනා ක්රම සකස් කළෙමු. ගුණාංගයක් සඳහා වන කොටස යනු ලැයිස්තු සමූහයකි, එහිදී එක් එක් ලැයිස්තුවේ දී ඇති ගුණාංගයක් සඳහා එකම අගයන් සහිත රේඛා අංක අඩංගු වේ. එවැනි සෑම ලැයිස්තුවක්ම පොකුරක් ලෙස හැඳින්වේ. බොහෝ නවීන ඇල්ගොරිතම පරායත්තතාවයක් පවත්වා ගෙන යනවාද නැද්ද යන්න තීරණය කිරීමට කොටස් භාවිතා කරයි, එනම්, ඒවා lemma: යැපීම පිළිපදින්නේය. නම් පවත්වන ලදී . මෙතන කොටසක් නම් කර ඇති අතර කොටස් ප්‍රමාණය යන සංකල්පය භාවිතා වේ - එහි ඇති පොකුරු ගණන. කොටස් භාවිතා කරන ඇල්ගොරිතම, පරායත්තතාවය උල්ලංඝනය වන විට, පරායත්තතාවයේ වම් පැත්තට අමතර ගුණාංග එකතු කරන්න, ඉන්පසු එය නැවත ගණනය කරන්න, කොටස්වල ඡේදනය කිරීමේ මෙහෙයුම සිදු කරයි. මෙම මෙහෙයුම ලිපිවල විශේෂීකරණය ලෙස හැඳින්වේ. නමුත් ඡේදනය කිරීමේ ක්‍රියාවලිය මිල අධික බැවින්, විශේෂීකරණය වට කිහිපයකින් පසුව පමණක් රඳවා තබා ගන්නා පරායත්තතා සඳහා වන කොටස් සක්‍රියව නැවත භාවිතා කළ හැකි බව අපි දුටුවෙමු.
එබැවින්, අපි ෂැනන් එන්ට්‍රොපි සහ ජින්නි අවිනිශ්චිතතාවය මත පදනම් වූ හූරිස්ටික් එකක් මෙන්ම ප්‍රතිලෝම එන්ට්‍රොපි ලෙස හැඳින්වූ අපගේ මෙට්‍රික් එකක් යෝජනා කළෙමු. එය Shannon Entropy හි සුළු වෙනස් කිරීමක් වන අතර දත්ත කට්ටලයේ සුවිශේෂත්වය වැඩි වන විට වැඩි වේ. යෝජිත හූරිස්ටික් පහත පරිදි වේ:
එය - මෑතකදී ගණනය කරන ලද කොටසෙහි සුවිශේෂත්වය පිළිබඳ උපාධිය හා පුද්ගල ගුණාංග සඳහා සුවිශේෂත්වයේ අංශක මධ්යන්ය වේ. ඉහත විස්තර කර ඇති ප්‍රමිතික තුනම සුවිශේෂතා මෙට්‍රික් එකක් ලෙස පරීක්‍ෂා කරන ලදී. හූරිස්ටික් තුළ නවීකරණ දෙකක් ඇති බව ද ඔබට දැක ගත හැකිය. පළමුවැන්න වත්මන් කොටස ප්‍රාථමික යතුරට කෙතරම් සමීපද යන්න පෙන්වා දෙන අතර විභව යතුරට වඩා දුරින් ඇති එම කොටස් බොහෝ දුරට හැඹිලිගත කිරීමට ඔබට ඉඩ සලසයි. දෙවන විකරණකාරකය ඔබට හැඹිලි පදිංචිය නිරීක්ෂණය කිරීමට ඉඩ ලබා දෙන අතර එමඟින් නිදහස් ඉඩ තිබේ නම් හැඹිලියට තවත් කොටස් එකතු කිරීම දිරිමත් කරයි. මෙම ගැටලුවේ සාර්ථක විසඳුම දත්ත කට්ටලය මත පදනම්ව PYRO ඇල්ගොරිතම 10-40% කින් වේගවත් කිරීමට අපට ඉඩ සලසයි. PYRO ඇල්ගොරිතම මෙම ප්රදේශයේ වඩාත්ම සාර්ථක බව සඳහන් කිරීම වටී.
පහත රූපයේ ඔබට මූලික coin-flip caching ප්‍රවේශයකට සාපේක්ෂව යෝජිත හියුරිස්ටික් යෙදීමේ ප්රතිඵල දැකිය හැක. X අක්ෂය ලඝුගණක වේ.
කොටස් ගබඩා කිරීම සඳහා විකල්ප ක්රමයක්
අපි පසුව කොටස් ගබඩා කිරීම සඳහා විකල්ප ක්රමයක් යෝජනා කළා. කොටස් යනු පොකුරු සමූහයකි, ඒ සෑම එකක්ම ඇතැම් ගුණාංග සඳහා සමාන අගයන් සහිත ටියුපල් සංඛ්‍යා ගබඩා කරයි. මෙම පොකුරු වල ටියුපල් සංඛ්‍යා වල දිගු අනුපිළිවෙලක් අඩංගු විය හැක, උදාහරණයක් ලෙස වගුවක ඇති දත්ත අනුපිළිවෙලක් නම්. එබැවින්, අපි කොටස් ගබඩා කිරීම සඳහා සම්පීඩන ක්රමයක් යෝජනා කළෙමු, එනම් කොටස් පොකුරු වල අගයන් පරතරය ගබඩා කිරීම:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{පළමු අන්තරය}, underbrace{7, 8}_{Second interval}, 10}}\ downarrow{ Compression} \ pi(X) = {{යටි වරහන{$, 1, 5}_{පළමු~අන්තරය}, යටි වරහන{7, 8}_{දෙවන~ පරතරය}, 10}}$$දර්ශණය$$
1 සිට 25% දක්වා TANE ඇල්ගොරිතමයේ ක්රියාකාරිත්වය තුළ මතක පරිභෝජනය අඩු කිරීමට මෙම ක්රමය සමත් විය. TANE ඇල්ගොරිතම යනු ෆෙඩරල් නීති සෙවීම සඳහා සම්භාව්‍ය ඇල්ගොරිතමයකි; එය එහි වැඩ අතරතුර කොටස් භාවිතා කරයි. භාවිතයේ කොටසක් ලෙස, TANE ඇල්ගොරිතම තෝරා ගන්නා ලදී, මන්ද යෝජිත ප්‍රවේශය ක්‍රියාත්මක වේද යන්න තක්සේරු කිරීම සඳහා, උදාහරණයක් ලෙස, PYRO ට වඩා එහි කාල පරතරය ක්‍රියාත්මක කිරීම පහසු වූ බැවිනි. ලබාගත් ප්රතිඵල පහත රූපයේ දැක්වේ. X අක්ෂය ලඝුගණක වේ.
සම්මන්ත්‍රණය ADBIS-2019
පර්යේෂණයේ ප්රතිඵල මත පදනම්ව, 2019 සැප්තැම්බර් මාසයේදී මම ලිපියක් පළ කළෙමි දත්ත සමුදායන් සහ තොරතුරු පද්ධතිවල දියුණුව පිළිබඳ 23 වැනි යුරෝපීය සමුළුවේදී (ADBIS-2019). ඉදිරිපත් කිරීමේදී, දත්ත සමුදා ක්ෂේත්‍රයේ සැලකිය යුතු පුද්ගලයෙකු වන බර්න්හාඩ් තල්හයිම් විසින් මෙම කාර්යය සටහන් කරන ලදී. පර්යේෂණ ප්රතිඵල ශාන්ත පීටර්ස්බර්ග් ප්‍රාන්ත විශ්වවිද්‍යාලයේ ගණිතය සහ යාන්ත්‍ර විද්‍යාව පිළිබඳ ශාස්ත්‍රපති උපාධියේ මගේ නිබන්ධනයේ පදනම වූ අතර, එම කාලය තුළ යෝජිත ප්රවේශයන් (හැඹිලි සහ සම්පීඩනය) දෙකම ඇල්ගොරිතම දෙකෙහිම ක්‍රියාත්මක කරන ලදී: TANE සහ PYRO. එපමනක් නොව, ප්රතිඵල පෙන්නුම් කළේ ඇල්ගොරිතම දෙකෙහිම, ප්රවේශයන් දෙකම සමඟ, මතක පරිභෝජනයෙහි සැලකිය යුතු අඩුවීමක් මෙන්ම ඇල්ගොරිතමවල ක්රියාකාරී කාලයෙහි සැලකිය යුතු අඩුවීමක් දක්නට ලැබෙන බැවින්, යෝජිත ප්රවේශයන් විශ්වීය බවයි.
මූලාශ්රය: www.habr.com