Өгөгдлийн функциональ хамаарлыг олох нь өгөгдлийн шинжилгээний янз бүрийн салбарт ашиглагддаг: мэдээллийн сангийн менежмент, өгөгдлийг цэвэрлэх, мэдээллийн сангийн урвуу инженерчлэл, өгөгдөл хайх. Бид хараат байдлын талаар аль хэдийн нийтэлсэн Анастасия Бирилло, Никита Бобров нар. Энэ удаад Компьютерийн Шинжлэх Ухааны Төвийг энэ жил төгссөн Анастасия тус төвд хамгаалсан судалгааны ажлынхаа хүрээнд энэхүү бүтээлээ хөгжүүлж байгаагаа хуваалцаж байна.
Даалгаврын сонголт
Би CS төвд суралцаж байхдаа мэдээллийн сангууд, тухайлбал функциональ болон ялгааны хамаарлыг эрэлхийлэх талаар гүнзгий судалж эхэлсэн. Энэ сэдэв нь миний их сургуулийн хичээлийн сэдэвтэй холбоотой байсан тул курсын ажил дээр ажиллаж байхдаа мэдээллийн сан дахь янз бүрийн хамаарлын тухай нийтлэлүүдийг уншиж эхэлсэн. Би энэ хэсгийн тоймыг бичсэн - миний анхны хүмүүсийн нэг англи хэл дээр SEIM-2017 чуулганд өргөн мэдүүлсэн. Эцсийн эцэст түүнийг хүлээж авсныг мэдээд би маш их баяртай байсан бөгөөд энэ сэдвийг илүү гүнзгийрүүлэхээр шийдсэн. Энэ үзэл баримтлал нь өөрөө шинэ зүйл биш - 90-ээд оноос хойш ашиглагдаж эхэлсэн боловч одоо ч олон салбарт ашиглагдаж байна.
Тус төвд XNUMX-р семестрт суралцаж байхдаа би функциональ хамаарлыг олох алгоритмыг сайжруулах судалгааны төслийг эхлүүлсэн. Тэрээр Санкт-Петербургийн Улсын Их Сургуулийн аспирант Никита Бобровтой JetBrains Research-д хамтран ажилласан.
Функциональ хамаарлыг хайх тооцооллын нарийн төвөгтэй байдал
Гол асуудал бол тооцооллын нарийн төвөгтэй байдал юм. Боломжит хамгийн бага болон чухал бус хамаарлын тоог дээрх утгаар хязгаарласан хаана - хүснэгтийн шинж чанаруудын тоо. Алгоритмуудын ажиллах хугацаа нь зөвхөн шинж чанаруудын тооноос гадна мөрийн тооноос хамаарна. 90-ээд оны үед ердийн ширээний компьютер дээрх холбооны хуулийн хайлтын алгоритмууд нь 20 хүртэлх шинж чанар, хэдэн арван мянган мөр агуулсан өгөгдлийн багцыг хэдэн цагийн дотор боловсруулж чаддаг байв. Олон цөмт процессор дээр ажилладаг орчин үеийн алгоритмууд нь ойролцоогоор ижил хугацаанд хэдэн зуун шинж чанар (200 хүртэл), хэдэн зуун мянган мөрнөөс бүрдэх өгөгдлийн багцын хамаарлыг илрүүлдэг. Гэсэн хэдий ч энэ нь хангалттай биш юм: ийм хугацаа нь ихэнх бодит хэрэглээний програмуудад хүлээн зөвшөөрөгдөхгүй. Тиймээс бид одоо байгаа алгоритмуудыг хурдасгах арга барилыг боловсруулсан.
Хуваалтын уулзваруудын кэшийн схемүүд
Ажлын эхний хэсэгт бид хуваалтын огтлолцлын аргыг ашигладаг алгоритмын ангиллын кэшийн схемийг боловсруулсан. Атрибутын хуваалт нь жагсаалт бүр нь тухайн шинж чанарын хувьд ижил утгатай мөрийн дугааруудыг агуулсан жагсаалтуудын багц юм. Ийм жагсаалт бүрийг кластер гэж нэрлэдэг. Орчин үеийн олон алгоритмууд нь хамаарал байгаа эсэхийг тодорхойлохын тулд хуваалтуудыг ашигладаг, тухайлбал: Хамаарал зохион байгуулсан бол . Энд байна хуваалтыг тодорхойлсон бөгөөд хуваалтын хэмжээ гэсэн ойлголтыг ашигладаг - доторх кластеруудын тоо. Хуваалтуудыг ашигладаг алгоритмууд нь хамаарал зөрчигдсөн тохиолдолд хамаарлын зүүн талд нэмэлт шинж чанаруудыг нэмж, дараа нь хуваалтуудын огтлолцлын үйлдлийг гүйцэтгэнэ. Энэ үйлдлийг нийтлэлд мэргэшүүлэх гэж нэрлэдэг. Гэхдээ бид хэд хэдэн мэргэшсэний дараа л хадгалагдах хамаарлын хуваалтыг идэвхтэй дахин ашиглах боломжтойг анзаарсан бөгөөд энэ нь огтлолцох ажиллагаа нь үнэтэй байдаг тул алгоритмуудын ажиллах хугацааг эрс багасгаж чадна.
Тиймээс бид Шеннон энтропи ба Жиннигийн тодорхойгүй байдал дээр үндэслэсэн эвристикийг санал болгосны зэрэгцээ урвуу энтропи гэж нэрлэсэн хэмжигдэхүүнээ санал болгосон. Энэ нь Shannon Entropy-ийн бага зэрэг өөрчлөлт бөгөөд өгөгдлийн багцын өвөрмөц байдал нэмэгдэх тусам нэмэгддэг. Санал болгож буй эвристик нь дараах байдалтай байна.
энд - саяхан тооцоолсон хуваалтын өвөрмөц байдлын зэрэг болон нь хувь хүний шинж чанаруудын давтагдашгүй байдлын дундаж үзүүлэлт юм. Дээр дурдсан бүх гурван хэмжүүрийг өвөрмөц байдлын хэмжүүр болгон шалгасан. Мөн эвристикт хоёр хувиргагч байгааг анзаарч болно. Эхнийх нь одоогийн хуваалт нь үндсэн түлхүүртэй хэр ойрхон байгааг харуулж байгаа бөгөөд боломжит түлхүүрээс хол байгаа хуваалтыг илүү их хэмжээгээр кэшлэх боломжийг танд олгоно. Хоёрдахь хувиргагч нь кэшийн ашиглалтыг хянах боломжийг олгодог бөгөөд ингэснээр хоосон зай байгаа тохиолдолд кэшэд илүү олон хуваалт нэмэхийг дэмждэг. Энэ асуудлыг амжилттай шийдсэн нь PYRO алгоритмыг өгөгдлийн багцаас хамааран 10-40% хурдасгах боломжийг бидэнд олгосон. PYRO алгоритм нь энэ чиглэлээр хамгийн амжилттай гэдгийг тэмдэглэх нь зүйтэй.
Доорх зурган дээр та санал болгож буй эвристикийг зоос эргүүлэх кэш хийх үндсэн аргатай харьцуулсан үр дүнг харж болно. X тэнхлэг нь логарифм юм.
Хуваалтуудыг хадгалах өөр арга
Дараа нь бид хуваалтыг хадгалах өөр аргыг санал болгов. Хуваалтууд нь кластеруудын багц бөгөөд тэдгээр нь тус бүр нь тодорхой шинж чанаруудын хувьд ижил утгатай олон тооны багцуудыг хадгалдаг. Эдгээр кластерууд нь жишээлбэл хүснэгтэд байгаа өгөгдлийг эрэмбэлсэн тохиолдолд урт дараалсан тоонуудыг агуулж болно. Тиймээс бид хуваалтуудыг хадгалах шахалтын схемийг санал болгов, тухайлбал хуваалтын кластер дахь утгыг интервалаар хадгалах.
$$display$$pi(X) = {{доорх{1, 2, 3, 4, 5}_{Эхний интервал}, доод хаалт{7, 8}_{Хоёр дахь интервал}, 10}}\ доош сум{ Шахах} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Энэ арга нь TANE алгоритмыг ажиллуулах явцад санах ойн зарцуулалтыг 1-ээс 25% хүртэл бууруулж чадсан. TANE алгоритм нь холбооны хуулийг хайх сонгодог алгоритм бөгөөд ажиллах явцад хуваалтуудыг ашигладаг. Практикийн нэг хэсэг болгон TANE алгоритмыг сонгосон, учир нь санал болгож буй арга нь ажиллаж байгаа эсэхийг үнэлэхийн тулд жишээлбэл PYRO-ээс илүү интервалын хадгалалтыг хэрэгжүүлэх нь илүү хялбар байсан. Хүлээн авсан үр дүнг доорх зурагт үзүүлэв. X тэнхлэг нь логарифм юм.
ADBIS-2019 бага хурал
Судалгааны үр дүнд үндэслэн 2019 оны XNUMX-р сард би нийтлэл хэвлүүлсэн Мэдээллийн сан ба мэдээллийн системийн дэвшлийн тухай Европын 23 дахь бага хурал (ADBIS-2019). Танилцуулгын үеэр мэдээллийн сангийн салбарын чухал хүн Бернхард Тальхайм уг ажлыг тэмдэглэв. Судалгааны үр дүн нь Санкт-Петербургийн Улсын Их Сургуулийн математик, механикийн чиглэлээр магистрын зэрэг хамгаалсан миний диссертацийн үндэс суурь болсон бөгөөд энэ хугацаанд санал болгож буй аргуудыг (кэш ба шахалт) TANE болон PYRO хоёр алгоритм дээр хэрэгжүүлсэн. Түүгээр ч зогсохгүй үр дүн нь санал болгож буй аргууд нь бүх нийтийн шинж чанартай болохыг харуулсан, учир нь хоёр алгоритмын аль алинд нь санах ойн зарцуулалт мэдэгдэхүйц буурч, алгоритмын ажиллах хугацаа мэдэгдэхүйц буурсан байна.
Эх сурвалж: www.habr.com