ڈیٹا میں فعال انحصار تلاش کرنا ڈیٹا کے تجزیہ کے مختلف شعبوں میں استعمال ہوتا ہے: ڈیٹا بیس مینجمنٹ، ڈیٹا کلیننگ، ڈیٹا بیس ریورس انجینئرنگ اور ڈیٹا ایکسپلوریشن۔ ہم خود انحصار کے بارے میں پہلے ہی شائع کر چکے ہیں۔ ایناستاسیا بریلو اور نکیتا بوبروف۔ اس بار، اناستاسیا، جو اس سال کمپیوٹر سائنس سینٹر سے فارغ التحصیل ہیں، اس تحقیقی کام کے حصے کے طور پر اس کام کی ترقی کا اشتراک کرتی ہیں جس کا اس نے مرکز میں دفاع کیا۔
ٹاسک سلیکشن
CS سینٹر میں پڑھتے ہوئے، میں نے ڈیٹا بیس کا گہرائی میں مطالعہ کرنا شروع کیا، یعنی فنکشنل اور فرق پر انحصار کی تلاش۔ یہ موضوع یونیورسٹی میں میرے کورس ورک کے موضوع سے متعلق تھا، اس لیے کورس ورک پر کام کرتے ہوئے، میں نے ڈیٹا بیس میں مختلف انحصار کے بارے میں مضامین پڑھنا شروع کیا۔ میں نے اس علاقے کا ایک جائزہ لکھا - میرا پہلا انگریزی میں اور اسے SEIM-2017 کانفرنس میں جمع کرایا۔ مجھے بہت خوشی ہوئی جب مجھے پتہ چلا کہ آخرکار اسے قبول کر لیا گیا ہے، اور اس موضوع میں مزید گہرائی میں جانے کا فیصلہ کیا۔ یہ تصور خود نیا نہیں ہے - یہ 90 کی دہائی میں استعمال ہونا شروع ہوا، لیکن اب بھی یہ بہت سے علاقوں میں استعمال ہوتا ہے۔
مرکز میں اپنے دوسرے سمسٹر کے دوران، میں نے ایک تحقیقی پروجیکٹ شروع کیا تاکہ فعال انحصار تلاش کرنے کے لیے الگورتھم کو بہتر بنایا جا سکے۔ اس نے جیٹ برینز ریسرچ میں سینٹ پیٹرزبرگ اسٹیٹ یونیورسٹی کی گریجویٹ طالبہ نکیتا بوبروف کے ساتھ مل کر اس پر کام کیا۔
فنکشنل انحصار کی تلاش کی کمپیوٹیشنل پیچیدگی
بنیادی مسئلہ کمپیوٹیشنل پیچیدگی ہے۔ ممکنہ کم سے کم اور غیر معمولی انحصار کی تعداد اوپر قدر کے لحاظ سے محدود ہے۔ جہاں - ٹیبل کی خصوصیات کی تعداد۔ الگورتھم کا آپریٹنگ وقت صرف صفات کی تعداد پر نہیں بلکہ قطاروں کی تعداد پر بھی منحصر ہے۔ 90 کی دہائی میں، ایک باقاعدہ ڈیسک ٹاپ پی سی پر وفاقی قانون کی تلاش کے الگورتھم کئی گھنٹوں تک 20 صفات اور دسیوں ہزار قطاروں پر مشتمل ڈیٹا سیٹ پر کارروائی کر سکتے تھے۔ ملٹی کور پروسیسرز پر چلنے والے جدید الگورتھم تقریباً ایک ہی وقت میں سینکڑوں صفات (200 تک) اور سیکڑوں ہزاروں قطاروں پر مشتمل ڈیٹا سیٹ کے لیے انحصار کا پتہ لگاتے ہیں۔ تاہم، یہ کافی نہیں ہے: ایسا وقت زیادہ تر حقیقی دنیا کی ایپلی کیشنز کے لیے ناقابل قبول ہے۔ لہذا، ہم نے موجودہ الگورتھم کو تیز کرنے کے لیے نقطہ نظر تیار کیا۔
تقسیم کے چوراہوں کے لیے کیشنگ اسکیمیں
کام کے پہلے حصے میں، ہم نے الگورتھم کی ایک کلاس کے لیے کیشنگ اسکیمیں تیار کیں جو کہ پارٹیشن انٹرسیکشن کا طریقہ استعمال کرتی ہیں۔ ایک انتساب کے لیے تقسیم فہرستوں کا ایک مجموعہ ہے، جہاں ہر فہرست میں کسی خاص وصف کے لیے یکساں اقدار کے ساتھ لائن نمبر ہوتے ہیں۔ ایسی ہر فہرست کو کلسٹر کہا جاتا ہے۔ بہت سے جدید الگورتھم اس بات کا تعین کرنے کے لیے پارٹیشنز کا استعمال کرتے ہیں کہ انحصار رکھا گیا ہے یا نہیں، یعنی وہ لیما پر قائم ہیں: انحصار منعقد اگر . یہاں ایک پارٹیشن نامزد کیا جاتا ہے اور پارٹیشن سائز کا تصور استعمال کیا جاتا ہے - اس میں کلسٹرز کی تعداد۔ الگورتھم جو پارٹیشنز کا استعمال کرتے ہیں، جب انحصار کی خلاف ورزی ہوتی ہے، انحصار کے بائیں جانب اضافی صفات شامل کرتے ہیں، اور پھر اس کا دوبارہ حساب لگاتے ہیں، پارٹیشنز کے انٹرسیکشن کے آپریشن کو انجام دیتے ہیں۔ اس آپریشن کو مضامین میں تخصص کہا جاتا ہے۔ لیکن ہم نے دیکھا ہے کہ انحصار کے لیے پارٹیشنز جو صرف مہارت کے چند دوروں کے بعد ہی برقرار رہیں گے فعال طور پر دوبارہ استعمال کیے جا سکتے ہیں، جو الگورتھم کے چلنے کے وقت کو نمایاں طور پر کم کر سکتے ہیں، کیونکہ انٹرسیکشن آپریشن مہنگا ہے۔
لہذا، ہم نے شینن اینٹروپی اور گینی غیر یقینی صورتحال کے ساتھ ساتھ اپنے میٹرک، جسے ہم نے ریورس اینٹروپی کہا ہے، پر مبنی ایک ہیورسٹک تجویز کیا۔ یہ شینن اینٹروپی کی ایک معمولی ترمیم ہے اور ڈیٹا سیٹ کی انفرادیت بڑھنے کے ساتھ ساتھ بڑھتی ہے۔ مجوزہ تخمینہ حسب ذیل ہے:
یہاں - حال ہی میں شمار شدہ تقسیم کی انفرادیت کی ڈگری اور انفرادی صفات کے لیے انفرادیت کے درجات کا میڈین ہے۔ اوپر بیان کردہ تینوں میٹرکس کو انفرادیت میٹرک کے طور پر جانچا گیا۔ آپ یہ بھی دیکھ سکتے ہیں کہ ہیورسٹک میں دو ترمیم کرنے والے ہیں۔ پہلا اشارہ کرتا ہے کہ موجودہ پارٹیشن بنیادی کلید کے کتنا قریب ہے اور آپ کو ان پارٹیشنز کو زیادہ حد تک کیش کرنے کی اجازت دیتا ہے جو ممکنہ کلید سے دور ہیں۔ دوسرا ترمیم کنندہ آپ کو کیش قبضے کی نگرانی کرنے کی اجازت دیتا ہے اور اس طرح خالی جگہ دستیاب ہونے پر کیشے میں مزید پارٹیشنز شامل کرنے کی حوصلہ افزائی کرتا ہے۔ اس مسئلے کے کامیاب حل نے ہمیں ڈیٹا سیٹ کے لحاظ سے PYRO الگورتھم کو 10-40% تک تیز کرنے کی اجازت دی۔ یہ بات قابل غور ہے کہ PYRO الگورتھم اس علاقے میں سب سے کامیاب ہے۔
نیچے دی گئی تصویر میں آپ کوائن فلپ کیشنگ کے بنیادی نقطہ نظر کے مقابلے میں مجوزہ ہیورسٹک کو لاگو کرنے کے نتائج دیکھ سکتے ہیں۔ ایکس محور لوگاریتھمک ہے۔
پارٹیشنز کو ذخیرہ کرنے کا ایک متبادل طریقہ
پھر ہم نے پارٹیشنز کو ذخیرہ کرنے کا ایک متبادل طریقہ تجویز کیا۔ پارٹیشنز کلسٹرز کا ایک سیٹ ہیں، جن میں سے ہر ایک مخصوص صفات کے لیے ایک جیسی قدروں کے ساتھ ٹیپلز کی تعداد کو محفوظ کرتا ہے۔ ان کلسٹرز میں ٹیپل نمبرز کی لمبی ترتیبیں ہوسکتی ہیں، مثال کے طور پر اگر کسی ٹیبل میں موجود ڈیٹا کو ترتیب دیا گیا ہو۔ لہذا، ہم نے پارٹیشنز کو اسٹور کرنے کے لیے ایک کمپریشن اسکیم تجویز کی، یعنی پارٹیشنز کے کلسٹرز میں قدروں کا وقفہ ذخیرہ:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First interval}, underbrace{7}, 8}_{Secend interval}, 10}}\ downarrow{compression} \ pi(X) = {{انڈربریس{$، 1، 5}_{پہلا~ وقفہ}، انڈربریس{7}، 8}{دوسرا~ وقفہ}، 10}}$$display$$
یہ طریقہ TANE الگورتھم کے آپریشن کے دوران میموری کی کھپت کو 1 سے 25٪ تک کم کرنے کے قابل تھا۔ TANE الگورتھم وفاقی قوانین کی تلاش کے لیے ایک کلاسک الگورتھم ہے؛ یہ اپنے کام کے دوران پارٹیشنز کا استعمال کرتا ہے۔ مشق کے حصے کے طور پر، TANE الگورتھم کا انتخاب کیا گیا تھا، کیونکہ اس میں وقفہ اسٹوریج کو لاگو کرنا بہت آسان تھا، مثال کے طور پر، PYRO میں یہ جائزہ لینے کے لیے کہ آیا مجوزہ نقطہ نظر کام کرتا ہے یا نہیں۔ حاصل کردہ نتائج نیچے دی گئی تصویر میں پیش کیے گئے ہیں۔ ایکس محور لوگارتھمک ہے۔
کانفرنس ADBIS-2019
تحقیق کے نتائج کی بنیاد پر، ستمبر 2019 میں میں نے ایک مضمون شائع کیا۔ ڈیٹا بیسز اور انفارمیشن سسٹمز (ADBIS-23) میں پیشرفت پر 2019 ویں یورپی کانفرنس میں۔ پریزنٹیشن کے دوران، ڈیٹا بیس کے شعبے میں ایک اہم شخص، Bernhard Thalheim نے کام کو نوٹ کیا۔ تحقیقی نتائج نے سینٹ پیٹرزبرگ اسٹیٹ یونیورسٹی میں ریاضی اور میکانکس میں ماسٹر ڈگری پر میرے مقالے کی بنیاد بنائی، جس کے دوران دونوں الگورتھم میں مجوزہ نقطہ نظر (کیشنگ اور کمپریشن) کو لاگو کیا گیا: TANE اور PYRO۔ مزید برآں، نتائج سے پتہ چلتا ہے کہ مجوزہ نقطہ نظر عالمگیر ہیں، کیونکہ دونوں الگورتھم پر، دونوں طریقوں کے ساتھ، میموری کی کھپت میں نمایاں کمی دیکھی گئی، ساتھ ہی الگورتھم کے آپریٹنگ وقت میں بھی نمایاں کمی دیکھی گئی۔
ماخذ: www.habr.com