ស្វែងរកភាពអាស្រ័យមុខងារក្នុងមូលដ្ឋានទិន្នន័យប្រកបដោយប្រសិទ្ធភាព

ការស្វែងរកមុខងារអាស្រ័យនៅក្នុងទិន្នន័យត្រូវបានប្រើក្នុងផ្នែកផ្សេងៗនៃការវិភាគទិន្នន័យ៖ ការគ្រប់គ្រងមូលដ្ឋានទិន្នន័យ ការសម្អាតទិន្នន័យ វិស្វកម្មបញ្ច្រាស់មូលដ្ឋានទិន្នន័យ និងការរុករកទិន្នន័យ។ យើង​បាន​ផ្សព្វផ្សាយ​រួច​ហើយ​អំពី​ភាព​អាស្រ័យ​ខ្លួន​ឯង អត្ថបទ Anastasia Birillo និង Nikita Bobrov ។ លើកនេះ នាង Anastasia ដែលជានិស្សិតបញ្ចប់ការសិក្សានៅមជ្ឈមណ្ឌលវិទ្យាសាស្ត្រកុំព្យូទ័រនៅឆ្នាំនេះ ចែករំលែកការអភិវឌ្ឍន៍ការងារនេះ ជាផ្នែកនៃការងារស្រាវជ្រាវដែលនាងការពារនៅមជ្ឈមណ្ឌលនេះ។

ការជ្រើសរើសភារកិច្ច

ខណៈពេលដែលកំពុងសិក្សានៅមជ្ឈមណ្ឌល CS ខ្ញុំបានចាប់ផ្តើមសិក្សាមូលដ្ឋានទិន្នន័យឱ្យស៊ីជម្រៅ ពោលគឺការស្វែងរកមុខងារ និងភាពខុសគ្នាអាស្រ័យលើភាពអាស្រ័យ។ ប្រធានបទនេះគឺទាក់ទងទៅនឹងប្រធានបទនៃវគ្គសិក្សារបស់ខ្ញុំនៅសកលវិទ្យាល័យ ដូច្នេះនៅពេលធ្វើការលើវគ្គសិក្សានេះ ខ្ញុំបានចាប់ផ្តើមអានអត្ថបទអំពីភាពអាស្រ័យផ្សេងៗនៅក្នុងមូលដ្ឋានទិន្នន័យ។ ខ្ញុំបានសរសេរការពិនិត្យឡើងវិញអំពីតំបន់នេះ - ទីមួយរបស់ខ្ញុំ អត្ថបទ ជាភាសាអង់គ្លេស ហើយបញ្ជូនវាទៅសន្និសីទ SEIM-2017 ។ ខ្ញុំសប្បាយចិត្តខ្លាំងណាស់នៅពេលដែលខ្ញុំដឹងថានាងត្រូវបានទទួលយក ហើយសម្រេចចិត្តស្វែងយល់ឱ្យកាន់តែស៊ីជម្រៅទៅក្នុងប្រធានបទ។ គំនិតខ្លួនវាមិនមែនជារឿងថ្មីទេ - វាបានចាប់ផ្តើមប្រើឡើងវិញនៅក្នុងទសវត្សរ៍ទី 90 ប៉ុន្តែសូម្បីតែឥឡូវនេះវាត្រូវបានគេប្រើនៅក្នុងតំបន់ជាច្រើន។

ក្នុងអំឡុងពេលឆមាសទីពីររបស់ខ្ញុំនៅមជ្ឈមណ្ឌល ខ្ញុំបានចាប់ផ្តើមគម្រោងស្រាវជ្រាវមួយដើម្បីកែលម្អក្បួនដោះស្រាយសម្រាប់ការស្វែងរកភាពអាស្រ័យមុខងារ។ នាងបានធ្វើការលើវារួមគ្នាជាមួយនិស្សិតបញ្ចប់ការសិក្សារបស់សាកលវិទ្យាល័យ St. Petersburg State Nikita Bobrov នៅក្រុមហ៊ុន JetBrains Research ។

ភាពស្មុគស្មាញនៃការគណនានៃការស្វែងរកភាពអាស្រ័យមុខងារ

បញ្ហាចម្បងគឺភាពស្មុគស្មាញនៃការគណនា។ ចំនួននៃភាពអាស្រ័យតិចតួចបំផុត និងមិនសំខាន់ត្រូវបានកំណត់ខាងលើដោយតម្លៃ ដែលជាកន្លែង - ចំនួននៃគុណលក្ខណៈតារាង។ ពេលវេលាប្រតិបត្តិការនៃក្បួនដោះស្រាយមិនត្រឹមតែអាស្រ័យទៅលើចំនួននៃគុណលក្ខណៈប៉ុណ្ណោះទេ ប៉ុន្តែក៏អាស្រ័យលើចំនួនជួរដេកផងដែរ។ ក្នុងទសវត្សរ៍ទី 90 ក្បួនដោះស្រាយការស្វែងរកច្បាប់សហព័ន្ធនៅលើកុំព្យូទ័រលើតុធម្មតាអាចដំណើរការសំណុំទិន្នន័យដែលមានគុណលក្ខណៈរហូតដល់ 20 និងជួររាប់ម៉ឺនជួរក្នុងរយៈពេលច្រើនម៉ោង។ ក្បួនដោះស្រាយទំនើបដែលដំណើរការលើប្រព័ន្ធដំណើរការពហុស្នូលរកឃើញភាពអាស្រ័យសម្រាប់សំណុំទិន្នន័យដែលមានគុណលក្ខណៈរាប់រយ (រហូតដល់ 200) និងរាប់រយរាប់ពាន់ជួរក្នុងរយៈពេលប្រហាក់ប្រហែលគ្នា។ ទោះយ៉ាងណាក៏ដោយ នេះមិនគ្រប់គ្រាន់ទេ៖ ពេលវេលាបែបនេះមិនអាចទទួលយកបានសម្រាប់កម្មវិធីក្នុងពិភពពិតភាគច្រើនទេ។ ដូច្នេះហើយ យើងបានបង្កើតវិធីសាស្រ្តដើម្បីបង្កើនល្បឿននៃក្បួនដោះស្រាយដែលមានស្រាប់។

គ្រោងឃ្លាំងសម្ងាត់សម្រាប់ប្រសព្វភាគថាស

នៅក្នុងផ្នែកដំបូងនៃការងារ យើងបានបង្កើតគម្រោងឃ្លាំងសម្ងាត់សម្រាប់ថ្នាក់នៃក្បួនដោះស្រាយដែលប្រើវិធីសាស្ត្រប្រសព្វភាគថាស។ ភាគថាសសម្រាប់គុណលក្ខណៈគឺជាសំណុំនៃបញ្ជី ដែលបញ្ជីនីមួយៗមានលេខបន្ទាត់ដែលមានតម្លៃដូចគ្នាសម្រាប់គុណលក្ខណៈដែលបានផ្តល់ឱ្យ។ បញ្ជីបែបនេះនីមួយៗត្រូវបានគេហៅថាចង្កោម។ ក្បួនដោះស្រាយសម័យទំនើបជាច្រើនប្រើភាគថាសដើម្បីកំណត់ថាតើភាពអាស្រ័យមួយត្រូវបានប្រារព្ធឡើងឬអត់ ពោលគឺពួកគេប្រកាន់ខ្ជាប់នូវលេម៉ា: ភាពអាស្រ័យ បានប្រារព្ធឡើងប្រសិនបើ . នៅទីនេះ ភាគថាសត្រូវបានកំណត់ហើយគំនិតនៃទំហំភាគថាសត្រូវបានប្រើ - ចំនួននៃចង្កោមនៅក្នុងវា។ ក្បួនដោះស្រាយដែលប្រើភាគថាស នៅពេលដែលភាពអាស្រ័យត្រូវបានបំពាន បន្ថែមគុណលក្ខណៈបន្ថែមទៅផ្នែកខាងឆ្វេងនៃភាពអាស្រ័យ ហើយបន្ទាប់មកគណនាវាឡើងវិញ ដោយអនុវត្តប្រតិបត្តិការប្រសព្វនៃភាគថាស។ ប្រតិបត្តិការនេះត្រូវបានគេហៅថាឯកទេសក្នុងអត្ថបទ។ ប៉ុន្តែយើងសង្កេតឃើញថា ភាគថាសសម្រាប់ភាពអាស្រ័យដែលនឹងត្រូវបានរក្សាទុកបន្ទាប់ពីជំនាញឯកទេសពីរបីជុំអាចប្រើឡើងវិញយ៉ាងសកម្ម ដែលអាចកាត់បន្ថយពេលវេលាដំណើរការនៃក្បួនដោះស្រាយបានយ៉ាងច្រើន ដោយសារប្រតិបត្តិការប្រសព្វមានតម្លៃថ្លៃ។

ហេតុដូច្នេះហើយ យើងបានស្នើឡើងនូវទ្រឹស្ដីមួយដោយផ្អែកលើ Shannon Entropy និង Ginny Uncertainty ក៏ដូចជាម៉ែត្ររបស់យើងដែលយើងហៅថា Reverse Entropy ។ វាគឺជាការកែប្រែបន្តិចបន្តួចនៃ Shannon Entropy ហើយកើនឡើងនៅពេលដែលលក្ខណៈពិសេសនៃសំណុំទិន្នន័យកើនឡើង។ ទ្រឹស្តីបទដែលបានស្នើឡើងមានដូចខាងក្រោម៖

វាគឺជាការ - កម្រិតនៃភាពប្លែកនៃភាគថាសដែលបានគណនាថ្មីៗនេះ និង គឺជាកម្រិតមធ្យមនៃកម្រិតនៃភាពប្លែកសម្រាប់លក្ខណៈបុគ្គល។ រង្វាស់ទាំងបីដែលបានពិពណ៌នាខាងលើត្រូវបានសាកល្បងជាម៉ែត្រឯកតា។ អ្នក​ក៏​អាច​សម្គាល់​ឃើញ​ថា​មាន​ការ​កែប្រែ​ពីរ​នៅ​ក្នុង​ការ​ស្រាវជ្រាវ​។ ទីមួយបង្ហាញពីរបៀបបិទភាគថាសបច្ចុប្បន្នទៅនឹងកូនសោចម្បង ហើយអនុញ្ញាតឱ្យអ្នករក្សាទុកក្នុងទំហំធំជាងនេះ ភាគថាសទាំងនោះដែលនៅឆ្ងាយពីសោសក្តានុពល។ កម្មវិធីកែប្រែទីពីរអនុញ្ញាតឱ្យអ្នកត្រួតពិនិត្យការកាន់កាប់ឃ្លាំងសម្ងាត់ ហើយដោយហេតុនេះលើកទឹកចិត្តឱ្យបន្ថែមភាគថាសបន្ថែមទៀតទៅក្នុងឃ្លាំងសម្ងាត់ ប្រសិនបើទំហំទំនេរមាន។ ដំណោះស្រាយជោគជ័យនៃបញ្ហានេះបានអនុញ្ញាតឱ្យយើងបង្កើនល្បឿនក្បួនដោះស្រាយ PYRO ដោយ 10-40% អាស្រ័យលើសំណុំទិន្នន័យ។ គួរកត់សម្គាល់ថាក្បួនដោះស្រាយ PYRO គឺជោគជ័យបំផុតនៅក្នុងតំបន់នេះ។

នៅក្នុងរូបភាពខាងក្រោម អ្នកអាចមើលឃើញលទ្ធផលនៃការអនុវត្តការស្ទង់មតិដែលបានស្នើឡើងបើប្រៀបធៀបទៅនឹងវិធីសាស្រ្តឃ្លាំងសម្ងាត់កាក់ត្រឡប់ជាមូលដ្ឋាន។ អ័ក្ស X គឺជាលោការីត។

វិធីជំនួសដើម្បីរក្សាទុកភាគថាស

បន្ទាប់​មក​យើង​បាន​ស្នើ​ឱ្យ​មាន​វិធី​ជំនួស​ដើម្បី​រក្សា​ទុក​ភាគ​ថា​ស​។ ភាគថាសគឺជាសំណុំនៃចង្កោម ដែលនីមួយៗរក្សាទុកចំនួននៃ tuples ជាមួយនឹងតម្លៃដូចគ្នាបេះបិទសម្រាប់គុណលក្ខណៈជាក់លាក់។ ចង្កោមទាំងនេះអាចមានលំដាប់វែងនៃលេខ tuple ឧទាហរណ៍ប្រសិនបើទិន្នន័យក្នុងតារាងត្រូវបានតម្រៀប។ ដូច្នេះ យើង​បាន​ស្នើ​ឡើង​នូវ​គ្រោងការណ៍​បង្ហាប់​មួយ​សម្រាប់​ការ​រក្សា​ទុក​ភាគ​ថា​ស​គឺ​ការ​ផ្ទុក​ចន្លោះ​ពេល​នៃ​តម្លៃ​ក្នុង​ចង្កោម​ភាគ​ថា​សៈ

$$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$$

វិធីសាស្រ្តនេះអាចកាត់បន្ថយការប្រើប្រាស់អង្គចងចាំក្នុងអំឡុងពេលប្រតិបត្តិការនៃក្បួនដោះស្រាយ TANE ពី 1 ទៅ 25% ។ ក្បួនដោះស្រាយ TANE គឺជាក្បួនដោះស្រាយបុរាណសម្រាប់ការស្វែងរកច្បាប់សហព័ន្ធ ដែលវាប្រើភាគថាសក្នុងអំឡុងពេលការងាររបស់វា។ ជាផ្នែកមួយនៃការអនុវត្ត ក្បួនដោះស្រាយ TANE ត្រូវបានជ្រើសរើស ដោយសារវាកាន់តែងាយស្រួលក្នុងការអនុវត្តការផ្ទុកចន្លោះពេលនៅក្នុងវាជាងឧទាហរណ៍នៅក្នុង PYRO ដើម្បីវាយតម្លៃថាតើវិធីសាស្រ្តដែលបានស្នើឡើងដំណើរការឬអត់។ លទ្ធផលដែលទទួលបានត្រូវបានបង្ហាញក្នុងរូបភាពខាងក្រោម។ អ័ក្ស X គឺជាលោការីត។

សន្និសីទ ADBIS-2019

ដោយផ្អែកលើលទ្ធផលនៃការស្រាវជ្រាវនៅក្នុងខែកញ្ញា 2019 ខ្ញុំបានបោះពុម្ពអត្ថបទមួយ។ Smart Caching សម្រាប់ការរកឃើញមុខងារពឹងផ្អែកដែលមានប្រសិទ្ធភាព នៅសន្និសីទអឺរ៉ុបលើកទី 23 ស្តីពីភាពជឿនលឿនក្នុងមូលដ្ឋានទិន្នន័យ និងប្រព័ន្ធព័ត៌មាន (ADBIS-2019)។ ក្នុងអំឡុងពេលនៃការធ្វើបទបង្ហាញ ការងារនេះត្រូវបានកត់សម្គាល់ដោយលោក Bernhard Thalheim ដែលជាមនុស្សសំខាន់ក្នុងវិស័យមូលដ្ឋានទិន្នន័យ។ លទ្ធផលស្រាវជ្រាវបានបង្កើតមូលដ្ឋាននៃនិក្ខេបបទរបស់ខ្ញុំនៅថ្នាក់អនុបណ្ឌិតផ្នែកគណិតវិទ្យា និងមេកានិកនៅសាកលវិទ្យាល័យ St. Petersburg State ក្នុងអំឡុងពេលដែលវិធីសាស្រ្តទាំងពីរដែលបានស្នើឡើង (ឃ្លាំងសម្ងាត់ និងការបង្ហាប់) ត្រូវបានអនុវត្តនៅក្នុងក្បួនដោះស្រាយទាំងពីរ៖ TANE និង PYRO ។ លើសពីនេះទៅទៀត លទ្ធផលបានបង្ហាញថា វិធីសាស្រ្តដែលបានស្នើឡើងគឺមានលក្ខណៈជាសកល ដោយហេតុថានៅលើក្បួនដោះស្រាយទាំងពីរ ជាមួយនឹងវិធីសាស្រ្តទាំងពីរ ការថយចុះគួរឱ្យកត់សម្គាល់នៃការប្រើប្រាស់អង្គចងចាំត្រូវបានគេសង្កេតឃើញ ក៏ដូចជាការថយចុះគួរឱ្យកត់សម្គាល់នៃពេលវេលាប្រតិបត្តិការនៃក្បួនដោះស្រាយ។

ប្រភព: www.habr.com