Approximate Membership Query Filter
لگ بھگ ممبرشپ سوال فلٹر (اے ایم کیو-فلٹر) جگہ کے موثر ممکنہ ڈیٹا ڈھانچوں کا ایک گروپ ہے جو تقریبا رکنیت کے سوالات کی حمایت کرتا ہے۔ ایک لگ بھگ رکنیت کے سوال کا جواب ہے کہ آیا کوئی عنصر کسی سیٹ میں ہے یا نہیں جس کی غلط مثبت شرح ہے۔ بلوم فلٹر سب سے زیادہ معروف اے ایم کیو-فلٹر ہیں، لیکن دیگر اے ایم کیو-فلٹر بھی ہیں جو اضافی کارروائیوں کی حمایت کرتے ہیں یا جگہ کی مختلف ضروریات رکھتے ہیں۔ AMQ-فلٹرز کی متعدد ایپلی کیشنز ہیں، بنیادی طور پر تقسیم شدہ سسٹمز اور ڈیٹا بیس میں۔ وہاں، وہ اکثر نیٹ ورک کی درخواست یا I/O کارروائیوں سے بچنے کے لیے استعمال ہوتے ہیں جو ان عناصر کی درخواست کے نتیجے میں ہوتے ہیں جو موجود نہیں ہیں۔ لگ بھگ رکنیت کے استفسار کا مسئلہ تقریبا رکنیت کے استفسار کا مسئلہ عناصر کے ایک سیٹ کے بارے میں معلومات کو جگہ کے موثر طریقے سے ذخیرہ کرنا ہے۔ مقصد ان سوالات کا جواب دینا ہے کہ آیا کوئی عنصر سیٹ میں ہے یا نہیں جبکہ زیادہ سے زیادہ امکان کے ساتھ غلط مثبت کی اجازت دیتا ہے۔ تمام اے ایم کیو-فلٹر اس آپریشن تلاش کی حمایت کرتے ہیں۔ متحرک اے ایم کیو-فلٹر کسی بھی وقت اندراج کی اجازت دیتے ہیں جبکہ جامد اے ایم کیو-فلٹر کو اضافی عناصر داخل کرنے کے بعد دوبارہ تعمیر کرنا پڑتا ہے۔ کچھ اے ایم کیو فلٹر اضافی کارروائیوں کی حمایت کرتے ہیں جیسے عناصر کو حذف کرنا یا دو فلٹرز کو ضم کرنا۔ تلاش اس بات کا تعین کر سکتی ہے کہ آیا کوئی عنصر یقینی طور پر سیٹ میں نہیں ہے یا اگر کوئی عنصر شاید سیٹ میں ہے:: ہمیشہ درست آتا ہے۔ : کے امکان کے ساتھ غلط واپسی۔ غلط مثبت کسی عنصر کی تلاش ہے جو سیٹ کا حصہ نہیں ہے، لیکن تلاش ویسے بھی درست ہوتی ہے۔ اس کے ہونے کا امکان غلط مثبت شرح ہے۔ اے ایم کیو فلٹرز کے لیے غلط منفی (تلاش غلط واپسی کرتی ہے حالانکہ عنصر سیٹ کا حصہ ہے) کی اجازت نہیں ہے۔ اندراج کسی عنصر کو داخل کرنے کے بعد اس عنصر کی تلاش کو درست ہونا چاہیے۔ متحرک اے ایم کیو-فلٹر ڈیٹا ڈھانچے کی تعمیر نو کے بغیر ایک وقت میں عناصر کو داخل کرنے میں مدد کرتے ہیں۔ دوسرے اے ایم کیو فلٹرز کو ہر اندراج کے بعد دوبارہ تعمیر کرنا پڑتا ہے۔ انہیں جامد اے ایم کیو فلٹر کہا جاتا ہے۔ غلط مثبت شرح بمقابلہ جگہ اسٹوریج کے سائز اور غلط مثبت شرح کے درمیان ایک تجارت ہے۔ اسٹوریج کی جگہ بڑھانے سے غلط مثبت شرح کم ہو جاتی ہے۔ نظریاتی نچلی حد ہر عنصر کے لیے بٹس ہوتی ہے۔ متحرک اے ایم کیو-فلٹر اس نچلی حد تک نہیں پہنچ سکتے۔ انہیں داخل کرنے کے لیے کم از کم بٹس کی ضرورت ہوتی ہے۔ مختلف اے ایم کیو-فلٹر میں غلط مثبت شرحوں اور جگہ کی ضروریات کی مختلف حدود ہوتی ہیں۔ بہترین اے ایم کیو فلٹر کا انتخاب ایپلی کیشن پر منحصر ہے۔ اعداد و شمار کے ڈھانچے تقریبا رکنیت کے استفسار کے مسئلے کو حل کرنے کے مختلف طریقے ہیں۔ سب سے زیادہ معروف ڈیٹا ڈھانچہ بلوم فلٹرز ہیں، لیکن دیگر ڈیٹا ڈھانچے بھی ہیں جو کچھ غلط مثبت شرحوں اور جگہ کی ضروریات کے لیے بہتر کارکردگی کا مظاہرہ کرتے ہیں، اضافی کارروائیوں کی حمایت کرتے ہیں، یا دوسرے اندراج اور تلاش کے اوقات رکھتے ہیں۔ کچھ معروف اے ایم کیو فلٹر یہ ہیں: بلوم فلٹر ایک بلوم فلٹر ہیش افعال کے ساتھ بٹس کی ایک چھوٹی سی صف ہے۔ ہر ہیش فنکشن صف میں کسی ایک مقام پر ایک عنصر کا نقشہ بناتا ہے۔ شروع میں، صف کے تمام بٹس صفر پر سیٹ کیے جاتے ہیں۔ کسی عنصر کو داخل کرنے کے لیے، تمام ہیش افعال کا حساب لگایا جاتا ہے اور صف میں موجود تمام متعلقہ بٹس کو ایک پر سیٹ کیا جاتا ہے۔ کسی عنصر کو تلاش کرنے کے لیے، تمام ہیش افعال کا حساب لگایا جاتا ہے۔ اگر تمام متعلقہ بٹس سیٹ کیے جاتے ہیں، تو سچ واپس آ جاتا ہے۔ غلط مثبت شرح کو کم کرنے کے لیے، ہیش افعال کی تعداد میں اضافہ کیا جا سکتا ہے۔ کوٹینٹ فلٹر کا خیال کسی عنصر کو ہیش کرنا اور اس کے فنگر پرنٹ کو کم سے کم اہم بٹس میں تقسیم کرنا ہے جسے ریمینڈر اور سب سے اہم بٹس کو کوٹینٹ کہا جاتا ہے۔ حصص اس بات کا تعین کرتا ہے کہ ہیش ٹیبل میں بقیہ کہاں ذخیرہ کیا جاتا ہے۔ ہیش ٹیبل میں ہر سلاٹ کے لیے اضافی تین بٹس نرم تصادم کو حل کرنے کے لیے استعمال کیے جاتے ہیں (ایک ہی حصص لیکن مختلف بقیہ)۔ کوٹینٹ فلٹرز کے ذریعہ استعمال ہونے والی جگہ کا موازنہ بلوم فلٹرز سے کیا جا سکتا ہے، لیکن کوٹینٹ فلٹرز کو ان کی غلط مثبت شرح کو متاثر کیے بغیر ضم کیا جا سکتا ہے۔ کوکل فلٹر کوکل ہیشنگ پر مبنی ہوتے ہیں، لیکن عناصر کے صرف فنگر پرنٹس ہیش ٹیبل میں محفوظ ہوتے ہیں۔ ہر عنصر کے دو ممکنہ مقامات ہوتے ہیں۔ دوسرے مقام کا حساب پہلے مقام اور عنصر کے فنگر پرنٹ کی بنیاد پر کیا جاتا ہے۔ یہ پہلے سے داخل شدہ عناصر کو منتقل کرنے کے قابل بنانے کے لیے ضروری ہے اگر کسی عنصر کے لیے دونوں ممکنہ سلاٹ بھرے ہوئے ہوں۔ بوجھ کی حد تک پہنچنے کے بعد کوکل فلٹر کے داخل ہونے کی رفتار کم ہو جاتی ہے۔ یہ ممکن ہے کہ اندراج ناکام ہو جائے، اور میز کو دوبارہ کھینچنا پڑے۔ جبکہ بلوم فلٹرز میں ہمیشہ مستقل اندراج کا وقت ہوتا ہے، لیکن جیسے جیسے لوڈ فیکٹر بڑھتا ہے غلط مثبت شرح میں بھی اضافہ ہوتا ہے۔ کوکل فلٹر عناصر کو حذف کرنے کی حمایت کرتا ہے اگر ہم یقینی طور پر جانتے ہیں کہ عنصر داخل کیا گیا تھا۔ یہ بلوم فلٹرز اور کوٹینٹ فلٹرز کے مقابلے میں ایک فائدہ ہے جو اس آپریشن کی حمایت نہیں کرتے ہیں۔ Xor فلٹر جامد AMQ-فلٹر ہوتے ہیں جو بلومیئر فلٹر پر مبنی ہوتے ہیں اور آئیڈیا پرفیکٹ ہیش ٹیبل استعمال کرتے ہیں۔ کوکل فلٹرز کی طرح وہ ہیش ٹیبل میں موجود عناصر کے فنگر پرنٹس کو محفوظ کرتے ہیں۔ خیال یہ ہے کہ کسی عنصر کے لیے استفسار درست ہے اگر دیے گئے تین ہیش افعال کا xor فنگر پرنٹ ہے۔ ہیش ٹیبل بناتے وقت، ہر عنصر کو اس کے تین سلاٹس میں سے ایک اس طرح سے تفویض کیا جاتا ہے کہ اس سلاٹ کو کوئی دوسرا عنصر تفویض نہ کیا جائے۔ تمام عناصر کو تفویض کرنے کے بعد، ہم ہر عنصر کے لیے اس کی سلاٹ کی قیمت عنصر کے دو دوسرے (تفویض نہیں کیے گئے) سلاٹس کے xor اور عنصر کے فنگر پرنٹ پر سیٹ کرتے ہیں۔ یہ تعمیراتی الگورتھم ناکام ہو سکتا ہے اور ہیش ٹیبل کی تعمیر نو کے بغیر کوئی متحرک اندراج ممکن نہیں ہے۔ یہ ہیش ٹیبل فی عنصر صرف بٹس کا استعمال کرتے ہوئے بنایا جا سکتا ہے۔ اس فلٹر کا نقصان یہ ہے کہ اگر اضافی عناصر شامل کیے جائیں تو ڈیٹا ڈھانچے کو دوبارہ بنانا پڑتا ہے۔ وہ ایپلی کیشنز میں استعمال ہوتے ہیں جہاں بعد میں کسی عنصر کو شامل نہیں کرنا پڑتا ہے اور جگہ اہمیت کی حامل ہے۔ اے ایم کیو فلٹرز کی عام ایپلی کیشنز تقسیم شدہ سسٹم اور ڈیٹا بیس سسٹم ہیں۔ اے ایم کیو-فلٹر ڈیٹا بیس یا ریموٹ میموری کی کلیدوں کے سیٹ پر پراکسی کے طور پر کام کرتا ہے۔ ڈیٹا بیس یا ریموٹ میموری میں ممکنہ سست استفسار انجام دینے سے پہلے اے ایم کیو-فلٹر کا استعمال اس بات کا تخمینہ لگانے کے لیے کیا جاتا ہے کہ آیا کلید ڈیٹا بیس یا ریموٹ میموری میں ہے۔ سست استفسار صرف اس صورت میں انجام دیا جاتا ہے جب AMQ-فلٹر درست آتا ہے۔ صرف غلط مثبت نتیجہ غیر ضروری I/O آپریشن یا ریموٹ رسائی کا باعث بنتا ہے۔ ایپلی کیشنز بے شمار ہیں اور ان میں پیکیج اور ریسورس روٹنگ، پی 2 پی نیٹ ورک، اور ڈسٹری بیوٹڈ کیشنگ شامل ہیں: AMQ-فلٹر اکثر مہنگے ڈسک تک رسائی سے بچنے کے لیے میموری ڈیٹا ڈھانچے کے طور پر استعمال ہوتے ہیں۔ ایک ایپلی کیشن لاگ اسٹرکچرڈ مرج ٹری یا ایل ایس ایم ٹری ہے۔ ان میں ایک تیز میموری جزو اور ڈسک پر ایک یا ایک سے زیادہ اجزاء ہوتے ہیں جو خود درخت ہوتے ہیں۔ عناصر کو ان میموری جزو میں اس وقت تک داخل کیا جاتا ہے جب تک کہ یہ اپنے زیادہ سے زیادہ سائز تک نہ پہنچ جائے، اس کے مقابلے میں ان میموری جزو کو ڈسک اجزاء کے ساتھ ضم کر دیا جاتا ہے۔ تلاش کو تیز کرنے کے لیے بہت سے ایل ایس ایم درخت اے ایم کیو فلٹرز جیسے بلوم فلٹرز یا کوٹینٹ فلٹرز کو لاگو کرتے ہیں۔ وہ فلٹر ہر جزو کے لیے تخمینہ لگاتے ہیں کہ اس میں کون سے عناصر محفوظ ہیں۔ ایل ایس ایم درختوں کا استعمال ڈیٹا بیس جیسے اپاچی ایسٹرکس ڈی بی، بگ ٹیبل، ایچ بیس، لیول ڈی بی، ایس کیو لائٹ 4 میں کیا جاتا ہے۔ نیٹ ورک AMQ-فلٹرز کے لیے بہت سی ایپلی کیشنز پیش کرتے ہیں۔ وہ ڈیٹا کے ایک سیٹ کا تخمینہ لگانے کے لیے استعمال ہوتے ہیں جو مختلف سرورز پر واقع ہوتا ہے۔ بہت سے معاملات میں ان اے ایم کیو فلٹرز کو غیر متغیر کے طور پر دیکھا جا سکتا ہے۔ یہاں تک کہ اگر ریموٹ سرور پر سیٹ بدل جاتا ہے تو AMQ-فلٹر کو اکثر فوری طور پر اپ ڈیٹ نہیں کیا جاتا ہے، لیکن کچھ غلط مثبت کو برداشت کیا جاتا ہے۔ اس ایپلیکیشن کی ایک مثال ویب کیش شیئرنگ ہے۔ اگر کسی پراکسی کے پاس کیش مس ہے تو وہ اس بات کا تعین کرنا چاہتا ہے کہ آیا کسی اور پراکسی کے پاس درخواست کردہ ڈیٹا ہے یا نہیں۔ لہذا، پراکسی کو معلوم ہونا چاہیے یا کم از کم تخمینہ لگانا چاہیے کہ آیا کسی اور پراکسی کے پاس درخواست کردہ ویب پیج ہے۔ اسے وقتا فوقتا ویب صفحات کے یو آر ایل کے جامد اے ایم کیو-فلٹر کو نشر کرکے محفوظ کیا جا سکتا ہے جسے یو آر ایل کی فہرستیں نشر کرنے کے بجائے پراکسی نے کیش کیا ہے۔ اس ترتیب میں، اگر وقتا فوقتا اپ ڈیٹس کے درمیان کیش تبدیل ہو جائے تو غلط منفی ہو سکتے ہیں۔ اسی تصور کا اطلاق پی 2 پی نیٹ ورکس پر کیا جا سکتا ہے۔ نیٹ ورک کے ہر نوڈ پر جو کچھ ذخیرہ کیا گیا ہے اس کا تخمینہ لگانے کے لیے اے ایم کیو-فلٹرز کا استعمال کیا جا سکتا ہے۔ فلٹر کو نوڈس کے اصل دستاویزات کے آئی ڈیز یا مطلوبہ الفاظ سے بھرا جا سکتا ہے۔ جھوٹے مثبت صرف کچھ غیر ضروری درخواستوں کا باعث بنتے ہیں۔ اے ایم کیو-فلٹرز کے پی 2 پی نیٹ ورکس میں مزید ایپلی کیشنز ہیں مثال کے طور پر مختلف نوڈس پر محفوظ کردہ سیٹوں کے درمیان فرق یا چوراہے کو تلاش کرنا۔ حوالہ جات ممکنہ ڈیٹا ڈھانچے