Cardinality Estimation Meets Good-Turing

الگوریتم های برآورد کاردینال یک جریان از عناصر را دریافت می کنند که ممکن است دستور آن دلخواه باشد، با تکرارهای احتمالی، و تعدادی از عناصر متمایز را بازگرداند. چنین الگوریتمهای معمولا به دنبال به حداقل رساندن ذخیره و پردازش مورد نیاز در قیمت اشتباه در خروجی خود هستند. برنامه های واقعی دنیای این الگوریتم ها برای پردازش حجم زیادی داده های نظارت شده لازم است، و برای جمع آوری و تجزیه و تحلیل کل جریان ورودی غیر عملی است. در چنین مواردی، معمولا نمونه گیری و پردازش تنها یک قسمت کوچک از عناصر جریان است. در این مقاله یک الگوریتم عمومی برای ترکیب هر الگوریتم برآورد قدرتمند با یک فرایند نمونه برداری ارائه و تحلیل می شود. ما نشان می دهیم که الگوریتم نمونه گیری پیشنهادی بر روی عدم تساوی آستانه بندی برآوردگر تأثیر نمی گذارد و اثر نمونه گیری بر روی واریانس برآوردگر را تحلیل می کنیم.