தரவுத்தளங்களில் செயல்பாட்டு சார்புகளை திறம்பட கண்டறியவும்

தரவுகளில் செயல்பாட்டு சார்புகளைக் கண்டறிவது தரவு பகுப்பாய்வு பல்வேறு பகுதிகளில் பயன்படுத்தப்படுகிறது: தரவுத்தள மேலாண்மை, தரவு சுத்தம், தரவுத்தள தலைகீழ் பொறியியல் மற்றும் தரவு ஆய்வு. சார்புகளைப் பற்றி நாங்கள் ஏற்கனவே வெளியிட்டுள்ளோம் ஒரு கட்டுரை அனஸ்தேசியா பிரிலோ மற்றும் நிகிதா போப்ரோவ். இந்த நேரத்தில், இந்த ஆண்டு கணினி அறிவியல் மையத்தின் பட்டதாரி அனஸ்தேசியா, மையத்தில் அவர் பாதுகாத்த ஆராய்ச்சிப் பணியின் ஒரு பகுதியாக இந்த வேலையின் வளர்ச்சியைப் பகிர்ந்து கொள்கிறார்.

பணி தேர்வு

CS மையத்தில் படிக்கும் போது, ​​தரவுத்தளங்களை ஆழமாகப் படிக்க ஆரம்பித்தேன், அதாவது செயல்பாட்டு மற்றும் வேறுபாடு சார்புகளுக்கான தேடல். இந்த தலைப்பு பல்கலைக்கழகத்தில் எனது பாடத்திட்டத்தின் தலைப்புடன் தொடர்புடையது, எனவே பாடத்திட்டத்தில் பணிபுரியும் போது, ​​தரவுத்தளங்களில் பல்வேறு சார்புகளைப் பற்றிய கட்டுரைகளைப் படிக்க ஆரம்பித்தேன். நான் இந்த பகுதியில் ஒரு விமர்சனம் எழுதினேன் - என்னுடைய முதல் ஒன்று கட்டுரைகள் ஆங்கிலத்தில் மற்றும் SEIM-2017 மாநாட்டில் சமர்ப்பிக்கப்பட்டது. எல்லாவற்றிற்கும் மேலாக அவள் ஏற்றுக்கொள்ளப்பட்டாள் என்பதை அறிந்தபோது நான் மிகவும் மகிழ்ச்சியடைந்தேன், மேலும் தலைப்பை ஆழமாக ஆராய முடிவு செய்தேன். இந்த கருத்து புதியதல்ல - இது 90 களில் மீண்டும் பயன்படுத்தத் தொடங்கியது, ஆனால் இப்போது கூட இது பல பகுதிகளில் பயன்படுத்தப்படுகிறது.

மையத்தில் எனது இரண்டாவது செமஸ்டரின் போது, ​​செயல்பாட்டு சார்புகளைக் கண்டறிவதற்கான அல்காரிதம்களை மேம்படுத்துவதற்கான ஆராய்ச்சித் திட்டத்தைத் தொடங்கினேன். அவர் செயின்ட் பீட்டர்ஸ்பர்க் ஸ்டேட் யுனிவர்சிட்டி பட்டதாரி மாணவி நிகிதா போப்ரோவுடன் ஜெட்பிரைன்ஸ் ஆராய்ச்சியில் இணைந்து பணியாற்றினார்.

செயல்பாட்டு சார்புகளைத் தேடும் கணக்கீட்டு சிக்கலானது

முக்கிய பிரச்சனை கணக்கீட்டு சிக்கலானது. சாத்தியமான குறைந்தபட்ச மற்றும் அற்பமான சார்புகளின் எண்ணிக்கை மேலே உள்ள மதிப்பால் வரையறுக்கப்பட்டுள்ளது அங்கு - அட்டவணை பண்புக்கூறுகளின் எண்ணிக்கை. அல்காரிதம்களின் இயக்க நேரம் பண்புகளின் எண்ணிக்கையை மட்டுமல்ல, வரிசைகளின் எண்ணிக்கையையும் சார்ந்துள்ளது. 90களில், வழக்கமான டெஸ்க்டாப் கணினியில் உள்ள ஃபெடரல் லா தேடல் அல்காரிதம்கள் 20 பண்புக்கூறுகள் மற்றும் பல்லாயிரக்கணக்கான வரிசைகளைக் கொண்ட தரவுத் தொகுப்புகளை பல மணிநேரங்களில் செயலாக்க முடியும். மல்டி-கோர் செயலிகளில் இயங்கும் நவீன அல்காரிதம்கள், நூற்றுக்கணக்கான பண்புக்கூறுகள் (200 வரை) மற்றும் நூறாயிரக்கணக்கான வரிசைகளைக் கொண்ட தரவுத் தொகுப்புகளுக்கான சார்புகளைக் கண்டறியும். இருப்பினும், இது போதாது: பெரும்பாலான நிஜ உலக பயன்பாடுகளுக்கு அத்தகைய நேரம் ஏற்றுக்கொள்ள முடியாதது. எனவே, ஏற்கனவே உள்ள அல்காரிதம்களை விரைவுபடுத்துவதற்கான அணுகுமுறைகளை நாங்கள் உருவாக்கியுள்ளோம்.

பகிர்வு குறுக்குவெட்டுகளுக்கான கேச்சிங் திட்டங்கள்

வேலையின் முதல் பகுதியில், பகிர்வு வெட்டும் முறையைப் பயன்படுத்தும் ஒரு வகை அல்காரிதம்களுக்கான கேச்சிங் திட்டங்களை உருவாக்கினோம். ஒரு பண்புக்கூறுக்கான பகிர்வு என்பது பட்டியல்களின் தொகுப்பாகும், இதில் ஒவ்வொரு பட்டியலிலும் கொடுக்கப்பட்ட பண்புக்கூறுக்கான அதே மதிப்புகளுடன் வரி எண்கள் உள்ளன. அத்தகைய ஒவ்வொரு பட்டியலும் ஒரு கிளஸ்டர் என்று அழைக்கப்படுகிறது. பல நவீன வழிமுறைகள் சார்பு நிலை உள்ளதா இல்லையா என்பதை தீர்மானிக்க பகிர்வுகளைப் பயன்படுத்துகின்றன, அதாவது அவை லெம்மா: சார்பு நடத்தினால் . இங்கே ஒரு பகிர்வு நியமிக்கப்பட்டது மற்றும் பகிர்வு அளவு என்ற கருத்து பயன்படுத்தப்படுகிறது - அதில் உள்ள கிளஸ்டர்களின் எண்ணிக்கை. பகிர்வுகளைப் பயன்படுத்தும் அல்காரிதம்கள், சார்பு மீறப்படும்போது, ​​சார்புநிலையின் இடது பக்கத்தில் கூடுதல் பண்புகளைச் சேர்த்து, பின்னர் அதை மீண்டும் கணக்கிட்டு, பகிர்வுகளின் குறுக்குவெட்டு செயல்பாட்டைச் செய்கிறது. இந்த செயல்பாடு கட்டுரைகளில் நிபுணத்துவம் என்று அழைக்கப்படுகிறது. ஆனால், சில சுற்று நிபுணத்துவத்திற்குப் பிறகு மட்டுமே தக்கவைக்கப்படும் சார்புகளுக்கான பகிர்வுகளை தீவிரமாக மீண்டும் பயன்படுத்த முடியும் என்பதை நாங்கள் கவனித்தோம், இது அல்காரிதம்களின் இயங்கும் நேரத்தை கணிசமாகக் குறைக்கும், ஏனெனில் வெட்டும் செயல்பாடு விலை உயர்ந்தது.

எனவே, ஷானன் என்ட்ரோபி மற்றும் ஜின்னி நிச்சயமற்ற தன்மையை அடிப்படையாகக் கொண்ட ஒரு ஹூரிஸ்டிக் மற்றும் எங்கள் மெட்ரிக்கை நாங்கள் முன்மொழிந்தோம், அதை நாங்கள் ரிவர்ஸ் என்ட்ரோபி என்று அழைத்தோம். இது ஷானன் என்ட்ரோபியின் சிறிய மாற்றமாகும் மற்றும் தரவுத் தொகுப்பின் தனித்துவம் அதிகரிக்கும் போது அதிகரிக்கிறது. முன்மொழியப்பட்ட ஹூரிஸ்டிக் பின்வருமாறு:

இது - சமீபத்தில் கணக்கிடப்பட்ட பகிர்வின் தனித்தன்மையின் அளவு மற்றும் தனிப்பட்ட பண்புகளுக்கான தனித்தன்மையின் அளவுகளின் சராசரி. மேலே விவரிக்கப்பட்ட மூன்று அளவீடுகளும் தனித்தன்மை மெட்ரிக்காக சோதிக்கப்பட்டன. ஹூரிஸ்டிக்கில் இரண்டு மாற்றிகள் இருப்பதையும் நீங்கள் கவனிக்கலாம். முதலாவது தற்போதைய பகிர்வு முதன்மை விசைக்கு எவ்வளவு நெருக்கமாக உள்ளது என்பதைக் குறிக்கிறது மற்றும் சாத்தியமான விசையிலிருந்து வெகு தொலைவில் உள்ள பகிர்வுகளை அதிக அளவில் தற்காலிகமாக சேமிக்க உங்களை அனுமதிக்கிறது. இரண்டாவது மாற்றியானது கேச் ஆக்கிரமிப்பைக் கண்காணிக்க உங்களை அனுமதிக்கிறது. இந்தச் சிக்கலின் வெற்றிகரமான தீர்வு, தரவுத்தொகுப்பைப் பொறுத்து, PYRO அல்காரிதத்தை 10-40% வேகப்படுத்த அனுமதித்தது. PYRO அல்காரிதம் இந்த பகுதியில் மிகவும் வெற்றிகரமானது என்பது குறிப்பிடத்தக்கது.

கீழே உள்ள படத்தில், அடிப்படை நாணயம் புரட்டுதல் கேச்சிங் அணுகுமுறையுடன் ஒப்பிடும்போது, ​​முன்மொழியப்பட்ட ஹூரிஸ்டிக்கைப் பயன்படுத்துவதன் முடிவுகளைக் காணலாம். X அச்சு மடக்கை ஆகும்.

பகிர்வுகளை சேமிப்பதற்கான மாற்று வழி

பகிர்வுகளை சேமிப்பதற்கான மாற்று வழியை நாங்கள் முன்மொழிந்தோம். பகிர்வுகள் என்பது கிளஸ்டர்களின் தொகுப்பாகும், ஒவ்வொன்றும் சில பண்புகளுக்கு ஒரே மாதிரியான மதிப்புகளுடன் டூப்பிள்களின் எண்ணிக்கையை சேமிக்கிறது. இந்த க்ளஸ்டர்களில் டூப்பிள் எண்களின் நீண்ட வரிசைகள் இருக்கலாம், உதாரணமாக அட்டவணையில் உள்ள தரவு வரிசைப்படுத்தப்பட்டால். எனவே, பகிர்வுகளை சேமிப்பதற்கான சுருக்கத் திட்டத்தை நாங்கள் முன்மொழிந்தோம், அதாவது பகிர்வுகளின் தொகுப்பில் மதிப்புகளின் இடைவெளி சேமிப்பு:

$$display$$pi(X) = {{அண்டர்பிரேஸ்{1, 2, 3, 4, 5}_{முதல் இடைவெளி}, அண்டர்பிரேஸ்{7, 8}_{இரண்டாம் இடைவெளி}, 10}}\ கீழ்நோக்கி{ சுருக்கம்} \ pi(X) = {{அண்டர்பிரேஸ்{$, 1, 5}_{முதல்~இடைவெளி}, அண்டர்பிரேஸ்{7, 8}_{இரண்டாம்~இடைவெளி}, 10}}$$டிஸ்ப்ளே$$

இந்த முறையானது TANE அல்காரிதத்தின் செயல்பாட்டின் போது நினைவக நுகர்வு 1 முதல் 25% வரை குறைக்க முடிந்தது. TANE அல்காரிதம் என்பது கூட்டாட்சி சட்டங்களைத் தேடுவதற்கான ஒரு உன்னதமான அல்காரிதம் ஆகும்; இது அதன் வேலையின் போது பகிர்வுகளைப் பயன்படுத்துகிறது. நடைமுறையின் ஒரு பகுதியாக, TANE அல்காரிதம் தேர்ந்தெடுக்கப்பட்டது, ஏனெனில் முன்மொழியப்பட்ட அணுகுமுறை செயல்படுகிறதா என்பதை மதிப்பீடு செய்வதற்காக PYRO ஐ விட, இடைவெளி சேமிப்பகத்தை அதில் செயல்படுத்துவது மிகவும் எளிதாக இருந்தது. பெறப்பட்ட முடிவுகள் கீழே உள்ள படத்தில் வழங்கப்பட்டுள்ளன. X அச்சு மடக்கை ஆகும்.

மாநாடு ADBIS-2019

ஆராய்ச்சியின் முடிவுகளின் அடிப்படையில், செப்டம்பர் 2019 இல் நான் ஒரு கட்டுரையை வெளியிட்டேன் திறமையான செயல்பாட்டு சார்பு கண்டுபிடிப்புக்கான ஸ்மார்ட் கேச்சிங் தரவுத்தளங்கள் மற்றும் தகவல் அமைப்புகளில் முன்னேற்றங்கள் குறித்த 23வது ஐரோப்பிய மாநாட்டில் (ADBIS-2019). விளக்கக்காட்சியின் போது, ​​தரவுத்தளத் துறையில் குறிப்பிடத்தக்க நபரான பெர்ன்ஹார்ட் தல்ஹெய்ம் இந்த வேலையைக் குறிப்பிட்டார். செயின்ட் பீட்டர்ஸ்பர்க் ஸ்டேட் யுனிவர்சிட்டியில் கணிதம் மற்றும் இயக்கவியலில் முதுகலை பட்டப்படிப்பில் எனது ஆய்வுக் கட்டுரையின் அடிப்படையை ஆராய்ச்சி முடிவுகள் உருவாக்கியது, இதன் போது முன்மொழியப்பட்ட அணுகுமுறைகள் (கேச்சிங் மற்றும் கம்ப்ரஷன்) இரண்டு வழிமுறைகளிலும் செயல்படுத்தப்பட்டன: TANE மற்றும் PYRO. மேலும், முன்மொழியப்பட்ட அணுகுமுறைகள் உலகளாவியவை என்பதை முடிவுகள் காண்பித்தன, ஏனெனில் இரண்டு வழிமுறைகளிலும், இரண்டு அணுகுமுறைகளிலும், நினைவக நுகர்வில் குறிப்பிடத்தக்க குறைப்பு காணப்பட்டது, அத்துடன் அல்காரிதம்களின் இயக்க நேரத்தில் குறிப்பிடத்தக்க குறைப்பு காணப்பட்டது.

ஆதாரம்: www.habr.com