Approximate Membership Query Filter
আনুমানিক সদস্যপদ প্রশ্ন ফিল্টার (এ. এম. কিউ-ফিল্টার) হল স্থান-দক্ষ সম্ভাব্য তথ্য কাঠামোর একটি গোষ্ঠী যা আনুমানিক সদস্যপদ প্রশ্নগুলিকে সমর্থন করে। একটি আনুমানিক সদস্যপদ প্রশ্ন উত্তর দেয় যে কোনও উপাদান একটি সেটে আছে কি না যার ফলস পজিটিভ হার। ব্লুম ফিল্টারগুলি সর্বাধিক পরিচিত এএমকিউ-ফিল্টার, তবে অন্যান্য এএমকিউ-ফিল্টার রয়েছে যা অতিরিক্ত ক্রিয়াকলাপকে সমর্থন করে বা বিভিন্ন জায়গার প্রয়োজনীয়তা রয়েছে। এএমকিউ-ফিল্টারগুলির অসংখ্য প্রয়োগ রয়েছে, প্রধানত ডিস্ট্রিবিউটেড সিস্টেম এবং ডাটাবেসে। সেখানে, এগুলি প্রায়শই নেটওয়ার্ক অনুরোধ বা আই/ও অপারেশনগুলি এড়াতে ব্যবহৃত হয় যা বিদ্যমান নয় এমন উপাদানগুলির অনুরোধের ফলে ঘটে। আনুমানিক সদস্যপদ প্রশ্ন সমস্যা আনুমানিক সদস্যপদ প্রশ্ন সমস্যা হল একটি স্থান-দক্ষ উপায়ে উপাদানগুলির একটি সেট সম্পর্কে তথ্য সংরক্ষণ করা। লক্ষ্য হল কোনও উপাদান সেটের মধ্যে আছে কি না সেই প্রশ্নের উত্তর দেওয়া এবং এর সর্বাধিক সম্ভাব্যতা সহ মিথ্যা ধনাত্মকগুলিকে অনুমতি দেওয়া। সমস্ত এ. এম. কিউ-ফিল্টার এই অপারেশন অনুসন্ধানকে সমর্থন করে। গতিশীল এ. এম. কিউ-ফিল্টার যে কোনও সময় সন্নিবেশের অনুমতি দেয় যেখানে স্ট্যাটিক এ. এম. কিউ-ফিল্টারগুলিকে অতিরিক্ত উপাদান সন্নিবেশ করার পরে পুনর্নির্মাণ করতে হয়। কিছু এএমকিউ-ফিল্টার উপাদানগুলি মুছে ফেলা বা দুটি ফিল্টার একত্রিত করার মতো অতিরিক্ত ক্রিয়াকলাপগুলিকে সমর্থন করে। একটি অনুসন্ধান নির্ধারণ করতে পারে যে কোনও উপাদান অবশ্যই সেটে নেই কিনা বা কোনও উপাদান সম্ভবত সেটে রয়েছে কিনাঃ সর্বদা সত্য প্রদান করে। : এর সম্ভাবনা সহ মিথ্যা ফেরত দিন। একটি ফলস পজিটিভ হল এমন একটি উপাদানের সন্ধান যা সেটের অংশ নয়, তবে সন্ধানটি যেভাবেই হোক সত্য হয়। এই ঘটনা ঘটার সম্ভাবনা হল ফলস পজিটিভ হার। এএমকিউ-ফিল্টারগুলির জন্য মিথ্যা নেতিবাচক (সন্ধানটি মিথ্যা প্রদান করে যদিও উপাদানটি সেটের অংশ) অনুমোদিত নয়। সন্নিবেশ একটি উপাদান সন্নিবেশ করার পরে এই উপাদানটির সন্ধান অবশ্যই সত্য হতে হবে। গতিশীল এ. এম. কিউ-ফিল্টারগুলি তথ্য কাঠামো পুনর্নির্মাণ না করে একবারে একটি করে উপাদান সন্নিবেশ করাকে সমর্থন করে। প্রতিটি সন্নিবেশের পরে অন্যান্য এএমকিউ-ফিল্টারগুলি পুনর্নির্মাণ করতে হবে। এগুলিকে স্ট্যাটিক এ. এম. কিউ-ফিল্টার বলা হয়। মিথ্যা ধনাত্মক হার বনাম স্থান সংরক্ষণের আকার এবং মিথ্যা ধনাত্মক হারের মধ্যে একটি বিনিময় রয়েছে। সংরক্ষণের স্থান বাড়ানোর ফলে ফলস পজিটিভ হার হ্রাস পায়। তাত্ত্বিক নিম্ন সীমা হল প্রতিটি উপাদানের জন্য বিট। গতিশীল এ. এম. কিউ-ফিল্টারগুলি এই নিম্ন সীমাতে পৌঁছতে পারে না। সন্নিবেশের জন্য তাদের অন্তত বিট প্রয়োজন। বিভিন্ন এ. এম. কিউ-ফিল্টারের মিথ্যা ধনাত্মক হার এবং স্থানের প্রয়োজনীয়তার বিভিন্ন পরিসর রয়েছে। সর্বোত্তম এ. এম. কিউ-ফিল্টার নির্বাচন করা নির্ভর করে অ্যাপ্লিকেশনের উপর। ডেটা স্ট্রাকচার আনুমানিক সদস্যপদ প্রশ্নের সমস্যা সমাধানের বিভিন্ন উপায় রয়েছে। সর্বাধিক পরিচিত তথ্য কাঠামো হল ব্লুম ফিল্টার, তবে অন্যান্য তথ্য কাঠামো রয়েছে যা কিছু মিথ্যা ধনাত্মক হার এবং স্থানের প্রয়োজনীয়তার জন্য আরও ভাল কাজ করে, অতিরিক্ত ক্রিয়াকলাপকে সমর্থন করে, বা অন্যান্য সন্নিবেশ এবং সন্ধানের সময় থাকে। কিছু সুপরিচিত এএমকিউ-ফিল্টার হলঃ ব্লুম ফিল্টার একটি ব্লুম ফিল্টার হ্যাশ ফাংশন সহ বিটের একটি বিট অ্যারে। প্রতিটি হ্যাশ ফাংশন অ্যারের অবস্থানগুলির মধ্যে একটিতে একটি উপাদানকে ম্যাপ করে। শুরুতে, অ্যারের সমস্ত বিট শূন্যে সেট করা থাকে। একটি উপাদান সন্নিবেশ করার জন্য, সমস্ত হ্যাশ ফাংশন গণনা করা হয় এবং অ্যারের সমস্ত সংশ্লিষ্ট বিট একটিতে সেট করা হয়। একটি উপাদান খুঁজতে, সমস্ত হ্যাশ ফাংশন গণনা করা হয়। যদি সমস্ত সংশ্লিষ্ট বিট সেট করা থাকে, তবে সত্য ফেরত দেওয়া হয়। মিথ্যা ধনাত্মক হার কমাতে, হ্যাশ ফাংশনের সংখ্যা এবং বৃদ্ধি করা যেতে পারে। কোয়েন্ট ফিল্টার কোয়েন্ট ফিল্টারগুলির ধারণা হল একটি উপাদানকে হ্যাশ করা এবং তার ফিঙ্গারপ্রিন্টকে ন্যূনতম উল্লেখযোগ্য বিটগুলিতে বিভক্ত করা যাকে অবশিষ্টাংশ বলা হয় এবং সবচেয়ে গুরুত্বপূর্ণ বিটকে কোয়েন্ট বলা হয়। ভাগফল নির্ধারণ করে যে হ্যাশ টেবিলে অবশিষ্টাংশ কোথায় সংরক্ষণ করা হয়। হ্যাশ টেবিলের প্রতিটি স্লটের জন্য অতিরিক্ত তিনটি বিট নরম সংঘর্ষের সমাধান করতে ব্যবহৃত হয় (একই ভাগফল কিন্তু ভিন্ন অবশিষ্টাংশ)। কোয়েন্ট ফিল্টার দ্বারা ব্যবহৃত স্থান ব্লুম ফিল্টারগুলির সাথে তুলনীয়, তবে কোয়েন্ট ফিল্টারগুলি তাদের মিথ্যা ধনাত্মক হারকে প্রভাবিত না করে একত্রিত করা যেতে পারে। কোকিল ফিল্টার কোকিল হ্যাশিং-এর উপর ভিত্তি করে তৈরি, তবে শুধুমাত্র উপাদানগুলির আঙুলের ছাপ হ্যাশ টেবিলে সংরক্ষণ করা হয়। প্রতিটি উপাদানের দুটি সম্ভাব্য অবস্থান রয়েছে। দ্বিতীয় অবস্থানটি প্রথম অবস্থান এবং উপাদানটির আঙুলের ছাপের উপর ভিত্তি করে গণনা করা হয়। যদি কোনও উপাদানের জন্য উভয় সম্ভাব্য স্লট পূর্ণ থাকে তবে ইতিমধ্যে সন্নিবেশিত উপাদানগুলি সরানো সক্ষম করার জন্য এটি প্রয়োজনীয়। একটি লোড থ্রেশহোল্ডে পৌঁছানোর পরে কোকিল ফিল্টারের সন্নিবেশের গতি হ্রাস পায়। এটি সম্ভব যে একটি সন্নিবেশ ব্যর্থ হয়, এবং টেবিলটি অবশ্যই পুনর্ব্যবহার করা উচিত। যেখানে ব্লুম ফিল্টারগুলির সর্বদা ধ্রুবক সন্নিবেশের সময় থাকে, তবে লোড ফ্যাক্টর বাড়ার সাথে সাথে ফলস পজিটিভ হারও বৃদ্ধি পায়। একটি কোকিল ফিল্টার উপাদানগুলি মুছে ফেলাকে সমর্থন করে যদি আমরা নিশ্চিতভাবে জানি যে উপাদানটি সন্নিবেশ করা হয়েছিল। এটি ব্লুম ফিল্টার এবং কোয়োশিয়েন্ট ফিল্টারগুলির তুলনায় একটি সুবিধা যা এই ক্রিয়াকলাপকে সমর্থন করে না। Xor ফিল্টারগুলি স্ট্যাটিক AMQ-ফিল্টার যা একটি ব্লুমিয়ার ফিল্টার ভিত্তিক এবং ধারণাটি নিখুঁত হ্যাশ টেবিল ব্যবহার করে। কোকিল ফিল্টারের মতো এগুলি হ্যাশ টেবিলের উপাদানগুলির আঙুলের ছাপ সংরক্ষণ করে। ধারণাটি হল যে একটি উপাদানের জন্য একটি প্রশ্ন সত্য যদি প্রদত্ত তিনটি হ্যাশ ফাংশনের xor এর আঙুলের ছাপ হয়। হ্যাশ টেবিল তৈরি করার সময়, প্রতিটি উপাদানকে তার তিনটি স্লটের মধ্যে একটি এমনভাবে বরাদ্দ করা হয় যাতে এই স্লটে অন্য কোনও উপাদান বরাদ্দ করা না হয়। সমস্ত উপাদান বরাদ্দ করার পরে, আমরা প্রতিটি উপাদানের জন্য তার স্লটের মান উপাদানটির অন্য দুটি (নির্ধারিত নয়) স্লট এবং উপাদানটির আঙ্গুলের ছাপের xor-এ সেট করি। এই নির্মাণ অ্যালগরিদম ব্যর্থ হতে পারে এবং হ্যাশ টেবিল পুনর্নির্মাণ ছাড়া কোনও গতিশীল সন্নিবেশ সম্ভব নয়। এই হ্যাশ টেবিলটি প্রতি উপাদান শুধুমাত্র বিট ব্যবহার করে তৈরি করা যেতে পারে। এই ফিল্টারের অসুবিধা হল অতিরিক্ত উপাদান যোগ করা হলে ডেটা স্ট্রাকচারটি পুনর্নির্মাণ করতে হবে। এগুলি এমন অ্যাপ্লিকেশনগুলিতে ব্যবহৃত হয় যেখানে পরে কোনও উপাদান যুক্ত করতে হয় না এবং স্থান গুরুত্বপূর্ণ। এএমকিউ-ফিল্টারগুলির সাধারণ প্রয়োগগুলি হল ডিস্ট্রিবিউটেড সিস্টেম এবং ডাটাবেস সিস্টেম। এএমকিউ-ফিল্টার একটি ডাটাবেস বা রিমোট মেমরির কীগুলির সেটের প্রক্সি হিসাবে কাজ করে। ডাটাবেস বা রিমোট মেমরিতে একটি অনুমানযোগ্য ধীর অনুসন্ধান সম্পন্ন করার আগে এএমকিউ-ফিল্টারটি আনুমানিকভাবে ব্যবহার করা হয় যদি কীটি ডাটাবেস বা রিমোট মেমরিতে থাকে। যদি এ. এম. কিউ-ফিল্টার সঠিক হয়, তবেই ধীরগতির প্রশ্ন করা হয়। শুধুমাত্র একটি মিথ্যা ইতিবাচক ফলাফল একটি অপ্রয়োজনীয় আই/ও অপারেশন বা দূরবর্তী প্রবেশাধিকারের দিকে পরিচালিত করে। অ্যাপ্লিকেশনগুলি অসংখ্য এবং এতে প্যাকেজ এবং রিসোর্স রাউটিং, পি2পি নেটওয়ার্ক এবং ডিস্ট্রিবিউটেড ক্যাশিং অন্তর্ভুক্ত রয়েছেঃ এএমকিউ-ফিল্টারগুলি প্রায়শই ব্যয়বহুল ডিস্ক অ্যাক্সেস এড়াতে ইন-মেমরি ডেটা স্ট্রাকচার হিসাবে ব্যবহৃত হয়। একটি অ্যাপ্লিকেশন হল লগ-স্ট্রাকচার্ড মার্জ-ট্রি বা এলএসএম-ট্রি। এগুলির একটি দ্রুত ইন-মেমরি উপাদান রয়েছে এবং একটি ডিস্কে এক বা একাধিক উপাদান রয়েছে যা নিজেই গাছ। ইন-মেমরি উপাদানটি ডিস্ক উপাদানগুলির সাথে একীভূত হওয়ার চেয়ে ইন-মেমরি উপাদানটি তার সর্বোচ্চ আকারে না পৌঁছানো পর্যন্ত উপাদানগুলি ইন-মেমরি উপাদানটিতে ঢোকানো হয়। অনুসন্ধানের গতি বাড়ানোর জন্য অনেক এল. এস. এম-গাছ ব্লুম ফিল্টার বা কোয়েন্ট ফিল্টারের মতো এ. এম. কিউ-ফিল্টার প্রয়োগ করে। এই ফিল্টারগুলি প্রতিটি উপাদানের জন্য আনুমানিক কোন উপাদানগুলি এতে সংরক্ষণ করা হয়। এলএসএম-গাছগুলি অ্যাপাচি অ্যাস্টেরিক্সডিবি, বিগটেবল, এইচবেস, লেভেলডিবি, এসকিউএলাইট 4-এর মতো ডাটাবেসে ব্যবহৃত হয়। নেটওয়ার্কগুলি এএমকিউ-ফিল্টারগুলির জন্য প্রচুর অ্যাপ্লিকেশন সরবরাহ করে। এগুলি একটি ভিন্ন সার্ভারে অবস্থিত ডেটার একটি সেট আনুমানিক করতে ব্যবহৃত হয়। অনেক ক্ষেত্রে এই এ. এম. কিউ-ফিল্টারগুলিকে অপরিবর্তনীয় হিসাবে দেখা যেতে পারে। এমনকি রিমোট সার্ভারের সেট পরিবর্তন হলেও এএমকিউ-ফিল্টার প্রায়শই অবিলম্বে আপডেট করা হয় না, তবে কিছু মিথ্যা পজিটিভ সহ্য করা হয়। এই অ্যাপ্লিকেশনের একটি উদাহরণ হল ওয়েব ক্যাশে শেয়ারিং। যদি কোনও প্রক্সিতে ক্যাশ মিস থাকে তবে এটি নির্ধারণ করতে চায় যে অন্য কোনও প্রক্সিতে অনুরোধ করা ডেটা রয়েছে কিনা। অতএব, প্রক্সিকে অবশ্যই জানতে হবে বা কমপক্ষে আনুমানিক অনুমান করতে হবে যে অন্য কোনও প্রক্সি অনুরোধ করা ওয়েব পৃষ্ঠাটি ধারণ করে কিনা। ইউআরএল তালিকা সম্প্রচারের পরিবর্তে প্রক্সি ক্যাশে করা ওয়েব পৃষ্ঠাগুলির ইউআরএলগুলির একটি স্থির এএমকিউ-ফিল্টার পর্যায়ক্রমে সম্প্রচার করে এটি সংরক্ষণ করা যেতে পারে। এই সেটিংসে, পর্যায়ক্রমিক আপডেটের মধ্যে ক্যাশে পরিবর্তন হলে মিথ্যা নেতিবাচক ঘটনা ঘটতে পারে। একই ধারণা পি2পি নেটওয়ার্কগুলিতে প্রয়োগ করা যেতে পারে। এএমকিউ-ফিল্টারগুলি নেটওয়ার্কের প্রতিটি নোডে কী সংরক্ষণ করা হয়েছে তার আনুমানিক অনুমান করতে ব্যবহার করা যেতে পারে। ফিল্টারটি নোডের প্রকৃত নথির আইডি বা কীওয়ার্ড দিয়ে পূরণ করা যেতে পারে। মিথ্যা ইতিবাচক শুধুমাত্র কিছু অপ্রয়োজনীয় অনুরোধের দিকে পরিচালিত করে। পি2পি নেটওয়ার্কে এএমকিউ-ফিল্টারগুলির আরও প্রয়োগ রয়েছে উদাহরণস্বরূপ বিভিন্ন নোডে সংরক্ষিত সেটগুলির মধ্যে পার্থক্য বা ছেদ খুঁজে বের করা। তথ্যসূত্র সম্ভাব্য তথ্য কাঠামো