الگوریتم جریان داده‌ها - ویکی‌پدیا، دانشنامهٔ آزاد

در علم رایانه الگوریتم جریان داده‌ها (به انگلیسی: Streaming algorithm) الگوریتمی ست برای پردازش جریان داده‌ها که به صورت توالی از آیتم‌ها به عنوان ورودی هستند و از یک یا تعداد محدودی گذرگاه می‌توانند مورد بررسی قرار بگیرند. در واقع این الگوریتم دنباله‌ای از داده را به عنوان ورودی دریافت کرده و یک سری تابع روی آن‌ها اعمال می‌کند. این الگوریتم حافظه مورد نیاز (کمتر از اندازه واقعی خود ورودی) و زمان پردازش هر آیتم را هم محدود می‌کند. این محدودیت‌ها به این معناست که این الگوریتم جواب تقریبی بر اساس یک خلاصه یا «طرحی» از جریان داده‌ها در حافظه تولید می‌کند.

تاریخچه[ویرایش]

اگرچه مطالعه الگوریتم جریان توسط مونرو و پاترسون^[۱] دراوایل ۱۹۸۰ آغاز شد اما توسط Philippe Flajolet و نایجل مارتین در ۱۹۸۲–۱۹۸۳ باعث شد^[۲] موضوعات مرتبط به الگوریتم‌های جریان برای اولین بار به رسمیت شناخته شود و در یک مقاله در سال ۱۹۹۶ توسط نوگا آلون، یوسی ماتیاس، و ماریو^[۳] محبوب شد. نویسندگان این مقاله بعداً جایزه گودل در سال ۲۰۰۵ را «برای سهم بنیادی شان نسبت به الگوریتم‌های جریانی» کسب کردند. از آن زمان کار زیادی حول الگوریتم‌های جریان داده انجام شد که طیف متنوعی از زمینه‌های علوم کامپیوتر از قبیل تئوری، پایگاه داده، شبکه و پردازش زبان طبیعی را گسترش داد. الگوریتم‌های نیمه جریانی در سال ۲۰۰۵ به عنوان یک فرمت از الگوریتم‌های جریانی ارائه شد که برای تعداد ثابت یا لگاریتمی از گذرگاه‌ها روی مجموعهٔ داده‌ها امکان‌پذیر است.

مدل‌ها[ویرایش]

در مدل جریان داده‌ها، برخی یا همه داده‌های ورودی که قابل عملیات هستند، برای دسترسی تصادفی از روی دیسک یا حافظه در دسترس نیستند، اما به عنوان یک جریان داده پیوسته سریع تر می‌رسند. جریان را می‌توان به صورت دنباله‌ای از نقاط تعریف کرد که می‌تواند تنها یک بار یا تعداد کمی در دسترس قرار بگیرد. بسیاری از ادبیات جریانی با آمار کامپیوتری روی داده‌های توزیعی که برای ذخیره کردن بسیار بزرگ هستند، مرتبط است. برای این دسته از مشکلات یک بردار a = (${\displaystyle a_{1}}$ , … , ${\displaystyle a_{n}}$) تعریف می‌کنیم که به صفر مقداردهی اولیه می‌کنیم که در یک جریان داده آمادهٔ به روزرسانی می‌باشد. هدف از این الگوریتم محاسبه توابعی از a با استفاده از فضای بسیار کمتری نسبت به فضایی که دقیقاً اشغال می‌کند، است. دو مدل رایج برای به روزرسانی هر جریان وجود دارد، به نام "مدل درخواست نقدی" (به انگلیسی:cash register) و "مدل گردان (به انگلیسی turnstile).^[۴] در مدل درخواست نقدی، هر به روزرسانی به فرم (i,c) می‌باشد به‌طوری‌که ${\displaystyle a_{1}}$ توسط c عدد صحیح مثبت افزایش می‌یابد. در مدل گردان هیچ‌کدام از${\displaystyle a_{i}}$ها منفی نیستند. چندین مقاله نیز مدل «پنجره کشویی» را مطرح گرده‌اند. در این مدل، تابع مورد نظربرای محاسبه بیش از یک پنجره با اندازه ثابت در جریان داده دارد. هنگامی که جریان داده پیشرفت کند، یک آیتم از انتهای این جریان حذف شده و یک آیتم جدید جای آن را می‌گیرد.
علاوه بر مشکلاتی که در فرکانس بالا ایجادمیشود، مشکلات دیگر نیز بررسی شده‌است. تعدادی از مسائل گراف، با ماتریس همسایگی یا فهرست همسایگی که به صورت جریانی تعریف شده باشند، حل شده‌است. تعدادی از مشکلات این حوزه نیز به order(حجم و ترتیب و تعداد آیتم‌ها) یک جریان بستگی دارد. (مثلاً توابع نامتقارن) به‌طور مثال شمارش تعداد نابه جایی‌ها در یک توالی داده مثلاً یک آرایه و یافتن طولانی‌ترین زیررشته صعودی . در واقع الگوریتم‌های مطرح برای رسیدن به این خواسته‌ها به طول رشته داده بستگی دارد و هرچه تعداد آیتم‌های این توالی داده‌ها بیشتر باشد، زمان اجرای الگوریتم و رسیدن به مطلوب سؤال یشتر می‌شود، در واقع مفهوم order به معنی میزان زمان اجرای الگوریتم و تعداد عملیات‌های انجام شده در یک الگوریتم و پیچیدگی الگوریتم می‌باشد. با توجه به حجم داده‌ها، مدل جریان داده‌ها در پیدا کردن نابه جایی‌ها یک محیط طبیعی برای طراحی کارآمد است. ما مجموعه‌ای از الگوریتم‌های جریانی کارآمد، برای تخمین تعداد نابه جایی‌ها در یک جایگشت به دست می‌آوریم. بهترین order برای این الگوریتم‌ها الگوریتم قطعی (deterministic) است که در${\displaystyle O(logn)}$ انجام می‌شود (عبارت ${\displaystyle O(logn)}$ به این مفهوم است که وقتی طول رشته داده ما n باشد زمان اجرای الگوریتم و همان order الگوریتم یک ضریبی از ${\displaystyle logn}$ می‌باشد).

تحلیل و ارزیابی[ویرایش]

عملکرد یک الگوریتم در جریانی از داده‌ها توسط سه عامل اساسی اندازه‌گیری می‌شود:

• تعداد عملیات‌ها و گذرهایی که روی اعضای آن توالی داده انجام می‌شود.
• حافظه موجود.
• زمان اجرای الگوریتم

این الگوریتم‌ها شباهت‌های بسیاری با الگوریتم برخط دارند، زیرا هر دو نیاز به تصمیم‌گیری و پردازش و اجرای عملیات دارند قبل از اینکه تمام داده‌ها در دسترس باشند، یعنی در ابتدای شروع کار الگوریتم، ورودی این الگوریتم‌ها به‌طور کامل در اختیار الگوریتم نیست و به صورت ترتیبی و مرحله مرحله انجام می‌شود اما این شباهت به معنی یکسانی نیست. الگوریتم‌های جریان داده‌ها تنها حافظهٔ در دسترس را محدود کرده‌اند اما آن‌ها ممکن است انجام یک عمل را به تأخیر بیندازند تا یک گروه از نقاط برسند، در حالی که الگوریتم‌های برخط به محض اینکه نقطه‌ای برسد، عملیات را انجام می‌دهند. در واقع الگوریتم‌های جریانی حافظهٔ در دسترس شان را می‌توانند تغییر دهند و حافظه‌شان از ${\displaystyle O(n)}$ است اما حافظهٔ در دسترس الگوریتم‌های برخط ثابت و از ${\displaystyle O(1)}$ می‌باشد. در نتیجه این تفاوت‌ها داریم که الگوریتم‌های جریانی به‌طور نهایی می‌توانند اجرای درست عملیات خود را آزمایش کنند اما آزمایش کردن برای الگوریتم برخط هرمرحله انجام می‌شود
اگر الگوریتمی تقریبی باشد، دقت جواب فاکتور کلیدی می‌شود. دقت پاسخ اغلب به صورت (${\displaystyle \delta }$ , ${\displaystyle \epsilon }$) بیان می‌شود که در آن اشتباه و خطای پاسخ از ${\displaystyle \epsilon }$ با احتمال کمتر است.

کاربردها[ویرایش]

الگوریتم جریان داده‌ها چندین کابرد در حوزه شبکه رایانه‌ای از قبیل کنترل پیوندهای شبکه برای جریان‌های بزرگ داده، شمارش تعداد جریان‌های متمایز، برآورد توزیع اندازه جریان و غیره دارد.^[۵] هم‌چنین تعدادی کابرد در زمینهٔ پایگاه داده دارد مانند تخمین اندازه پیوندها.
به عنوان مثال در زمینه ارتباطات :۳ میلیارد تماس‌های تلفنی در آمریکا هر روز ۳۰ میلیارد ایمیل‌های روزانه، ۱ میلیارد اس‌ام‌اس وجود دارد که ذخیره تمام این داده‌ها در حافظه با دسترسی تصادفی برای پردازش غیرممکن است؛ که راه حل این مسئله پردازش داده‌ها به عنوان یک جریان و بردازش روی این داده‌ها می‌باشد.

چندمسئله حل شده با الگوریتم جریان داده‌ها[ویرایش]

ممان فرکانسی[ویرایش]

k مین ممان فرکانسی از مجموعه فرکانس‌ها به اسم a ایگونه تعریف می‌شود: ${\displaystyle F_{k}(a)=\sum _{i=1}^{n}a_{i}^{k}}$
اولین ممان ${\displaystyle F_{1}}$ به سادگی مجموع فرکانس‌هاست (به عنوان مثال، تعداد کل). رخداد${\displaystyle F_{2}}$ برای محاسبه خواص آماری از داده‌ها، مانند شاخص جینی مورد استفاده است. ${\displaystyle F_{\infty }}$ به عنوان فرکانس عضو پرفرکانس‌ترین تعریف می‌شود.
مقاله بدوی از آلون، ماتیاس و Szegedy به مشکل برآورد لحظات فرکانس پرداخته است.

محاسبه ممان فرکانسی[ویرایش]

یک روش مستقیم برای پیدا کردن ممان‌های فرکانس نیاز به حفظ یک ثبات ${\displaystyle m_{i}}$ برای همه عناصر متمایز${\displaystyle a_{i}}$ که عضو (۱٬۲٬۳٬۴، …، N) می‌باشد که به حداقل حافظه با حدود${\displaystyle \Omega (n)}$ نیاز دارند.^[۳] اما ما باید محدودیت فضا مواجه هستیم و نیاز به یک الگوریتم است که در حافظه بسیار پایین‌تر محاسبه کند. به این می‌توان با استفاده از تقریب به جای ارزش‌های دقیق دست یافت. یک الگوریتمی که محاسبه می‌کند یک تقریب (${\displaystyle \delta }$ , ${\displaystyle \epsilon }$) از ${\displaystyle F_{k}}$ که ${\displaystyle \epsilon }$ به عنوان پارامتر تقریب و ${\displaystyle \delta }$ به عنوان پارامتر اطمینان است. .^[۶]

محاسبه ${\displaystyle F_{0}}$ عناصر متمایز در جریان داده[ویرایش]

الگوریتم FM-Sketch[ویرایش]

فلاجولت (به انگلیسی: Flajolet) وهمکاران در روش احتمالاتی از شمارش که از یک مقاله نوشتهٔ رابرت موریس الهام گرفته شده بود، شمارش تعداد زیادی از حوادث در ثبات‌های کوچک را معرفی کرد. موریس در مقاله خود می‌گوید که اگر نیاز به دقت، کاهش یافته‌است، یک شمارنده ${\displaystyle n}$ می‌تواند با یک شمارنده ${\displaystyle logn}$ جایگزین شود که در ${\displaystyle loglogn}$ بیت ذخیره می‌شود.^[۷] فلاجولت (به انگلیسی: Flajolet) وهمکاران این روش را با استفاده از تابع هش ${\displaystyle h}$ که عناصر را به صورت یکنواخت در فضای هش توزیع می‌کند (یک رشته عدد باینری به طول ${\displaystyle L}$)، بهبود بخشیدند. ${\displaystyle h:[m]->[0,2^{L}-1]}$
فرض کنید bit(y,k) نشان‌دهنده بیت k ام در عدد باینری y است : ${\displaystyle \sum _{k>=0}bit(y,k)*2^{k}}$

فرض کنید ${\displaystyle \rho (y)}$ نشان‌دهنده کم ارزش‌ترین بیت ۱ در نمایش باینری عدد ${\displaystyle y_{i}}$ با یک قرارداد و تعریف مناسب از ${\displaystyle \rho (0)}$ می‌باشد. ${\displaystyle {\begin{cases}Min(bit(y,k))\quad if\quad y>0\\L\qquad \qquad \qquad if\quad y=0\end{cases}}}$
فرض کنید A یک دنباله‌ای از داده‌ها به طول M است که کاردینالیتی مورد نیاز را مشخص می‌کند. فرض کنید BITMAP[0..L-1] فضای هش می‌باشد که ${\displaystyle \rho (hashedvalues)}$ در آنجا ثبت می‌شود. الگوریتم زیر کاردینالیتی تقریبی A را مشخص می‌کند.

 for i in 0 to L − 1 do  BITMAP[i]:=0  end for  for x in A: do  Index:=ρ(hash(x))  i  end if  end for  B:= Position of left most 0 bit of BITMAP[]  return 2^B 

اگر n عنصر متمایز و جدا در جریان داده وجود داشته باشد:

برای همه ${\displaystyle i\gg logn}$ ، در این صورت: BITMAP[i]=0
برای همه ${\displaystyle i\ll logn}$ ، در این صورت: BITMAP[i] = 1
برای همه ${\displaystyle i\approx logn}$ ، در این صورت BITMAP[i] عددی اطراف ۰ و ۱ می‌شود.

الگوریتم ارزش k امین مینیمم[ویرایش]

الگوریتم قبلی اولین تلاش و مرحله برای تقریب ${\displaystyle F_{0}}$ در جریان داده‌ها توسط فلاجولت و مارتین توصیف می‌کند. الگوریتم یک تابع هش تصادفی را انتخاب می‌کند که به‌طور یکنواخت مقادیر را به فضای هش می‌برد.
باریوسف و همکاران الگوریتم مقدار k امین مینیمم برای تعیین تعداد عناصر متمایز در جریان داده‌ها را معرفی کردند. آن‌ها از یک تابع هش مشابه استفاده کردند که مقادیر رو بین ۰ و ۱ می‌برد (عملیات نرمال کردن)${\displaystyle h:[m]->[0,1]}$ . اما آن‌ها یک مقدار محدود t را برای تعداد عناصر موجود در فضای هش یعنی بازه [۰٬۱] ثابت کردند. مقدار t از ${\displaystyle O({\dfrac {1}{\epsilon _{2}}})}$ می‌باشد. الگوریتم KVM مقدار هش شدهٔ کوچک‌ترین t را نگه می‌دارد. پس ازاینکه همه m مقدار داده دریافت شد ، ${\displaystyle v=Max(h(a_{i}))}$ تا بتواند به وسیله آن ${\displaystyle F_{0}^{\prime }={\dfrac {t}{v}}}$را حساب کند. در بازه فضای یکنواخت هش، آن‌ها انتظار دارند که کمترین مقدار t از ${\displaystyle O({\dfrac {t}{F_{0}}})}$ کمتر باشد.

Procedure 2 K-Minimum Value  Initialize first t values of KMV for a in a1 to an do if h(a) <Max(KMV) then Remove Max(KMV) from KMV set Insert h(a) to KMV end if end for return t/Max(KMV) 

تحلیل پیچیدگی الگوریتم KMV[ویرایش]

الگوریتم یافتن مقدار k امین مینیمم می‌تواند در ${\displaystyle O(({\dfrac {1}{\epsilon _{2}}}).log(m)))}$ از بیت‌های حافظه پیاده‌سازی شود. هش کردن هر مقدار ${\displaystyle O(log(m)))}$ از بیت‌های حافظه را نیاز دارد؛ و تعداد هش کردن مقادیر نیز از ${\displaystyle O({\dfrac {1}{\epsilon _{2}}})}$ می‌باشد. اگر مقدار هش شده t در درخت باینری قرار داده شود، زمان دسترسی به آن به مقدار ${\displaystyle O({\dfrac {1}{\epsilon }})}$ کاهش یافته و به‌طور کلی الگوریتم به ${\displaystyle O(({\dfrac {1}{\epsilon }}).log(m)))}$ کاهش می‌یابد.

محاسبه ${\displaystyle F_{k}}$[ویرایش]

آلون و همکاران ${\displaystyle F_{x}}$ را با تعریف متغیری تصادفی که به وسیله فضا و زمان داده شده قابل محساسبه است، تخمین زدند. مقدار ${\displaystyle E[x]}$ یعنی مقدار میانگین وزن‌دار این متغیر تصادفی بیانگر مقدار تقریبی ${\displaystyle F_{k}}$ می‌باشد.
طول داده m از قبل محاسبه شده‌است.
متغیر تصادفی X این‌گونه تعریف می‌شود:

• ${\displaystyle a_{p}}$ یک مقدار تصادفی از دنباله A با شماره p می‌باشد:${\displaystyle a_{p}=l\in (1,2,3,\ldots ,n)}$
• فرض کنید ${\displaystyle r=|\{q:q\geq p,a_{q}=l\}|}$ نشان‌دهنده تعداد رخداد l به عنوان عضوی از دنباله A با تعریف a_p
• متغیر تصادفی X با تعریف ${\displaystyle X=m(r^{k}-(r-1)^{k})}$ می‌باشد.

فرض کنید ${\displaystyle S_{1}}$ از ${\displaystyle O({\dfrac {n^{1-{\dfrac {1}{k}}}}{\lambda ^{2}}})}$ باشد و ${\displaystyle S_{2}}$ از${\displaystyle O(log({\dfrac {1}{\epsilon }}))}$ باشد، در این صورت الگوریتم ${\displaystyle S_{2}}$ را به عنوان یک متغیرتصادفی با مقادیر Y₁,Y₂,... ,Y_S2 و مقدار میانگین Y درنطر می‌گیرد. به‌طوری‌که Y_i مقدار متوسط X_ij برای همه ۱ ≤ j ≤ S₁ می‌باشد.
اکنون مقدار${\displaystyle E[X]}$ را محاسبه می‌کنیم:

پیچیدگی${\displaystyle F_{k}}$[ویرایش]

باتوجه به الگوریتم بالا برای محاسبه ${\displaystyle F_{k}}$ که در آن متغیر تصادفی X دو مقدار ${\displaystyle a_{p}}$ و ${\displaystyle r}$ را ذخیره می‌کند پس متوجه می‌شویم برای محاسبه X به log(n) بیت برای ذخیره کردن ${\displaystyle a_{p}}$ و log(n) بیت برای ذخیره کردن ${\displaystyle r}$ نیازمندیم. تعداد کل متغیرتصادفی X از ${\displaystyle S_{1}*S_{2}}$ محاسبه می‌شود؛ بنابراین کل الگوریتم از ${\displaystyle O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)}$ می‌باشد.

روش مشابه برای محاسبه ${\displaystyle F_{k}}$[ویرایش]

الگوریتم قبلی ${\displaystyle F_{2}}$ را در ${\displaystyle O({\sqrt {n}}(\log m+\log n))}$ از حافظه محاسبه می‌کرد. آلون و همکاران ساده شده این الگوریتم را با استفاده از چهار متغیر تصادفی مستقل که مقادیر رو در بازه ${\displaystyle [-1,1]}$ هش می‌کند. این کار پیچیدگی الگوریتم را به ${\displaystyle O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)}$ کاهش می‌دهد.

بزرگان الگوریتم‌های جریان داده‌ها[ویرایش]

برخی از الگوریتم‌های قابل توجه به جهت یافتن شایع‌ترین و محبوب‌ترین عناصر در یک جریان داده‌ها:

• Boyer–Moore majority vote algorithm
• Karp-Papadimitriou-Shenker algorithm
• تعداد مینمم‌های مطرح
• نمونه مهم شده
• شمارش‌سازی با اتلاف
• نمونه‌گیری و نگهداری
• چند مرحله فیلتر بلووم
• طرح شمارش
• نمونه‌گیری کمک‌کننده طرح

تشخیص رویداد[ویرایش]

تشخیص رویدادها در جریان داده اغلب با استفاده از یک الگوریتم بزرگان که در بالا ذکر شده‌است، انجام می‌شود. شایع‌ترین عناصر و میزان فرکانس و تکرار با استفاده یکی از این الگوریتمها تعیین می‌شود، سپس بیشترین افزایشی که در طول زمان گذشته رخ داده گزارش شود. این رویکرد می‌تواند با استفاده از میانگین متحرک نمایی و واریانس عادی و نرمال شده تصفیه شود. .^[۸]

شمارش عناصر متمایز[ویرایش]

شمارش تعداد عناصر متمایز در یک جریان (گاهی اوقات ممان${\displaystyle F_{0}}$ خوانده می‌شود) مشکل دیگری است که به خوبی مورد مطالعه قرار گرفته‌است. اولین الگوریتم برای آن توسط فلاجولت و مارتین ارائه شده‌است. در سال ۲۰۱۰ کین، نلسون و ودراف یک الگوریتم مجانبی بهینه برای این مشکل پیدا کرده‌اند.^[۹] این الگوریتم از O(ε² + log d) برای حافظه و فضا، بدترین حالت به روزرسانی و زمانش از O(1)، هم‌چنین توابع هش جهانی و یک مجموعه از r هش مستقل به‌طوری کهr = Ω(log(1/ε) / log log(1/ε))استفاده می‌کند.

آنتروپی[ویرایش]

با استفاده از آنتروپی توزیع ترافیک می‌توان نشان داد در طیف گسترده‌ای از برنامه‌های کاربردی نظارت بر شبکه مانند تشخیص ناهنجاری، خوشه بندی برای آشکار ساختن الگوهای جالب، و طبقه‌بندی ترافیک ازآن استفاده می‌شود. با این حال، تحقق این سود بالقوه در عمل نیاز به الگوریتم‌های دقیق است که بتوانند بر روی لینک‌های با سرعت بالا با پردازنده و حافظه مورد نیاز پایین عمل کنند. در این راستا دو الگوریتم وجود دارد که اولین الگوریتم برای برآورد آنتروپی توسط شباهت ساختاری با کار منی آلون و همکاران الهام گرفته‌است که برای برآورد ممان‌های فرکانس از آن استفاده می‌شود و الگوریتم دوم که در آن با مشاهدات عملکرد الگوریتم جریان به جدا کردن آیتم‌های فرکانس بالا (یا فیل‌ها) از موارد با فرکانس پایین می‌رسیم.

آنتروپی یک مجموعه از فرکانس‌های ${\displaystyle \mathbf {a} }$ به صورت ${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}}$ تعریف می‌شود که در آن ${\displaystyle m=\sum _{i=1}^{n}a_{i}}$. برآورد این مقدار در یک جریان توسط این افراد انجام شده‌است:

• McGregor و همکاران
• Do Ba و همکاران
• Lall و همکاران
• Chakrabarti و همکاران

یادگیری آنلاین[ویرایش]

مقاله اصلی: یادگیری آنلاین ماشین یادگیری یک مدل (به عنوان مثال یک طبقه‌بندی آماری) از طریق گذراندن یک مجموعه آموزش:

• هش کردن ویژگی‌ها
• گرادیان نزولی تصادفی

کران پایین[ویرایش]

کران پایین برای بسیاری از مشکلات جریان داده که مطالعه شده‌اند محاسبه شده‌است. تا کنون، متداول‌ترین روش برای محاسبه این کران استفاده از پیچیدگی‌های ارتباطی است.

بیشتر مطالعه کنید[ویرایش]

• • کاویدن جریانی از داده‌ها
• خوشه‌بندی جریانی از داده‌ها
• الگوریتم برخط
• پردازش جریانی
• الگوریتم ترتیبی

پانویس[ویرایش]

منابع[ویرایش]

• Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "The space complexity of approximating the frequency moments", Journal of Computer and System Sciences, 58 (1): 137–147, doi:10.1006/jcss.1997.1545, ISSN 0022-0000. First published as Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), "The space complexity of approximating the frequency moments", Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996), pp. 20–29, doi:10.1145/237814.237823, ISBN 0-89791-785-5.
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002), "Models and issues in data stream systems", Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) (PDF), pp. 1–16, doi:10.1145/543613.543615, archived from the original (PDF) on 9 July 2017, retrieved 1 June 2017.
• Gilbert, A. C.; Kotidis, Y.; Muthukrishnan, S.; Strauss, M. J. (2001), "Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries" (PDF), Proceedings of the International Conference on Very Large Data Bases: 79–88.
• Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), An optimal algorithm for the distinct elements problem, PODS '10, New York, NY, USA: ACM, pp. 41–52, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9 {{citation}}: Unknown parameter |book-title= ignored (help).
• Karp, R. M.; Papadimitriou, C. H.; Shenker, S. (2003), "A simple algorithm for finding frequent elements in streams and bags", ACM Transactions on Database Systems, 28 (1): 51–55, doi:10.1145/762471.762473.
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006), "Data streaming algorithms for estimating entropy of network traffic", Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006) (PDF), doi:10.1145/1140277.1140295^{[پیوند مرده]}.
• Xu, Jun (Jim) (2007), A Tutorial on Network Data Streaming (PDF).
• Heath, D. , Kasif, S. , Kosaraju, R. , Salzberg, S. , Sullivan, G. , "Learning Nested Concepts With Limited Storage", Proceeding IJCAI'91 Proceedings of the 12th international joint conference on Artificial intelligence - Volume 2, Pages 777-782, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©۱۹۹۱
• http://dl.acm.org

پیوند به بیرون[ویرایش]

• Princeton Lecture Notes
• Streaming Algorithms for Geometric Problems, by Piotr Indyk, MIT
• Dagstuhl Workshop on Sublinear Algorithms
• List of open problems in streaming (compiled by Andrew McGregor) from discussion at the IITK Workshop on Algorithms for Data Streams, 2006.
• StreamIt - programming language and compilation infrastructure by MIT CSAIL بایگانی‌شده در ۲۱ مه ۲۰۱۷ توسط Wayback Machine
• IBM Spade - Stream Processing Application Declarative Engine
• IBM InfoSphere Streams

آموزش و نظرسنجی

• Data Stream Algorithms and Applications by S. Muthu Muthukrishnan
• Stanford STREAM project survey
• Network Applications of Bloom filters, by Broder and Mitzenmacher
• Xu's SIGMETRICS 2007 tutorial
• Lecture notes from Data Streams course at Barbados in 2009, by Andrew McGregor and S. Muthu Muthukrishnan

وبگاه دروس

• Dartmouth
• MIT
• Rice
• Rutgers
• University at Buffalo