በመረጃ ቋቶች ውስጥ ተግባራዊ ጥገኞችን በብቃት ያግኙ

በመረጃ ላይ ያሉ ተግባራዊ ጥገኞችን መፈለግ በተለያዩ የመረጃ ትንተና ዘርፎች ጥቅም ላይ ይውላል፡ የውሂብ ጎታ አስተዳደር፣ የመረጃ ጽዳት፣ የውሂብ ጎታ ተቃራኒ ምህንድስና እና የመረጃ አሰሳ። ስለ ጥገኞቹ እራሳቸው አስቀድመን አሳትመናል። ጽሑፍ Anastasia Birillo እና Nikita Bobrov. በዚህ ጊዜ በዚህ አመት የኮምፒዩተር ሳይንስ ሴንተር የተመረቀችው አናስታሲያ የዚህን ስራ እድገት በማዕከሉ ጥብቅና ካደረገችው የምርምር ስራ አካል ጋር ትካፈላለች።

የተግባር ምርጫ

በሲኤስ ማእከል ውስጥ እያጠናሁ, የውሂብ ጎታዎችን በጥልቀት ማጥናት ጀመርኩ, ማለትም ተግባራዊ እና ልዩነት ጥገኛ ፍለጋ. ይህ ርዕስ በዩኒቨርሲቲ ውስጥ ካለኝ የኮርስ ስራ ርዕስ ጋር የተያያዘ ነው, ስለዚህ በኮርስ ስራው ላይ ስሰራ, በመረጃ ቋቶች ውስጥ ስለ ተለያዩ ጥገኞች ጽሑፎች ማንበብ ጀመርኩ. የዚህን አካባቢ ግምገማ ጻፍኩ - ከመጀመሪያዬ አንዱ ጽሑፎች በእንግሊዝኛ እና ለ SEIM-2017 ኮንፈረንስ አቅርቧል. ከሁሉም በኋላ ተቀባይነት እንዳገኘች ሳውቅ በጣም ደስ ብሎኝ ነበር, እና ወደ ርዕሱ በጥልቀት ለመፈተሽ ወሰንኩ. ጽንሰ-ሐሳቡ ራሱ አዲስ አይደለም - በ 90 ዎቹ ውስጥ ጥቅም ላይ መዋል ጀመረ, አሁን ግን በብዙ አካባቢዎች ጥቅም ላይ ይውላል.

በማዕከሉ ሁለተኛ ሴሚስተር በነበርኩበት ወቅት፣ የተግባር ጥገኝነቶችን ለማግኘት ስልተ ቀመሮችን ለማሻሻል የምርምር ፕሮጀክት ጀመርኩ። ከሴንት ፒተርስበርግ ስቴት ዩኒቨርሲቲ ተመራቂ ተማሪ ኒኪታ ቦቦሮቭ ጋር በጄትብሬንስ ምርምር ላይ ሠርታለች።

ተግባራዊ ጥገኝነቶችን የመፈለግ ስሌት ውስብስብነት

ዋናው ችግር የስሌት ውስብስብነት ነው. ሊሆኑ የሚችሉ አነስተኛ እና ቀላል ያልሆኑ ጥገኞች ቁጥር ከላይ በዋጋ የተገደበ ነው። የት - የሠንጠረዥ ባህሪያት ብዛት. የአልጎሪዝም አሠራር ጊዜ የሚወሰነው በባህሪያት ብዛት ላይ ብቻ ሳይሆን በረድፎች ብዛት ላይ ነው. በ90ዎቹ የፌደራል ህግ የፍለጋ ስልተ ቀመሮች በመደበኛ ዴስክቶፕ ፒሲ ላይ እስከ 20 የሚደርሱ ባህሪያትን እና በአስር ሺዎች የሚቆጠሩ ረድፎችን የያዙ የውሂብ ስብስቦችን እስከ ብዙ ሰአታት ውስጥ ማካሄድ ይችላል። በባለብዙ-ኮር ፕሮሰሰር ላይ የሚሰሩ ዘመናዊ ስልተ ቀመሮች በመቶዎች የሚቆጠሩ ባህሪያትን (እስከ 200) እና በመቶ ሺዎች የሚቆጠሩ ረድፎችን ያቀፉ የውሂብ ስብስቦች ጥገኝነቶችን በተመሳሳይ ጊዜ ይገነዘባሉ። ነገር ግን, ይህ በቂ አይደለም: እንዲህ ዓይነቱ ጊዜ ለአብዛኞቹ የእውነተኛ ዓለም አፕሊኬሽኖች ተቀባይነት የለውም. ስለዚህ, ያሉትን ስልተ ቀመሮችን ለማፋጠን አቀራረቦችን አዘጋጅተናል.

ለክፍል መገናኛዎች መሸጎጫ እቅዶች

በስራው የመጀመሪያ ክፍል ክፍልፍል መገናኛ ዘዴን ለሚጠቀሙ የአልጎሪዝም ክፍል የመሸጎጫ መርሃግብሮችን አዘጋጅተናል. የአንድ ባህሪ ክፍልፍል የዝርዝሮች ስብስብ ነው፣ እያንዳንዱ ዝርዝር ለአንድ የተወሰነ ባህሪ ተመሳሳይ እሴቶች ያላቸው የመስመር ቁጥሮችን የያዘ ነው። እያንዳንዱ እንደዚህ ያለ ዝርዝር ክላስተር ይባላል. ብዙ ዘመናዊ ስልተ ቀመሮች ጥገኝነት መያዙን ወይም አለመያዙን ለመወሰን ክፍልፋዮችን ይጠቀማሉ፣ እነሱም ከሌማ፡ ጥገኝነት ጋር ይከተላሉ። ከተያዘ . እዚህ አንድ ክፍል ተሰይሟል እና የክፋይ መጠን ጽንሰ-ሐሳብ ጥቅም ላይ ይውላል - በውስጡ ያሉት ስብስቦች ብዛት። ክፍልፋዮችን የሚጠቀሙ ስልተ ቀመሮች ጥገኝነት ሲጣስ በግራ በኩል ባለው ጥገኝነት ላይ ተጨማሪ ባህሪያትን ይጨምሩ እና ከዚያ እንደገና ያሰሉ, የክፍሎች መገናኛን አሠራር ያከናውናሉ. ይህ ክዋኔ በአንቀጾቹ ውስጥ ስፔሻላይዜሽን ይባላል. ነገር ግን ከጥቂት ዙሮች ስፔሻላይዜሽን በኋላ ብቻ የሚቆዩ የጥገኛ ክፍልፋዮች በንቃት እንደገና ጥቅም ላይ ሊውሉ እንደሚችሉ አስተውለናል ፣ ይህም የመስቀለኛ መንገድ ሥራ ውድ ስለሆነ የስልተ ቀመሮችን የስራ ጊዜ በእጅጉ ሊቀንስ ይችላል።

ስለዚህ፣ በሻነን ኢንትሮፒ እና በጂኒ ጥርጣሬ እንዲሁም በእኛ መለኪያ ላይ የተመሰረተ ሂዩሪቲካል ሃሳብ አቅርበን ነበር፣ እሱም Reverse Entropy። የሻነን ኢንትሮፒ ትንሽ ማሻሻያ ሲሆን የውሂብ ስብስቡ ልዩነት ሲጨምር ይጨምራል። የታቀደው ሂዩሪስቲክ እንደሚከተለው ነው-

ይህ ነው - በቅርብ ጊዜ የተሰላው ክፍልፋይ የልዩነት ደረጃ ና ለግለሰብ ባህሪያት የልዩነት ደረጃዎች መካከለኛ ነው። ከላይ የተገለጹት ሶስቱም መለኪያዎች እንደ ልዩነት መለኪያ ተፈትነዋል። በተጨማሪም በሂዩሪስቲክ ውስጥ ሁለት ማሻሻያዎች እንዳሉ ልብ ማለት ይችላሉ. የመጀመሪያው የሚያመለክተው የአሁኑ ክፍልፍል ከዋናው ቁልፍ ጋር ምን ያህል እንደሚጠጋ እና ከሚችለው ቁልፍ በጣም የራቁ ክፍፍሎችን በከፍተኛ መጠን እንዲሸጎጡ ያስችልዎታል። ሁለተኛው ማሻሻያ የመሸጎጫ ቦታን ለመከታተል ይፈቅድልዎታል እና በዚህ ምክንያት ነፃ ቦታ ካለ ተጨማሪ ክፍሎችን ወደ መሸጎጫው ማከል ያበረታታል። የዚህ ችግር የተሳካ መፍትሄ እንደ ዳታ ስብስብ ላይ በመመስረት የ PYRO አልጎሪዝምን ከ10-40% ለማፋጠን አስችሎናል። በዚህ አካባቢ የ PYRO አልጎሪዝም በጣም ስኬታማ መሆኑን ልብ ሊባል የሚገባው ነው.

ከታች ባለው ስእል ላይ ከመሠረታዊ የሳንቲም-መሸጎጫ ዘዴ ጋር ሲነጻጸር የታቀደውን ሂዩሪስቲክን የመተግበር ውጤቶችን ማየት ይችላሉ. የ X ዘንግ ሎጋሪዝም ነው።

ክፍልፋዮችን ለማከማቸት አማራጭ መንገድ

ከዚያም ክፍልፋዮችን ለማከማቸት አማራጭ መንገድ አቅርበናል. ክፍልፋዮች የክላስተር ስብስብ ናቸው፣ እያንዳንዱም ለተወሰኑ ባህሪያት ተመሳሳይ እሴቶች ያላቸውን የቱፕል ቁጥሮች ያከማቻል። እነዚህ ዘለላዎች ረጅም ተከታታይ የ tuple ቁጥሮችን ሊይዙ ይችላሉ፣ ለምሳሌ በሠንጠረዥ ውስጥ ያለው መረጃ የታዘዘ ከሆነ። ስለዚህ ክፍልፋዮችን ለማከማቸት ፣ ማለትም በክፍሎች ስብስቦች ውስጥ የእሴቶችን የጊዜ ክፍተት ለማከማቸት የመጨመቂያ እቅድ አቅርበናል-

$$display$$pi(X) = {{ከታሰረ{1, 2, 3, 4, 5}_{የመጀመሪያው ክፍተት}፣ ከስር ስር{7፣ 8}_{ሁለተኛ ክፍተት}፣ 10}}\ ቁልቁል{መጭመቂያ} \ pi(X) = {{ከታች ቅንፍ{$፣ 1፣ 5}_{መጀመሪያ~interval}፣ ከስር ቅንፍ{7፣ 8}_{ሁለተኛ~interval}፣ 10}}$$ ማሳያ$$

ይህ ዘዴ የ TANE አልጎሪዝም በሚሠራበት ጊዜ የማስታወስ ፍጆታን ከ 1 ወደ 25% መቀነስ ችሏል. የ TANE አልጎሪዝም የፌደራል ህጎችን ለመፈለግ ክላሲክ ስልተ-ቀመር ነው፤ በስራው ወቅት ክፍልፋዮችን ይጠቀማል። እንደ ልምምዱ አካል፣ የታሰበው አካሄድ እንደሚሰራ ለመገምገም ለምሳሌ በPYRO ውስጥ ካለው የጊዜ ክፍተት ማከማቻን መተግበር በጣም ቀላል ስለነበር የ TANE አልጎሪዝም ተመርጧል። የተገኘው ውጤት ከዚህ በታች ባለው ስእል ቀርቧል. የ X ዘንግ ሎጋሪዝም ነው።

ኮንፈረንስ ADBIS-2019

በጥናቱ ውጤቶች ላይ በመመስረት፣ በሴፕቴምበር 2019 አንድ ጽሑፍ አሳትሜያለሁ ለቅልጥፍና የተግባር ጥገኝነት ግኝት ስማርት መሸጎጫ በ 23 ኛው የአውሮፓ ኮንፈረንስ በመረጃ ቋቶች እና የመረጃ ሥርዓቶች እድገቶች (ADBIS-2019)። በገለፃው ወቅት ስራው በመረጃ ቋቶች መስክ ጉልህ በሆነው በበርንሃርድ ታልሃይም ተመልክቷል። የምርምር ውጤቶቹ በሴንት ፒተርስበርግ ስቴት ዩኒቨርሲቲ በሂሳብ እና በመካኒክስ የማስተርስ ዲግሪዬን የመመረቂያ ፅሁፌን መሰረት ያደረጉ ሲሆን በዚህ ወቅት ሁለቱም የታቀዱ አቀራረቦች (መሸጎጫ እና መጭመቅ) በሁለቱም ስልተ ቀመሮች ውስጥ ተግባራዊ ሆነዋል-TANE እና PYRO። ከዚህም በላይ ውጤቶቹ እንደሚያሳዩት የታቀዱት አቀራረቦች ሁለንተናዊ ናቸው, ምክንያቱም በሁለቱም ስልተ ቀመሮች ላይ, ከሁለቱም አቀራረቦች ጋር, የማህደረ ትውስታ ፍጆታ ላይ ከፍተኛ ቅነሳ, እንዲሁም በአልጎሪዝም የስራ ጊዜ ላይ ከፍተኛ ቅነሳ ታይቷል.

ምንጭ: hab.com