พารามิเตอร์อินพุท
ผู้ใช้ให้พารามิเตอร์อินพุทสองตัว ได้แก่ เกณฑ์ min support threshold, σ (sigma) และ error bound ก่อนหน้า (error bound) ที่ระบุเป็น ε (epsilon) สตรีมที่เข้ามา (incoming stream) ถูกแบ่งทฤษฎี (theoretically divided) เป็น buckets (ถัง) ที่มีความกว้าง w = [1/ε]
ให้ N เป็นความยาวสตรีมปัจจุบัน (current stream length) คือ จำนวนไอเทมที่มองเห็นไปแล้วจนถึงตอนนี้ อัลกอริทึมต้องการโครงสร้างข้อมูล frequency-list (รายการความถี่) สำหรับทุกองค์ประกอบที่มีความถี่มากกว่า 0 สำหรับแต่ละไอเทม รายการเก็บ f (approximate frequency count - จำนวนความถี่ประมาณ) และ Δ (maximum possible error ของ f - ความผิดพลาดสูงสุดที่เป็นไปได้ของ f)
ขั้นตอนการประมวลผล Buckets
อัลกอริทึมประมวลผล buckets ของไอเทมดังนี้ เมื่อ bucket ใหม่มาถึง ไอเทมใน bucket จะถูกเพิ่มเข้า frequency list หากไอเทมที่กำหนดมีอยู่ในรายการแล้ว เพียงแค่เพิ่ม frequency count f ของมัน มิฉะนั้น เพิ่มมันเข้าไปในรายการด้วย frequency count 1 หากไอเทมใหม่นั้นมาจาก bucket ที่ b (bth bucket) ตั้งค่า Δ (maximum possible bug บน frequency count ของไอเทม) ให้เป็น b−1
ทุกครั้งที่ถึงขอบเขต bucket (bucket boundary) (คือ N ถึงจำนวนคูณของความกว้าง w เช่น w, 2w, 3w เป็นต้น) frequency list จะถูกกำหนด (determined) ให้ b เป็นหมายเลข bucket ปัจจุบัน รายการไอเทม (item entry) จะถูกลบ (removed) หากสำหรับรายการนั้น f + Δ ≤ b ในแนวทางนี้ อัลกอริทึมมุ่งรักษา frequency list ให้เล็ก เพื่อให้พอดีกับ primary memory (หน่วยความจำหลัก) Frequency count ที่จัดเก็บสำหรับแต่ละไอเทมจะเป็น true frequency (ความถี่จริง) ของไอเทมหรือน้อยกว่า
การวิเคราะห์ Approximation Ratio
ปัจจัยสำคัญใน approximation algorithms คือ approximation ratio (หรือ error bound) มาดูกรณีที่ไอเทมถูกลบ ซึ่งเกิดขึ้นเมื่อ f + Δ ≤ b สำหรับไอเทมหนึ่ง โดยที่ b คือหมายเลข bucket ปัจจุบัน
สามารถเห็นได้ว่า b ≤ N/w นั่นคือ b ≤ εN ความถี่จริงของไอเทมสูงสุดคือ f+Δ ดังนั้น ไอเทมสามารถลดลงได้ถึง εN หาก true support ของไอเทมนี้คือ σ (นี่คือ minimum support หรือ lower bound สำหรับมันที่จะถูกมองว่า frequent) ดังนั้น actual frequency คือ σN และ frequency f บน frequency list ควรจะเป็นอย่างน้อย (σN − εN)
ดังนั้น หากเรา output ไอเทมทั้งหมดใน frequency list ที่มีค่า f อย่างน้อย (σN − εN) ดังนั้น frequent items บางส่วนจะถูก output นอกจากนี้ subfrequent items (ที่มี actual frequency อย่างน้อย σN − εN แต่น้อยกว่า σN) ก็จะถูก output ด้วย
