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

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

பணி தேர்வு

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

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

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

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

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

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

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

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

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

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

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

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{முதல்~இடைவெளி}, underbrace{7, 8}_{இரண்டாவது~இடைவெளி}, 10}}\downarrow{compression}\pi(X) = {{underbrace{$, 1, 5}_{முதல்~இடைவெளி}, underbrace{7, 8}_{இரண்டாவது~இடைவெளி}, 10}}$$display$$

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

ADBIS-2019 மாநாடு

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

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