خوارزمية العد مع فقدان البيانات

خوارزمية العد مع فقدان البيانات هي خوارزمية لتحديد العناصر في تدفق البيانات التي يتجاوز تكرارها عتبة يحددها المستخدم. تعمل الخوارزمية بتقسيم تدفق البيانات إلى مجموعات للعناصر المتكررة، مع ملء أكبر عدد ممكن من هذه المجموعات في الذاكرة الرئيسية دفعة واحدة. لا يكون التكرار المحسوب بهذه الخوارزمية دقيقًا دائمًا، ولكنه يخضع لعتبة خطأ يمكن للمستخدم تحديدها. يتناسب وقت التشغيل والمساحة المطلوبة للخوارزمية عكسيًا مع عتبة الخطأ المحددة؛ وبالتالي، كلما زاد الخطأ، قلّ حجم البيانات المطلوبة .

ابتكر هذه الخوارزمية عالما الحاسوب راجيف موتاني وجورميت سينغ مانكو. وتُستخدم في العمليات الحسابية التي تتخذ فيها البيانات شكل تدفق بيانات مستمر بدلاً من مجموعة بيانات محدودة ، مثل قياسات حركة مرور الشبكة ، وسجلات خادم الويب ، ومسارات النقرات .

الخوارزمية العامة هي كما يلي ^{[ 1 ]}

• الخطوة 1: قسّم تدفق البيانات الواردة إلى مجموعات بعرض${\displaystyle w=1/\epsilon }$، أين${\displaystyle \epsilon }$يذكر المستخدم أن هذا هو حد الخطأ (إلى جانب الحد الأدنى للدعم =${\displaystyle \sigma }$).
• الخطوة الثانية: قم بزيادة عدد مرات ظهور كل عنصر وفقًا لقيم المجموعة الجديدة. بعد كل مجموعة، قم بإنقاص جميع العدادات بمقدار 1.
• الخطوة 3: كرر - قم بتحديث العدادات وبعد كل مجموعة، قم بإنقاص جميع العدادات بمقدار 1.