ব্যবহারকারী দুটি ইনপুট প্যারামিটার প্রদান করেন: মিন সাপোর্ট থ্রেশহোল্ড (σ) এবং এরর বাউন্ড (ε)। আগত স্ট্রিম সैদ্ধান্তিকভাবে w = ⌈1/ε⌉ প্রস্থের বালতিতে বিভক্ত হয়।
N হল বর্তমান স্ট্রিমের দৈর্ঘ্য, অর্থাৎ আজ পর্যন্ত দেখা আইটেমের সংখ্যা। অ্যালগরিদমটি একটি ফ্রিকোয়েন্সি-লিস্ট ডেটা স্ট্রাকচার ধরে রাখে সব উপাদানের জন্য যাদের ফ্রিকোয়েন্সি ০-র চেয়ে বেশি। প্রতিটি আইটেমের জন্য, লিস্টে থাকে f (অনুমানিক ফ্রিকোয়েন্সি কাউন্ট) এবং Δ (f-এর সর্বাধিক সম্ভাব্য ত্রুটি)।
অ্যালগরিদমের প্রক্রিয়া
- যখন একটি নতুন বালতি আসে, বালতির আইটেমগুলো ফ্রিকোয়েন্সি লিস্টে যোগ করা হয়।
- যদি আইটেমটি লিস্টে ইতিমধ্যে থাকে, তার ফ্রিকোয়েন্সি কাউন্ট f বাড়ানো হয়।
- অন্যথায়, ফ্রিকোয়েন্সি কাউন্ট ১ দিয়ে লিস্টে যোগ করা হয়।
- যদি নতুন আইটেম b-তম বালতি থেকে হয়, তবে Δ (আইটেমের ফ্রিকোয়েন্সি কাউন্টের সর্বাধিক সম্ভাব্য বাগ) b−1 সেট করা হয়।
যখনই একটি বালতি সীমানা পৌঁছায় (অর্থাৎ N w-এর গুণিতক হয়ে যায়, যেমন w, 2w, 3w, ইত্যাদি), ফ্রিকোয়েন্সি লিস্ট পরিশোধিত হয়। b হল বর্তমান বালতি নম্বর। একটি আইটেম এন্ট্রি মুছে ফেলা হয় যদি, সেই এন্ট্রির জন্য, f + Δ ≤ b। এই পদ্ধতিতে, অ্যালগরিদম ফ্রিকোয়েন্সি লিস্ট ছোট রাখার লক্ষ্য রাখে যাতে সেটি প্রাইমারি মেমরিতে ফিট করতে পারে। প্রতিটি আইটেমের জন্য সংরক্ষিত ফ্রিকোয়েন্সি কাউন্ট হবে আইটেমের আসল ফ্রিকোয়েন্সি বা তার চেয়ে কম।
অনুমান অনুপাত (Approximation Ratio)
অনুমান অ্যালগরিদমের অপরিহার্য ফ্যাক্টর হল অনুমান অনুপাত (বা এরর বাউন্ড)। এরো ফেলা হলে এরো দেখা যাক: f + Δ ≤ b একটি আইটেমের জন্য, যেখানে b হল বর্তমান বালতি নম্বর।
আমরা জানি b ≤ N/w, অর্থাৎ b ≤ εN। একটি আইটেমের আসল ফ্রিকোয়েন্সি সর্বোচ্চ f+Δ। তাই একটি আইটেম সর্বোচ্চ εN কমানো হতে পারে। যদি এই আইটেমের আসল সাপোর্ট σ হয় (এটি ফ্রিকোয়েন্ট বলে বিবেচিত হওয়ার জন্য ন্যূনতম সাপোর্ট বা লোয়ার বাউন্ড), তবে আসল ফ্রিকোয়েন্সি হল σN, এবং ফ্রিকোয়েন্সি লিস্টের f হবে ন্যূনতম (σN − εN)।
তাই, যদি ফ্রিকোয়েন্সি লিস্টে f মান ন্যূনতম (σN − εN) থাকা সব আইটেম আউটপুট করা হয়, তবে কিছু ফ্রিকোয়েন্ট আইটেম আউটপুট হবে। 덧붙ন্তু, কিছু সাব-ফ্রিকোয়েন্ট আইটেম (য যাদের আসল ফ্রিকোয়েন্সি ন্যূনতম σN − εN কিন্তু σN-এর চেয়ে কম)ও আউটপুট হবে।
