ڊيٽا ۾ فنڪشنل انحصار ڳولڻ ڊيٽا جي تجزيو جي مختلف علائقن ۾ استعمال ڪيو ويندو آهي: ڊيٽابيس مينيجمينٽ، ڊيٽا جي صفائي، ڊيٽابيس ريورس انجنيئرنگ ۽ ڊيٽا جي ڳولا. اسان اڳ ۾ ئي خود انحصار بابت شايع ڪيو آهي Anastasia Birillo ۽ Nikita Bobrov. هن ڀيري، انسٽاسيا، هن سال ڪمپيوٽر سائنس سينٽر جي گريجوئيٽ، هن ڪم جي ترقي کي حصيداري ڪري ٿو تحقيق جي ڪم جي حصي جي طور تي هن مرڪز ۾ دفاع ڪيو.
ڪم جي چونڊ
سي ايس سينٽر ۾ پڙهائڻ دوران، مون ڊيٽابيسس کي گہرائي ۾ پڙهڻ شروع ڪيو، يعني فنڪشنل ۽ فرق جي انحصار جي ڳولا. هي موضوع يونيورسٽي ۾ منهنجي ڪورس ورڪ جي موضوع سان لاڳاپيل هو، تنهنڪري ڪورس ورڪ تي ڪم ڪندي، مون ڊيٽابيس ۾ مختلف انحصار بابت آرٽيڪل پڙهڻ شروع ڪيو. مون هن علائقي جو هڪ جائزو لکيو - منهنجي پهرين مان هڪ انگريزي ۾ ۽ ان کي SEIM-2017 ڪانفرنس ۾ جمع ڪرايو. مون کي ڏاڍي خوشي ٿي جڏهن مون کي معلوم ٿيو ته هوءَ قبول ڪئي وئي هئي، ۽ فيصلو ڪيم ته موضوع تي وڌيڪ تفصيل سان غور ڪيو وڃي. تصور پاڻ کي نئون نه آهي - ان کي 90s ۾ واپس استعمال ڪرڻ شروع ڪيو، پر اڃا به ڪيترن ئي علائقن ۾ استعمال ڪيو ويندو آهي.
مرڪز ۾ منهنجي ٻئي سيمسٽر دوران، مون هڪ تحقيقي منصوبو شروع ڪيو ته جيئن ڪارڪردگي انحصار ڳولڻ لاءِ الگورتھم کي بهتر بڻائي سگهجي. هن ان تي سينٽ پيٽرسبرگ اسٽيٽ يونيورسٽي جي گريجوئيٽ شاگرد نڪيتا بوبروف سان گڏجي JetBrains Research ۾ ڪم ڪيو.
فنڪشنل انحصار جي ڳولا جي ڪمپيوٽيشنل پيچيدگي
بنيادي مسئلو ڪمپيوٽر جي پيچيدگي آهي. ممڪن آهي ته گهٽ ۾ گهٽ ۽ غير معمولي انحصار جو تعداد مٿين قدر طرفان محدود آهي ڪٿي - جدول جي خاصيتن جو تعداد. الورورٿم جي آپريٽنگ وقت نه رڳو خاصيتن جي تعداد تي منحصر آهي، پر قطار جي تعداد تي پڻ. 90 جي ڏهاڪي ۾، وفاقي قانون ڳولها الگورتھم هڪ باقاعده ڊيسڪ ٽاپ پي سي تي ڊيٽا سيٽ کي پروسيس ڪري سگھن ٿا جن ۾ 20 خاصيتون ۽ ڏهه هزار قطارون ڪيترن ئي ڪلاڪن تائين شامل آهن. ملٽي-ڪور پروسيسرز تي هلندڙ جديد الگورٿمس ڊيٽا سيٽن لاءِ انحصار کي ڳوليندا آهن جن ۾ سوين خاصيتون (200 تائين) ۽ لڳ ڀڳ هڪ ئي وقت ۾ سوين هزارين قطارون شامل آهن. بهرحال، اهو ڪافي ناهي: اهڙي وقت تمام حقيقي دنيا جي ايپليڪيشنن لاء ناقابل قبول آهي. تنهن ڪري، اسان موجوده الگورتھم کي تيز ڪرڻ لاء طريقا ٺاهيا.
ورهاڱي جي چونڪن لاءِ ڪيشنگ اسڪيمون
ڪم جي پهرئين حصي ۾، اسان ڪيشنگ اسڪيمون تيار ڪيون آھن ڪلاس جي الگورتھم لاءِ جيڪي ورهاڱي جي چونڪ جو طريقو استعمال ڪن ٿيون. هڪ وصف لاء هڪ ورهاڱي فهرستن جو هڪ سيٽ آهي، جتي هر لسٽ ۾ ڏنل وصف لاء ساڳئي قدرن سان لائن نمبر شامل آهن. هر اهڙي فهرست کي ڪلستر سڏيو ويندو آهي. ڪيترائي جديد الگورٿمس استعمال ڪن ٿا ورهاڱي کي طئي ڪرڻ لاءِ ته انحصار رکيل آهي يا نه، يعني اهي ليما تي عمل ڪن ٿا: انحصار منعقد جيڪڏھن . هتي هڪ ورهاڱي کي نامزد ڪيو ويو آهي ۽ ورهاڱي جي ماپ جو تصور استعمال ڪيو ويو آهي - ان ۾ ڪلستر جو تعداد. الگورٿمس جيڪي ورهاڱي کي استعمال ڪن ٿا، جڏهن انحصار جي ڀڃڪڙي ٿئي ٿي، انحصار جي کاٻي پاسي ۾ اضافي خاصيتون شامل ڪريو، ۽ پوء ان کي ٻيهر ڳڻڻ، ڊويزن جي چونڪ جي آپريشن کي انجام ڏيو. هن آپريشن کي آرٽيڪلز ۾ اسپيشلائيزيشن چئبو آهي. پر اسان ڏٺو آهي ته انحصار لاءِ ورهاڱي وارا جيڪي صرف اسپيشلائيزيشن جي چند دورن کان پوءِ برقرار رکيا ويندا فعال طور تي ٻيهر استعمال ڪري سگھجن ٿا، جيڪي خاص طور تي الورورٿمس جي هلندڙ وقت کي گهٽائي سگهن ٿا، ڇاڪاڻ ته چونڪ جو آپريشن مهانگو آهي.
تنهن ڪري، اسان تجويز ڪيو هوريسٽڪ جي بنياد تي شنن اينٽروپي ۽ گيني غير يقيني صورتحال، انهي سان گڏ اسان جي ميٽرڪ، جنهن کي اسان ريورس اينٽروپي سڏيو آهي. اهو شانن اينٽروپي جي هڪ معمولي ترميم آهي ۽ وڌندي آهي جيئن ڊيٽا سيٽ جي انفراديت وڌائي ٿي. تجويز ڪيل هوريسٽ هن ريت آهي:
اهو آهي - تازو حساب ٿيل ورهاڱي جي انفراديت جو درجو ۽ انفرادي خاصيتن لاء انفراديت جي درجي جو وچولي آهي. مٿي بيان ڪيل سڀني ٽن ميٽرڪ کي انفراديت ميٽرڪ جي طور تي آزمايو ويو. توهان اهو پڻ نوٽيس ڪري سگهو ٿا ته هوريسٽ ۾ ٻه ترميم ڪندڙ آهن. پهريون اشارو ڏيکاري ٿو ته موجوده ورهاڱي جي ڪيتري ويجهو آهي پرائمري ڪيئي ۽ توهان کي اجازت ڏئي ٿي ڪيش ڪرڻ جي وڏي حد تائين اهي پارٽيشن جيڪي ممڪن ڪي کان پري آهن. ٻيو ترميم ڪندڙ توهان کي ڪيش جي قبضي جي نگراني ڪرڻ جي اجازت ڏئي ٿو ۽ انهي سان گڏ ڪيش ۾ وڌيڪ ورهاڱي شامل ڪرڻ جي حوصلا افزائي ڪري ٿو جيڪڏهن مفت جاء موجود آهي. ھن مسئلي جو ڪامياب حل اسان کي PYRO الگورتھم کي 10-40٪ تائين تيز ڪرڻ جي اجازت ڏني، ڊيٽا سيٽ تي منحصر آھي. اها ڳالهه نوٽ ڪرڻ گهرجي ته PYRO الگورتھم هن علائقي ۾ سڀ کان ڪامياب آهي.
ھيٺ ڏنل شڪل ۾ توھان ڏسي سگھو ٿا تجويز ڪيل ھيورسٽڪ لاڳو ڪرڻ جا نتيجا ھڪ بنيادي ڪوئن-فلپ ڪيشنگ اپروچ جي مقابلي ۾. ايڪس محور منطقي آهي.
ورهاڱي کي ذخيرو ڪرڻ لاء هڪ متبادل طريقو
ان کان پوء اسان ورهاڱي کي ذخيرو ڪرڻ لاء هڪ متبادل طريقو پيش ڪيو. ورهاڱي ڪلستر جو هڪ سيٽ آهن، جن مان هر هڪ ٽپلن جي تعداد کي ذخيرو ڪري ٿو هڪجهڙائي قدر سان ڪجهه خاصيتن لاء. اهي ڪلستر شايد ٽپل نمبرن جي ڊگھي ترتيبن تي مشتمل هجن، مثال طور جيڪڏهن جدول ۾ ڊيٽا ترتيب ڏنل آهي. تنهن ڪري، اسان ورهاڱي کي محفوظ ڪرڻ لاء هڪ کمپريشن اسڪيم جي تجويز ڏني، يعني تقسيم جي ڪلستر ۾ قدرن جو وقفو اسٽوريج:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First interval}, underbrace{7}, 8}_{second interval}, 10}}\ downarrow{compression} \ pi(X) = {{انڊربريس{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
اهو طريقو 1 کان 25٪ تائين TANE الگورتھم جي آپريشن دوران ياداشت جي استعمال کي گهٽائڻ جي قابل هو. TANE الگورٿم وفاقي قانونن جي ڳولا لاءِ هڪ کلاسک الگورٿم آهي؛ اهو پنهنجي ڪم دوران ورهاڱي کي استعمال ڪري ٿو. مشق جي حصي جي طور تي، TANE الورورٿم چونڊيو ويو، ڇاڪاڻ ته ان ۾ وقفي اسٽوريج کي لاڳو ڪرڻ تمام آسان هو، مثال طور، PYRO ۾ اهو جائزو وٺڻ لاء ته ڇا تجويز ڪيل طريقو ڪم ڪري ٿو. حاصل ڪيل نتيجا ھيٺ ڏنل شڪل ۾ پيش ڪيا ويا آھن. ايڪس محور منطقي آهي.
ڪانفرنس ADBIS-2019
تحقيق جي نتيجن جي بنياد تي، سيپٽمبر 2019 ۾ مون هڪ مضمون شايع ڪيو 23 هين يورپي ڪانفرنس آن ايڊوانسز ان ڊيٽابيسس اينڊ انفارميشن سسٽم (ADBIS-2019). پريزنٽيشن دوران، ڊيٽابيس جي شعبي ۾ هڪ اهم شخص Bernhard Thalheim پاران ڪم نوٽ ڪيو ويو. تحقيق جا نتيجا سينٽ پيٽرسبرگ اسٽيٽ يونيورسٽي ۾ رياضي ۽ ميڪنڪس ۾ ماسٽر جي ڊگري تي منهنجي مقالي جو بنياد بڻيا، جنهن دوران ٻنهي تجويز ڪيل طريقا (ڪيشنگ ۽ ڪمپريشن) ٻنهي الگورتھم ۾ لاڳو ڪيا ويا: TANE ۽ PYRO. ان کان علاوه، نتيجن مان ظاهر ٿئي ٿو ته تجويز ڪيل طريقا آفاقي آهن، ڇاڪاڻ ته ٻنهي الگورتھم تي، ٻنهي طريقن سان، يادداشت جي استعمال ۾ هڪ اهم گهٽتائي ڏٺو ويو آهي، انهي سان گڏ الگورتھم جي آپريٽنگ وقت ۾ هڪ اهم گهٽتائي.
جو ذريعو: www.habr.com