خوارزمية البث

في علوم الحاسوب ، تعالج خوارزميات معالجة البيانات المتدفقة تدفقات البيانات المدخلة كسلسلة من العناصر، وعادةً ما تُجري مرورًا واحدًا (أو بضعة مرورات) عبر البيانات. صُممت هذه الخوارزميات للعمل بذاكرة محدودة، وعادةً ما يكون حجم التدفق و/أو القيمة القصوى فيه لوغاريتميًا ، وقد يكون وقت معالجة كل عنصر محدودًا أيضًا.

ونتيجة لهذه القيود، غالباً ما تنتج خوارزميات البث إجابات تقريبية بناءً على ملخص أو "رسم تخطيطي" لتدفق البيانات.

تاريخ

^{على الرغم من أن مونرو وباترسون [ 1 ]} قد درسا خوارزميات تدفق البيانات منذ عام 1978، وكذلك فيليب فلاجو وجي. نايجل مارتن في عامي 1982/1983 ^{[ 2 ]،} إلا أن مجال خوارزميات تدفق البيانات قد تم صياغته ونشره لأول مرة في ورقة بحثية نُشرت عام 1996 من قِبل نوغا ألون ، ويوسي ماتياس ، وماريو سيجيدي ^{[ 3 ]} . وقد فاز مؤلفو هذه الورقة بجائزة غودل عام 2005 "لمساهمتهم الأساسية في خوارزميات تدفق البيانات". ومنذ ذلك الحين، ظهرت مجموعة كبيرة من الأبحاث التي تركز على خوارزميات تدفق البيانات، والتي تغطي طيفًا واسعًا من مجالات علوم الحاسوب، مثل النظرية، وقواعد البيانات، والشبكات، ومعالجة اللغات الطبيعية .

طُرحت خوارزميات شبه التدفق في عام 2005 كتحسين لخوارزميات التدفق للرسوم البيانية، ^{[ 4 ]} حيث تكون المساحة المسموح بها خطية بالنسبة لعدد الرؤوس n ، ولكنها لوغاريتمية فقط بالنسبة لعدد الحواف m . لا يزال هذا التحسين ذا أهمية للرسوم البيانية الكثيفة، ويمكنه حل مشكلات مهمة (مثل الاتصال) غير قابلة للحل في $o(n)$ فضاء.

نماذج

نموذج تدفق البيانات

في نموذج تدفق البيانات، يُمثَّل جزء من المدخلات أو كلها كسلسلة محدودة من الأعداد الصحيحة (من نطاق محدود) لا يمكن الوصول إليها عشوائيًا ، بل تصل عنصرًا تلو الآخر في "تدفق". ^{[ 5 ]} إذا كان طول التدفق n وحجم النطاق m ، فإن الخوارزميات مقيدة عمومًا باستخدام مساحة تتناسب لوغاريتميًا مع m و n . ويمكنها عادةً إجراء عدد ثابت صغير فقط من المرورات على التدفق، وأحيانًا مرة واحدة فقط . ^{[ 6 ]}

نماذج البوابات الدوارة وآلات تسجيل النقد

يركز جزء كبير من الأدبيات المتعلقة بالتدفق على حساب الإحصاءات المتعلقة بتوزيعات الترددات التي يصعب تخزينها نظرًا لكبر حجمها. بالنسبة لهذا النوع من المشكلات، يوجد متجه $\mathbf {a} =(a_{1},\dots ,a_{n})$ (تمت تهيئته إلى متجه الصفر) $\mathbf {0}$ ) التي تُعرض عليها التحديثات في تدفق. هدف هذه الخوارزميات هو حساب وظائف $\mathbf {a}$ باستخدام مساحة أقل بكثير مما يتطلبه تمثيل $\mathbf {a}$ بالضبط. هناك نموذجان شائعان لتحديث هذه التدفقات، يُطلق عليهما نموذج "سجل النقد" ونموذج "البوابة الدوارة". ^{[ 7 ]}

في نموذج آلة تسجيل النقد، يكون كل تحديث على الشكل التالي: $\langle i,c\rangle$ ، لهذا السبب $a_{i}$ يتم زيادته بمقدار عدد صحيح موجب $c$ ومن الحالات الخاصة البارزة عندما $c=1$ (يُسمح فقط بإدخال الوحدات).

في نموذج البوابة الدوارة، يكون كل تحديث على الشكل التالي: $\langle i,c\rangle$ ، لهذا السبب $a_{i}$ يتم زيادته بمقدار عدد صحيح (قد يكون سالباً). $c$ في نموذج "البوابة الدوارة الصارمة"، لا $a_{i}$ قد تكون قيمتها في أي وقت أقل من الصفر.

نموذج النافذة المنزلقة

تتناول العديد من الأبحاث نموذج "النافذة المنزلقة". في هذا النموذج، تتمثل الوظيفة محل الاهتمام في إجراء العمليات الحسابية على نافذة ذات حجم ثابت في التدفق. ومع تقدم التدفق، تُزال العناصر من نهاية النافذة من الحسابات، بينما تحل محلها عناصر جديدة من التدفق.

إلى جانب المسائل المذكورة أعلاه القائمة على التردد، دُرست أنواع أخرى من المسائل. تُحل العديد من مسائل الرسوم البيانية في حالة تدفق مصفوفة التجاور أو قائمة التجاور للرسم البياني بترتيب غير معروف. كما توجد مسائل أخرى تعتمد بشكل كبير على ترتيب التدفق (أي الدوال غير المتناظرة)، مثل حساب عدد الانعكاسات في التدفق وإيجاد أطول متتالية فرعية متزايدة.

تقييم

يتم قياس أداء الخوارزمية التي تعمل على تدفقات البيانات من خلال ثلاثة عوامل أساسية:

عدد مرات المرور التي يجب أن تقوم بها الخوارزمية على التدفق.
الذاكرة المتاحة.
زمن تشغيل الخوارزمية.

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

إذا كانت الخوارزمية خوارزمية تقريبية، فإن دقة الإجابة تُعد عاملاً رئيسياً آخر. وغالبًا ما تُعبر عن الدقة بـ $(\epsilon ,\delta )$ التقريب يعني أن الخوارزمية تحقق خطأً أقل من $\epsilon$ باحتمال $1-\delta$ .

التطبيقات

تُستخدم خوارزميات البث في العديد من تطبيقات الشبكات ، مثل مراقبة روابط الشبكة بحثًا عن تدفقات البيانات الضخمة ، وحساب عدد التدفقات المتميزة، وتقدير توزيع أحجام التدفقات، وما إلى ذلك. ^{[ 8 ]} كما تُستخدم أيضًا في قواعد البيانات، مثل تقدير حجم عملية الربط .

بعض مشاكل البث

لحظات التردد

العزم الترددي رقم $k$ لمجموعة من الترددات $\mathbf {a}$ يُعرَّف بأنه $F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}$ .

اللحظة الأولى $F_{1}$ هو ببساطة مجموع التكرارات (أي العدد الإجمالي). العزم الثاني $F_{2}$ وهو مفيد لحساب الخصائص الإحصائية للبيانات، مثل معامل جيني للتباين. $F_{\infty }$ يُعرَّف بأنه تكرار العناصر الأكثر تكرارًا.

تناولت الورقة البحثية الرائدة لألون وماتياس وسيجيدي مشكلة تقدير لحظات التردد.

حساب عزم التردد

يتطلب النهج المباشر لإيجاد لحظات التردد الاحتفاظ بسجل $m i$ لجميع العناصر المتميزة $a i \in (1,2,3,4,..., N)$ ، وهو ما يتطلب على الأقل ذاكرة من رتبة $\Omega (N)$ [ ³^] لكن لدينا قيود على المساحة، ونحتاج إلى خوارزمية تحسب باستخدام ذاكرة أقل بكثير. يمكن تحقيق ذلك باستخدام التقريبات بدلًا من القيم الدقيقة. خوارزمية تحسب تقريبًا ( ^ε $,$ δ ) لـ $Fk$ $،$ حيث $F'k هي القيمة التقريبية$ $لـ$ $Fk$ باستخدام ( ε,δ ) . ^[⁹^] حيث ε هو معامل التقريب و δ هو معامل الثقة. ^[¹⁰^]

حساب F ₀ (العناصر المميزة في تدفق البيانات)

خوارزمية رسم FM

قدّم فلاجو وآخرون في ^{[ 2 ]} طريقة احتمالية للعدّ مستوحاة من ورقة بحثية لروبرت موريس . ^{[ 11 ]} يذكر موريس في ورقته أنه في حال التخلي عن شرط الدقة، يمكن استبدال العداد n بعداد $log n$ الذي يمكن تخزينه في $log log n$ بت. ^{[ 12 ]} حسّن فلاجو وآخرون في ^{[ 2 ]} هذه الطريقة باستخدام دالة تجزئة $h،$ والتي يُفترض أنها توزع العنصر بشكل منتظم في فضاء التجزئة (سلسلة ثنائية طولها $L$ ).

h:[m]\rightarrow [0,2^{L}-1]

لنفترض أن $bit(y,k)$ يمثل البت رقم k في التمثيل الثنائي لـ $y$

y=\sum _{k\geq 0}\mathrm {bit} (y,k)*2^{k}

يترك $\rho (y)$ يمثل موضع البت الأقل أهمية (1) في التمثيل الثنائي لـ $y i$ وفقًا لاتفاقية مناسبة لـ $\rho (0)$ .

\rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}

ليكن A سلسلة من تدفقات البيانات بطول M والتي يلزم تحديد عدد عناصرها. ولتكن BITMAP [0... L − 1] هي

مساحة التجزئة حيث يتم تسجيل قيم التجزئة ( $ρ$ ). ثم تحدد الخوارزمية أدناه العدد التقريبي لعناصر المصفوفة A.

مخطط الإجراء FM: لكل i في 0 إلى L − 1 نفّذ BITMAP[i] := 0 نهاية لـ لكل عنصر x في المجموعة A: نفّذ Index := ρ(hash(x)) إذا كان BITMAP[index] = 0 فإن BITMAP[index] := 1 نهاية الشرط نهاية لـ B := موضع البت 0 الأيسر من BITMAP[] إرجاع 2 ^ ب

إذا كان هناك N عنصرًا مميزًا في تدفق البيانات.

ل $i\gg \log(N)$ إذن فإن BITMAP [ i ] يساوي بالتأكيد 0
ل $i\ll \log(N)$ إذن فإن BITMAP [ i ] هو بالتأكيد 1
ل $i\approx \log(N)$ إذن ، BITMAP [ i ] عبارة عن مجموعة من الأصفار والآحاد.

خوارزمية القيمة الدنيا K

تصف الخوارزمية السابقة المحاولة الأولى لتقريب F ₀ في تدفق البيانات بواسطة فلاجو ومارتن. تختار خوارزميتهم دالة تجزئة عشوائية يفترضون أنها توزع قيم التجزئة بشكل منتظم في فضاء التجزئة.

قدّم بار يوسف وآخرون في ^{[ 10 ]} خوارزمية القيمة الدنيا k لتحديد عدد العناصر المميزة في تدفق البيانات. استخدموا دالة تجزئة مماثلة h يمكن تطبيعها إلى [0,1] كـ $h:[m]\rightarrow [0,1]$ لكنهم حددوا حدًا أقصى t لعدد القيم في فضاء التجزئة. ويُفترض أن قيمة t من الرتبة $O\left({\dfrac {1}{\varepsilon _{2}}}\right)$ (أي أن قيمة التقريب ε الأقل تتطلب قيمة t أكبر ). تحتفظ خوارزمية KMV بأصغر t قيمة تجزئة فقط في فضاء التجزئة. بعد وصول جميع قيم m للتدفق، $\upsilon =\mathrm {Max} (h(a_{i}))$ تُستخدم لحساب $F'_{0}={\dfrac {t}{\upsilon }}$ أي أنه في فضاء تجزئة شبه منتظم، يتوقعون أن يكون عدد العناصر التي تقل عن t أقل من $O\left({\dfrac {t}{F_{0}}}\right)$ .

الإجراء 2 - القيمة الدنيا K قم بتهيئة القيم الأولى لـ KMV for a in a1 to an do إذا كانت h(a) < Max(KMV) فإن قم بإزالة Max(KMV) من مجموعة KMV أدخل h(a) في KMV نهاية الشرط نهاية لـ أعد t/Max(KMV)

تحليل تعقيد KMV

يمكن تطبيق خوارزمية KMV في $O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)$ مساحة بتات الذاكرة. تتطلب كل قيمة تجزئة مساحة من رتبة $O(\log(m))$ بتات الذاكرة. توجد قيم تجزئة من الرتبة $O\left({\dfrac {1}{\varepsilon _{2}}}\right)$ يمكن تقليل وقت الوصول إذا قمنا بتخزين قيم التجزئة t في شجرة ثنائية . وبالتالي، سيتم تقليل التعقيد الزمني إلى $O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)$ .

حساب $F k$

يُقدّر ألون وآخرون قيمة $F k$ بتعريف متغيرات عشوائية يمكن حسابها ضمن مساحة وزمن محددين. ^{[ 3 ]} القيمة المتوقعة للمتغيرات العشوائية تعطي القيمة التقريبية لـ $F k$ .

بافتراض أن طول المتتالية m معروف مسبقًا، قم بإنشاء متغير عشوائي X على النحو التالي:

اختر $عنصرًا$ عشوائيًا من المتتالية $A،$ $ويكون$ فهرسه عند $p$ . $a_{p}=l\in (1,2,3,\ldots ,n)$
يترك $r=|\{q:q\geq p,a_{q}=l\}|$ ، يمثل عدد مرات ظهور الحرف $l$ ضمن عناصر التسلسل $A$ بعد $الحرف p$ .
متغير عشوائي $X=m(r^{k}-(r-1)^{k})$ .

افترض أن S ₁ من الرتبة $O(n^{1-1/k}/\lambda ^{2})$ ويكون S ₂ من رتبة $O(\log(1/\varepsilon ))$ تأخذ الخوارزمية متغيرًا عشوائيًا S ₂ $Y_{1},Y_{2},...,Y_{S2}$ ويُخرج الوسيط $Y$ حيث $Y i$ هو متوسط $X ij$ حيث 1 ≤ j ≤ S ₁ .

الآن احسب القيمة المتوقعة للمتغير العشوائي $E (X)$ .

{\begin{array}{lll}E(X)&=&\sum _{i=1}^{n}\sum _{i=1}^{m_{i}}(j^{k}-(j-1)^{k})\\&=&{\frac {m}{m}}[(1^{k}+(2^{k}-1^{k})+\ldots +(m_{1}^{k}-(m_{1}-1)^{k}))\\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{2}^{k}-(m_{2}-1)^{k}))+\ldots \\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{n}^{k}-(m_{n}-1)^{k}))]\\&=&\sum _{i=1}^{n}m_{i}^{k}=F_{k}\end{array}}

تعقيد $F k$

من خلال الخوارزمية المستخدمة لحساب $F k$ المذكورة أعلاه، نلاحظ أن كل متغير عشوائي $X$ يخزن قيمتي $p$ و $r$ . لذا، لحساب $X،$ $نحتاج$ فقط إلى الاحتفاظ $بـ$ $log(n)$ بت لتخزين $p$ و $log(n)$ بت لتخزين $r$ . سيكون العدد الإجمالي للمتغيرات العشوائية $X هو$ ⁠ $S_{1}*S_{2}$ ⁠ .

وبالتالي فإن إجمالي تعقيد المساحة الذي تتطلبه الخوارزمية هو من رتبة $O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)$

طريقة أبسط لحساب $F 2$

تقوم الخوارزمية السابقة بالحساب $F_{2}$ حسب ترتيب $O({\sqrt {n}}(\log m+\log n))$ بتات الذاكرة. قام ألون وآخرون في ^{[ 3 ]} بتبسيط هذه الخوارزمية باستخدام متغير عشوائي مستقل رباعيًا بقيم مُعينة إلى $\{-1,1\}$ .

وهذا يقلل من تعقيد عملية الحساب $F_{2}$ ل $O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)$

العناصر المتكررة

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

بصورة أدق، لنفترض وجود ثابت موجب c > 1، وطول السلسلة m ، وتكرار القيمة _i في السلسلة fᵢ . تتمثل مشكلة العناصر المتكررة في إخراج المجموعة { i | fᵢ ^>_m /c }. ^[¹³ ]

من بين الخوارزميات البارزة ما يلي:

اكتشاف الأحداث

غالبًا ما يتم الكشف عن الأحداث في تدفقات البيانات باستخدام خوارزمية العناصر الأكثر تكرارًا كما هو موضح أعلاه: حيث تُحدد العناصر الأكثر تكرارًا وتكرارها باستخدام إحدى هذه الخوارزميات، ثم يُسجل أكبر ارتفاع مقارنةً بالنقطة الزمنية السابقة كاتجاه. ويمكن تحسين هذا النهج باستخدام المتوسطات المتحركة الموزونة أُسّيًا والتباين للتطبيع. ^{[ 14 ]}

عد العناصر المميزة

يُعدّ حساب عدد العناصر المتميزة في تدفق البيانات (والذي يُسمى أحيانًا $لحظة$ $F0$ ) مشكلة أخرى حظيت بدراسة وافية. وقد اقترح فلاجو ومارتن أول خوارزمية لحل هذه المشكلة. وفي عام 2010، وجد دانيال كين وجيلاني نيلسون وديفيد وودروف خوارزمية مثالية تقاربياً لحل هذه المشكلة. ^{[ 15 ]} تستخدم هذه الخوارزمية مساحة $O (ε² + log d) ، مع أوقات تحديث وإبلاغ في أسوأ الحالات$ $O (1)$ $،$ بالإضافة إلى دوال تجزئة شاملة وعائلة تجزئة مستقلة على مستوى $r$ حيث $r = Ω(log(1/ ε) / log log(1/ ε))$ .

إنتروبيا

الإنتروبيا (التجريبية) لمجموعة من الترددات $\mathbf {a}$ يُعرَّف بأنه $F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}$ ، أين $m=\sum _{i=1}^{n}a_{i}$ .

التعلم عبر الإنترنت

تعلم نموذجًا (مثل المصنف ) من خلال تمريرة واحدة على مجموعة التدريب.

الحدود الدنيا

تم حساب الحدود الدنيا للعديد من مشاكل تدفق البيانات التي تمت دراستها. وتُعد تقنية تعقيد الاتصال هي الأكثر شيوعًا لحساب هذه الحدود الدنيا .

انظر أيضاً

ملحوظات

↑ مونرو، ج. إيان؛ باترسون، مايك (1978). "الاختيار والفرز مع سعة تخزين محدودة". الندوة السنوية التاسعة عشرة حول أسس علوم الحاسوب، آن أربور، ميشيغان، الولايات المتحدة الأمريكية، 16-18 أكتوبر 1978. جمعية مهندسي الكهرباء والإلكترونيات (IEEE). الصفحات 253-258 . doi : 10.1109/SFCS.1978.32 .
1 2 3 فلاجو ومارتن (1985)
1 2 3 4 ألون، ماتياس وسيجيدي (1996)
↑ فيجنباوم، جوان؛ سامباث، كانان (2005). "حول مسائل الرسوم البيانية في نموذج شبه متدفق" . علوم الحاسوب النظرية . 348 (2): 207-216 . doi : 10.1016/j.tcs.2005.09.013 .
↑ بابكوك، برايان؛ بابو، شيفناث؛ داتار، مايور؛ موتاني، راجيف؛ ويدوم، جينيفر (2002). "نماذج وقضايا في أنظمة تدفق البيانات". وقائع الندوة الحادية والعشرين لجمعية ACM SIGMOD-SIGACT-SIGART حول مبادئ أنظمة قواعد البيانات . PODS '02. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 1-16 . CiteSeerX 10.1.1.138.190 . doi : 10.1145/543613.543615 . ISBN 978-1-58113-507-7. S2CID 2071130 .
↑ بار يوسف، زيف؛ جايرام، تي إس؛ كومار، رافي؛ سيفاكومار، د.؛ تريفيسان، لوكا (13-09-2002). "حساب العناصر المميزة في تدفق البيانات". تقنيات العشوائية والتقريب في علوم الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 2483. سبرينغر، برلين، هايدلبرغ. الصفحات 1-10 . CiteSeerX 10.1.1.12.6276 . doi : 10.1007/3-540-45726-7_1 . ISBN 978-3-540-45726-8. S2CID 4684185 .
↑ جيلبرت وآخرون (2001)
↑ شو (2007)
↑ إنديك، بيوتر؛ وودروف، ديفيد (1 يناير 2005). "التقريبات المثلى لعزوم التردد لتدفقات البيانات". وقائع الندوة السنوية السابعة والثلاثين لجمعية ACM حول نظرية الحوسبة . STOC '05. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 202-208 . doi : 10.1145/1060590.1060621 . ISBN 978-1-58113-960-0. S2CID 7911758 .
١ ٢ بار يوسف، زيف؛ جايرام، تي إس؛ كومار، رافي؛ سيفاكومار، دي؛ تريفيسان، لوكا (١٣-٠٩-٢٠٠٢). روليم، خوسيه دي بي؛ فادان، ساليل (محررون). عد العناصر المميزة في تدفق البيانات . سلسلة محاضرات في علوم الحاسوب. سبرينغر برلين هايدلبرغ. ص ١-١٠ . CiteSeerX 10.1.1.12.6276 . doi : 10.1007/3-540-45726-7_1 . ISBN 978-3-540-44147-2. S2CID 4684185 .
↑ موريس (1978)
↑ فلاجو، فيليب (1985-03-01). "العد التقريبي: تحليل مفصل". مجلة BIT للرياضيات العددية . 25 (1): 113-134 . CiteSeerX 10.1.1.64.5320 . doi : 10.1007/BF01934993 . ISSN 0006-3835 . S2CID 2809103 .
↑ كورمود، غراهام (2014). "ملخصات ميسرا-غريس". في: كاو، مينغ-يانغ (محرر). موسوعة الخوارزميات . سبرينغر الولايات المتحدة. ص 1-5 . doi : 10.1007/978-3-642-27848-8_572-1 . ISBN 978-3-642-27848-8.
↑ شوبرت، إي.؛ ويلر، إم.؛ كريجل، إتش بي (2014). SigniTrend: كشف قابل للتوسع للمواضيع الناشئة في تدفقات النصوص باستخدام عتبات الأهمية المُجزأة . وقائع المؤتمر الدولي العشرين لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات - KDD '14. الصفحات 871-880 . doi : 10.1145/2623330.2623740 . ISBN 978-1-4503-2956-9.
↑ كين، نيلسون وودروف (2010)

مراجع

ألون، نوغا ؛ ماتياس، يوسي ؛ سيجيدي، ماريو (1999)، "التعقيد المكاني لتقريب لحظات التردد"، مجلة علوم الحاسوب والأنظمة ، 58 (1): 137-147 ، doi : 10.1006/jcss.1997.1545 ، ISSN 0022-0000 نُشرت لأول مرة بعنوان: Alon, Noga; Matias, Yossi; Szegedy, Mario (1996)، "التعقيد المكاني لتقريب لحظات التردد"، وقائع الندوة الثامنة والعشرين لجمعية الحوسبة الآلية حول نظرية الحوسبة (STOC 1996) ، الصفحات 20-29 ، CiteSeerX 10.1.1.131.4984 ، doi : 10.1145/237814.237823 ، ISBN 978-0-89791-785-8، S2CID 1627911 .
بابكوك، برايان؛ بابو، شيفناث؛ داتار، مايور؛ موتاني، راجيف ؛ ويدوم، جينيفر (2002)، "نماذج وقضايا في أنظمة تدفق البيانات"، وقائع ندوة ACM SIGMOD-SIGACT-SIGART الحادية والعشرين حول مبادئ أنظمة قواعد البيانات (PODS 2002) (ملف PDF) ، الصفحات 1-16 ، CiteSeerX 10.1.1.138.190 ، doi : 10.1145/543613.543615 ، ISBN 978-1-58113-507-7، S2CID 2071130 ، مؤرشف من النسخة الأصلية (PDF) بتاريخ 2017-07-09 ، تم استرجاعه بتاريخ 2013-07-15 .
فلاجو، فيليب؛ مارتن، جي. نايجل (1985). "خوارزميات العد الاحتمالية لتطبيقات قواعد البيانات" (ملف PDF) . مجلة علوم الحاسوب والنظم . 31 (2): 182-209 . doi : 10.1016/0022-0000(85)90041-8 . تاريخ الاسترجاع: 11 ديسمبر 2016 .
جيلبرت، أ.س .؛ كوتيديس، ي.؛ موثوكريشنان، س .؛ شتراوس، م.ج. (2001)، "تصفح الموجات الصغيرة على التدفقات: ملخصات المرور الواحد لاستعلامات التجميع التقريبية" (ملف PDF) ، وقائع المؤتمر الدولي لقواعد البيانات الضخمة جدًا : 79-88.
كين، دانيال م.؛ نيلسون، جيلاني؛ وودروف، ديفيد ب. (2010). "خوارزمية مثلى لمسألة العناصر المتميزة". وقائع الندوة التاسعة والعشرين لجمعية ACM SIGMOD-SIGACT-SIGART حول مبادئ أنظمة قواعد البيانات . PODS '10. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 41-52 . CiteSeerX 10.1.1.164.142 . doi : 10.1145/1807085.1807094 . ISBN 978-1-4503-0033-9. S2CID 10006932 . .
كارب، آر إم ؛ باباديميتريو، سي إتش ؛ شينكر، إس. (2003)، "خوارزمية بسيطة لإيجاد العناصر المتكررة في التدفقات والحقائب"، معاملات ACM لأنظمة قواعد البيانات ، 28 (1): 51-55 ، CiteSeerX 10.1.1.116.8530 ، doi : 10.1145/762471.762473 ، S2CID 952840 .
لال، أشوين؛ سيكار، فياس؛ أوجيهارا، ميتسونوري؛ شو، جون؛ تشانغ، هوي (2006). "خوارزميات تدفق البيانات لتقدير إنتروبيا حركة مرور الشبكة". وقائع المؤتمر الدولي المشترك حول قياس ونمذجة أنظمة الحاسوب (ACM SIGMETRICS 2006) . ص 145. doi : 10.1145/1140277.1140295 . hdl : 1802/2537 . ISBN 978-1-59593-319-5. S2CID 240982 . .
شو، جون (جيم) (2007)، دليل تعليمي حول بث البيانات عبر الشبكة (PDF).
هيث، د.، كاسيف، س.، كوساراجو، ر.، سالزبرغ، س.، سوليفان، ج.، "تعلم المفاهيم المتداخلة مع سعة تخزين محدودة"، وقائع المؤتمر الدولي المشترك الثاني عشر حول الذكاء الاصطناعي IJCAI'91 - المجلد 2، الصفحات 777-782، دار نشر مورغان كوفمان، سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية ©1991
موريس، روبرت (1978)، "إحصاء أعداد كبيرة من الأحداث في سجلات صغيرة"، اتصالات رابطة آلات الحوسبة ، 21 (10): 840-842 ، doi : 10.1145/359619.359627 ، S2CID 36226357 .

[1] مونرو، ج. إيان؛ باترسون، مايك (1978). "الاختيار والفرز مع سعة تخزين محدودة". الندوة السنوية التاسعة عشرة حول أسس علوم الحاسوب، آن أربور، ميشيغان، الولايات المتحدة الأمريكية، 16-18 أكتوبر 1978. جمعية مهندسي الكهرباء والإلكترونيات (IEEE). الصفحات 253-258 . doi : 10.1109/SFCS.1978.32 .

[:0-2] 1 2 3 فلاجو ومارتن (1985)

[:1-3] 1 2 3 4 ألون، ماتياس وسيجيدي (1996)

[4] فيجنباوم، جوان؛ سامباث، كانان (2005). "حول مسائل الرسوم البيانية في نموذج شبه متدفق" . علوم الحاسوب النظرية . 348 (2): 207-216 . doi : 10.1016/j.tcs.2005.09.013 .

[5] بابكوك، برايان؛ بابو، شيفناث؛ داتار، مايور؛ موتاني، راجيف؛ ويدوم، جينيفر (2002). "نماذج وقضايا في أنظمة تدفق البيانات". وقائع الندوة الحادية والعشرين لجمعية ACM SIGMOD-SIGACT-SIGART حول مبادئ أنظمة قواعد البيانات . PODS '02. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 1-16 . CiteSeerX 10.1.1.138.190 . doi : 10.1145/543613.543615 . ISBN 978-1-58113-507-7. S2CID 2071130 .

[6] بار يوسف، زيف؛ جايرام، تي إس؛ كومار، رافي؛ سيفاكومار، د.؛ تريفيسان، لوكا (13-09-2002). "حساب العناصر المميزة في تدفق البيانات". تقنيات العشوائية والتقريب في علوم الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 2483. سبرينغر، برلين، هايدلبرغ. الصفحات 1-10 . CiteSeerX 10.1.1.12.6276 . doi : 10.1007/3-540-45726-7_1 . ISBN 978-3-540-45726-8. S2CID 4684185 .

[turnstile-7] جيلبرت وآخرون (2001)

[8] شو (2007)

[9] إنديك، بيوتر؛ وودروف، ديفيد (1 يناير 2005). "التقريبات المثلى لعزوم التردد لتدفقات البيانات". وقائع الندوة السنوية السابعة والثلاثين لجمعية ACM حول نظرية الحوسبة . STOC '05. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 202-208 . doi : 10.1145/1060590.1060621 . ISBN 978-1-58113-960-0. S2CID 7911758 .

[:2-10] ١ ٢ بار يوسف، زيف؛ جايرام، تي إس؛ كومار، رافي؛ سيفاكومار، دي؛ تريفيسان، لوكا (١٣-٠٩-٢٠٠٢). روليم، خوسيه دي بي؛ فادان، ساليل (محررون). عد العناصر المميزة في تدفق البيانات . سلسلة محاضرات في علوم الحاسوب. سبرينغر برلين هايدلبرغ. ص ١-١٠ . CiteSeerX 10.1.1.12.6276 . doi : 10.1007/3-540-45726-7_1 . ISBN 978-3-540-44147-2. S2CID 4684185 .

[11] موريس (1978)

[12] فلاجو، فيليب (1985-03-01). "العد التقريبي: تحليل مفصل". مجلة BIT للرياضيات العددية . 25 (1): 113-134 . CiteSeerX 10.1.1.64.5320 . doi : 10.1007/BF01934993 . ISSN 0006-3835 . S2CID 2809103 .

[13] كورمود، غراهام (2014). "ملخصات ميسرا-غريس". في: كاو، مينغ-يانغ (محرر). موسوعة الخوارزميات . سبرينغر الولايات المتحدة. ص 1-5 . doi : 10.1007/978-3-642-27848-8_572-1 . ISBN 978-3-642-27848-8.

[14] شوبرت، إي.؛ ويلر، إم.؛ كريجل، إتش بي (2014). SigniTrend: كشف قابل للتوسع للمواضيع الناشئة في تدفقات النصوص باستخدام عتبات الأهمية المُجزأة . وقائع المؤتمر الدولي العشرين لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات - KDD '14. الصفحات 871-880 . doi : 10.1145/2623330.2623740 . ISBN 978-1-4503-2956-9.

[15] كين، نيلسون وودروف (2010)

على الرغم من أن مونرو وباترسون [ 1 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[

[ 11 ]

[ 12 ]

>

[ 14 ]

[ 15 ]