الگوریتم جریان دادهها: تفاوت میان نسخهها
LetsDoItBot (بحث | مشارکتها) تمیزکاری، + ویرایش با ماژول ابرابزار با استفاده از AWB |
جز ربات: جایگزینی پیوند جادویی شابک با الگو شابک |
||
خط ۳۱: | خط ۳۱: | ||
==== محاسبه ممان فرکانسی ==== |
==== محاسبه ممان فرکانسی ==== |
||
یک روش مستقیم برای پیدا کردن ممانهای فرکانس نیاز به حفظ یک ثبات <math> m_i</math> برای همه عناصر متمایز<math> a_i</math> که عضو (۱٬۲٬۳٬۴، …، N) میباشد که به حداقل حافظه با حدود<math> \Omega(n) </math> نیاز دارند.<ref name="three" /> اما ما باید محدودیت فضا مواجه هستیم و نیاز به یک الگوریتم است که در حافظه بسیار پایینتر محاسبه کند. به این میتوان با استفاده از تقریب به جای ارزشهای دقیق دست یافت. یک الگوریتمی که محاسبه میکند یک تقریب (<math> \delta </math> , <math> \epsilon </math>) از <math> F_k</math> که <math> \epsilon </math> به عنوان پارامتر تقریب و <math> \delta </math> به عنوان پارامتر اطمینان است. .<ref>Bar-Yossef, Ziv; Jayram, T. S. ; Kumar, Ravi; Sivakumar, D. ; Trevisan, Luca (2002-09-13). Rolim, José D. P. ; Vadhan, Salil, eds. Counting Distinct Elements in a Data Stream. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1–10. ISBN |
یک روش مستقیم برای پیدا کردن ممانهای فرکانس نیاز به حفظ یک ثبات <math> m_i</math> برای همه عناصر متمایز<math> a_i</math> که عضو (۱٬۲٬۳٬۴، …، N) میباشد که به حداقل حافظه با حدود<math> \Omega(n) </math> نیاز دارند.<ref name="three" /> اما ما باید محدودیت فضا مواجه هستیم و نیاز به یک الگوریتم است که در حافظه بسیار پایینتر محاسبه کند. به این میتوان با استفاده از تقریب به جای ارزشهای دقیق دست یافت. یک الگوریتمی که محاسبه میکند یک تقریب (<math> \delta </math> , <math> \epsilon </math>) از <math> F_k</math> که <math> \epsilon </math> به عنوان پارامتر تقریب و <math> \delta </math> به عنوان پارامتر اطمینان است. .<ref>Bar-Yossef, Ziv; Jayram, T. S. ; Kumar, Ravi; Sivakumar, D. ; Trevisan, Luca (2002-09-13). Rolim, José D. P. ; Vadhan, Salil, eds. Counting Distinct Elements in a Data Stream. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1–10. {{ISBN|978-3-540-44147-2|en}}.</ref> |
||
===== محاسبه <math> F_0</math> عناصر متمایز در جریان داده ===== |
===== محاسبه <math> F_0</math> عناصر متمایز در جریان داده ===== |
||
خط ۱۲۶: | خط ۱۲۶: | ||
=== تشخیص رویداد === |
=== تشخیص رویداد === |
||
تشخیص رویدادها در جریان داده اغلب با استفاده از یک الگوریتم بزرگان که در بالا ذکر شده است، انجام میشود. شایعترین عناصر و میزان فرکانس و تکرار با استفاده یکی از این الگوریتمها تعیین میشود، سپس بیشترین افزایشی که در طول زمان گذشته رخ داده گزارش شود. این رویکرد میتواند با استفاده از میانگین متحرک نمایی و واریانس عادی و نرمال شده تصفیه شود. |
تشخیص رویدادها در جریان داده اغلب با استفاده از یک الگوریتم بزرگان که در بالا ذکر شده است، انجام میشود. شایعترین عناصر و میزان فرکانس و تکرار با استفاده یکی از این الگوریتمها تعیین میشود، سپس بیشترین افزایشی که در طول زمان گذشته رخ داده گزارش شود. این رویکرد میتواند با استفاده از میانگین متحرک نمایی و واریانس عادی و نرمال شده تصفیه شود. |
||
.<ref>Schubert, E. ; Weiler, M. ; Kriegel, H. P. (2014). SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. pp. 871–880. doi:10.1145/2623330.2623740. |
.<ref>Schubert, E. ; Weiler, M. ; Kriegel, H. P. (2014). SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. pp. 871–880. doi:10.1145/2623330.2623740. {{شابک|978-1-4503-2956-9}}</ref> |
||
=== شمارش عناصر متمایز === |
=== شمارش عناصر متمایز === |
نسخهٔ ۱۷ سپتامبر ۲۰۱۷، ساعت ۲۱:۵۹
در علم رایانه الگوریتم جریان دادهها (به انگلیسی: Streaming algorithm) الگوریتمی ست برای پردازش جریان دادهها که به صورت توالی از آیتمها به عنوان ورودی هستند و از یک یا تعداد محدودی گذرگاه میتوانند مورد بررسی قرار بگیرند. درواقع این الگوریتم دنباله ای از داده را به عنوان ورودی دریافت کرده و یک سری تابع روی آنها اعمال میکند. این الگوریتم حافظه مورد نیاز (کمتر از اندازه واقعی خود ورودی) و زمان پردازش هر آیتم را هم محدود میکند. این محدودیتها به این معناست که این الگوریتم جواب تقریبی بر اساس یک خلاصه یا «طرحی» از جریان دادهها در حافظه تولید میکند.
تاریخچه
اگرچه مطالعه الگوریتم جریان توسط مونرو و پاترسون[۱] دراوایل ۱۹۸۰ آغاز شد اما توسط Philippe Flajolet و نایجل مارتین در ۱۹۸۲–۱۹۸۳ باعث شد[۲] موضوعات مرتبط به الگوریتمهای جریان برای اولین بار به رسمیت شناخته شود و در یک مقاله در سال ۱۹۹۶ توسط نوگا آلون، یوسی ماتیاس، و ماریو[۳] محبوب شد. نویسندگان این مقاله بعداً جایزه گودل در سال ۲۰۰۵ را «برای سهم بنیادی شان نسبت به الگوریتمهای جریانی» کسب کردند. از آن زمان کار زیادی حول الگوریتمهای جریان داده انجام شد که طیف متنوعی از زمینههای علوم کامپیوتر از قبیل تئوری، پایگاه داده، شبکه و پردازش زبان طبیعی را گسترش داد. الگوریتمهای نیمه جریانی در سال ۲۰۰۵ به عنوان یک فرمت از الگوریتمهای جریانی ارائه شد که برای تعداد ثابت یا لگاریتمی از گذرگاهها روی مجموعهٔ دادهها امکانپذیر است.
مدلها
در مدل جریان دادهها، برخی یا همه دادههای ورودی که قابل عملیات هستند، برای دسترسی تصادفی از روی دیسک و یا حافظه در دسترس نیستند، اما به عنوان یک جریان داده پیوسته سریع تر میرسند. جریان را میتوان به صورت دنبالهای از نقاط تعریف کرد که میتواند تنها یک بار و یا تعداد کمی در دسترس قرار بگیرد. بسیاری از ادبیات جریانی با آمار کامپیوتری روی دادههای توزیعی که برای ذخیره کردن بسیار بزرگ هستند، مرتبط است. برای این دسته از مشکلات یک بردار a = ( , … , ) تعریف میکنیم که به صفر مقداردهی اولیه میکنیم که در یک جریان داده آمادهٔ به روزرسانی میباشد. هدف از این الگوریتم محاسبه توابعی از a با استفاده از فضای بسیار کمتری نسبت به فضایی که دقیقاً اشغال میکند، است. دو مدل رایج برای به روز رسانی هر جریان وجود دارد، به نام "مدل درخواست نقدی" (به انگلیسی:cash register) و "مدل گردان (به انگلیسی turnstile).[۴]
در مدل درخواست نقدی، هر به روز رسانی به فرم (i,c) میباشد به طوری که توسط c عدد صحیح مثبت افزایش مییابد. در مدل گردان هیچکدام از ها منفی نیستند. چندین مقاله نیز مدل «پنجره کشویی» را مطرح گردهاند. در این مدل، تابع مورد نظربرای محاسبه بیش از یک پنجره با اندازه ثابت در جریان داده دارد. هنگامی که جریان داده پیشرفت کند، یک آیتم از انتهای این جریان حذف شده و یک آیتم جدید جای آن را میگیرد.
علاوه بر مشکلاتی که در فرکانس بالا ایجادمیشود، مشکلات دیگر نیز بررسی شده است. تعدادی از مسائل گراف، با ماتریس همسایگی و یا فهرست همسایگی که به صورت جریانی تعریف شده باشند، حل شده است. تعدادی از مشکلات این حوزه نیز به order(حجم و ترتیب و تعداد آیتمها) یک جریان بستگی دارد. (مثلاً توابع نامتقارن) به طور مثال شمارش تعداد نابه جاییها در یک توالی داده مثلاً یک آرایه و یافتن طولانیترین زیررشته صعودی . درواقع الگوریتمهای مطرح برای رسیدن به این خواستهها به طول رشته داده بستگی دارد و هرچه تعداد آیتمهای این توالی دادهها بیشتر باشد، زمان اجرای الگوریتم و رسیدن به مطلوب سؤال یشتر میشود، در واقع مفهوم order به معنی میزان زمان اجرای الگوریتم و تعداد عملیاتهای انجام شده در یک الگوریتم و پیچیدگی الگوریتم میباشد. با توجه به حجم دادهها، مدل جریان دادهها در پیدا کردن نابه جاییها یک محیط طبیعی برای طراحی کارآمد است. ما مجموعه ای از الگوریتمهای جریانی کارآمد، برای تخمین تعداد نابه جاییها در یک جایگشت به دست میآوریم. بهترین order برای این الگوریتمها الگوریتم قطعی (deterministic) است که در انجام میشود (عبارت به این مفهوم است که وقتی طول رشته داده ما n باشد زمان اجرای الگوریتم و همان order الگوریتم یک ضریبی از میباشد).
تحلیل و ارزیابی
عملکرد یک الگوریتم در جریانی از دادهها توسط سه عامل اساسی اندازهگیری میشود:
- تعداد عملیاتها و گذرهایی که روی اعضای آن توالی داده انجام میشود.
- حافظه موجود.
- زمان اجرای الگوریتم
این الگوریتمها شباهتهای بسیاری با الگوریتم برخط دارند، زیرا هر دو نیاز به تصمیمگیری و پردازش و اجرای عملیات دارند قبل از اینکه تمام دادهها در دسترس باشند، یعنی در ابتدای شروع کار الگوریتم، ورودی این الگوریتمها به طور کامل در اختیار الگوریتم نیست و به صورت ترتیبی و مرحله مرحله انجام میشود اما این شباهت به معنی یکسانی نیست. الگوریتمهای جریان دادهها تنها حافظهٔ در دسترس را محدود کردهاند اما آنها ممکن است انجام یک عمل را به تأخیر بیندازند تا یک گروه از نقاط برسند، در حالی که الگوریتمهای برخط به محض اینکه نقطه ای برسد، عملیات را انجام میدهند. درواقع الگوریتمهای جریانی حافظهٔ در دسترس شان را میتوانند تغییر دهند و حافظه شان از است اما حافظهٔ در دسترس الگوریتمهای برخط ثابت و از میباشد. درنتیجه این تفاوتها داریم که الگوریتمهای جریانی به طور نهایی میتوانند اجرای درست عملیات خود را آزمایش کنند اما آزمایش کردن برای الگوریتم برخط هرمرحله انجام میشود
اگر الگوریتمی تقریبی باشد، دقت جواب فاکتور کلیدی میشود. دقت پاسخ اغلب به صورت ( , ) بیان میشود که درآن اشتباه و خطای پاسخ از با احتمال کمتر است.
کاربردها
الگوریتم جریان دادهها چندین کابرد در حوزه شبکه رایانهای از قبیل کنترل پیوندهای شبکه برای جریانهای بزرگ داده، شمارش تعداد جریانهای متمایز، برآورد توزیع اندازه جریان و غیره دارد.[۵] همچنین تعدادی کابرد در زمینهٔ پایگاه داده دارد مانند تخمین اندازه پیوندها.
به عنوان مثال در زمینه ارتباطات :۳ میلیارد تماسهای تلفنی در آمریکا هر روز ۳۰ میلیارد ایمیلهای روزانه، ۱ میلیارد اس ام اس وجود دارد که ذخیره تمام این دادهها در حافظه با دسترسی تصادفی برای پردازش غیرممکن است؛ که راه حل این مسئله پردازش دادهها به عنوان یک جریان و بردازش روی این دادهها میباشد.
چندمسئله حل شده با الگوریتم جریان دادهها
ممان فرکانسی
k مین ممان فرکانسی از مجموعه فرکانسها به اسم a ایگونه تعریف میشود:
اولین ممان به سادگی مجموع فرکانسهاست (به عنوان مثال، تعداد کل). رخداد برای محاسبه خواص آماری از دادهها، مانند شاخص جینی مورد استفاده است. به عنوان فرکانس عضو پرفرکانسترین تعریف میشود.
مقاله بدوی از آلون، ماتیاس و Szegedy به مشکل برآورد لحظات فرکانس پرداخته است.
محاسبه ممان فرکانسی
یک روش مستقیم برای پیدا کردن ممانهای فرکانس نیاز به حفظ یک ثبات برای همه عناصر متمایز که عضو (۱٬۲٬۳٬۴، …، N) میباشد که به حداقل حافظه با حدود نیاز دارند.[۳] اما ما باید محدودیت فضا مواجه هستیم و نیاز به یک الگوریتم است که در حافظه بسیار پایینتر محاسبه کند. به این میتوان با استفاده از تقریب به جای ارزشهای دقیق دست یافت. یک الگوریتمی که محاسبه میکند یک تقریب ( , ) از که به عنوان پارامتر تقریب و به عنوان پارامتر اطمینان است. .[۶]
محاسبه عناصر متمایز در جریان داده
الگوریتم FM-Sketch
فلاجولت (به انگلیسی: Flajolet) وهمکاران در روش احتمالاتی از شمارش که از یک مقاله نوشتهٔ رابرت موریس الهام گرفته شده بود، شمارش تعداد زیادی از حوادث در ثباتهای کوچک را معرفی کرد. موریس در مقاله خود میگوید که اگر نیاز به دقت، کاهش یافته است، یک شمارنده میتواند با یک شمارنده جایگزین شود که در بیت ذخیره میشود.[۷] فلاجولت (به انگلیسی: Flajolet) وهمکاران این روش را با استفاده از تابع هش که عناصر را به صورت یکنواخت در فضای هش توزیع میکند (یک رشته عدد باینری به طول )، بهبود بخشیدند.
فرض کنید bit(y,k) نشاندهنده بیت k ام در عدد باینری y است :
فرض کنید نشاندهنده کم ارزشترین بیت ۱ در نمایش باینری عدد با یک قرارداد و تعریف مناسب از
میباشد.
فرض کنید A یک دنباله ای از دادهها به طول M است که کاردینالیتی مورد نیاز را مشخص میکند. فرض کنید BITMAP[0..L-1] فضای هش میباشد که در آنجا ثبت میشود. الگوریتم زیر کاردینالیتی تقریبی A را مشخص میکند.
Procedure FM-Sketch:
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 عنصر متمایز و جدا در جریان داده وجود داشته باشد:
برای همه ، دراین صورت: BITMAP[i]=0
برای همه ، دراین صورت: BITMAP[i] = 1
برای همه ، دراین صورت BITMAP[i] عددی اطراف ۰ و ۱ میشود.
الگوریتم ارزش k امین مینیمم
الگوریتم قبلی اولین تلاش و مرحله برای تقریب در جریان دادهها توسط فلاجولت و مارتین توصیف میکند. الگوریتم یک تابع هش تصادفی را انتخاب میکند که به طور یکنواخت مقادیر را به فضای هش میبرد.
باریوسف و همکاران الگوریتم مقدار k امین مینیمم برای تعیین تعداد عناصر متمایز در جریان دادهها را معرفی کردند. آنها از یک تابع هش مشابه استفاده کردند که مقادیر رو بین ۰ و ۱ میبرد (عملیات نرمال کردن) . اما آنها یک مقدار محدود t را برای تعداد عناصر موجود در فضای هش یعنی بازه [۰٬۱] ثابت کردند. مقدار t از میباشد. الگوریتم KVM مقدار هش شدهٔ کوچکترین t را نگه میدارد. پس ازاینکه همه m مقدار داده دریافت شد ، تا بتواند به وسیله آن را حساب کند. در بازه فضای یکنواخت هش، آنها انتظار دارند که کمترین مقدار t از کمتر باشد.
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 امین مینیمم میتواند در از بیتهای حافظه پیادهسازی شود. هش کردن هر مقدار از بیتهای حافظه را نیاز دارد؛ و تعداد هش کردن مقادیر نیز از میباشد. اگر مقدار هش شده t در درخت باینری قرار داده شود، زمان دسترسی به آن به مقدار کاهش یافته و به طور کلی الگوریتم به کاهش مییابد.
محاسبه
آلون و همکاران را با تعریف متغیری تصادفی که به وسیله فضا و زمان داده شده قابل محساسبه است، تخمین زدند. مقدار
یعنی مقدار میانگین وزندار این متغیر تصادفی بیانگر مقدار تقریبی میباشد.
طول داده m از قبل محاسبه شده است.
متغیر تصادفی X اینگونه تعریف میشود:
- یک مقدار تصادفی از دنباله A با شماره p میباشد:
- فرض کنید نشاندهنده تعداد رخداد l به عنوان عضوی از دنباله A با تعریف ap
- متغیر تصادفی X با تعریف میباشد.
فرض کنید از باشد و از باشد، دراین صورت الگوریتم رابه عنوان یک متغیرتصادفی با مقادیر Y1,Y2,... ,YS2 و مقدار میانگین Y درنطر میگیرد. به طوری که Yi مقدار متوسط Xij برای همه ۱ ≤ j ≤ S1 میباشد.
اکنون مقدار را محاسبه میکنیم:
پیچیدگی
باتوجه به الگوریتم بالا برای محاسبه که در آن متغیر تصادفی X دو مقدار و را ذخیره میکند پس متوجه میشویم برای محاسبه X به log(n) بیت برای ذخیره کردن و log(n) بیت برای ذخیره کردن نیازمندیم. تعداد کل متغیرتصادفی X از محاسبه میشود؛ بنابراین کل الگوریتم از میباشد.
روش مشابه برای محاسبه
الگوریتم قبلی را در از حافظه محاسبه میکرد. آلون و همکاران ساده شده این الگوریتم را با استفاده از چهار متغیر تصادفی مستقل که مقادیر رو در بازه هش میکند. این کار پیچیدگی الگوریتم را به کاهش میدهد.
بزرگان الگوریتمهای جریان دادهها
برخی از الگوریتمهای قابل توجه به جهت یافتن شایعترین و محبوبترین عناصر در یک جریان دادهها:
- Boyer–Moore majority vote algorithm
- Karp-Papadimitriou-Shenker algorithm
- تعداد مینممهای مطرح
- نمونه مهم شده
- شمارش سازی با اتلاف
- نمونه گیری و نگهداری
- چند مرحله فیلتر بلووم
- طرح شمارش
- نمونه گیری کمک کننده طرح
تشخیص رویداد
تشخیص رویدادها در جریان داده اغلب با استفاده از یک الگوریتم بزرگان که در بالا ذکر شده است، انجام میشود. شایعترین عناصر و میزان فرکانس و تکرار با استفاده یکی از این الگوریتمها تعیین میشود، سپس بیشترین افزایشی که در طول زمان گذشته رخ داده گزارش شود. این رویکرد میتواند با استفاده از میانگین متحرک نمایی و واریانس عادی و نرمال شده تصفیه شود. .[۸]
شمارش عناصر متمایز
شمارش تعداد عناصر متمایز در یک جریان (گاهی اوقات ممان خوانده میشود) مشکل دیگری است که به خوبی مورد مطالعه قرار گرفته است. اولین الگوریتم برای آن توسط فلاجولت و مارتین ارائه شده است. در سال ۲۰۱۰ کین، نلسون و ودراف یک الگوریتم مجانبی بهینه برای این مشکل پیدا کردهاند.[۹] این الگوریتم از O(ε2 + log d) برای حافظه و فضا، بدترین حالت به روزرسانی و زمانش از O(1)، همچنین توابع هش جهانی و یک مجموعه از r هش مستقل به طوری کهr = Ω(log(1/ε) / log log(1/ε))استفاده میکند.
آنتروپی
با استفاده از آنتروپی توزیع ترافیک میتوان نشان داد در طیف گسترده ای از برنامههای کاربردی نظارت بر شبکه مانند تشخیص ناهنجاری، خوشه بندی برای آشکار ساختن الگوهای جالب، و طبقهبندی ترافیک ازآن استفاده میشود. با این حال، تحقق این سود بالقوه در عمل نیاز به الگوریتمهای دقیق است که بتوانند بر روی لینکهای با سرعت بالا با پردازنده و حافظه مورد نیاز پایین عمل کنند. دراین راستا دو الگوریتم وجود دارد که اولین الگوریتم برای برآورد آنتروپی توسط شباهت ساختاری با کار منی آلون و همکاران الهام گرفته است که برای برآورد ممانهای فرکانس از آن استفاده میشود و الگوریتم دوم که در آن با مشاهدات عملکرد الگوریتم جریان به جدا کردن آیتمهای فرکانس بالا (یا فیلها) از موارد با فرکانس پایین میرسیم.
آنتروپی یک مجموعه از فرکانسهای به صورت تعریف میشود که در آن . برآورد این مقدار در یک جریان توسط این افراد انجام شده است:
- McGregor و همکاران
- Do Ba و همکاران
- Lall و همکاران
- Chakrabarti و همکاران
یادگیری آنلاین
مقاله اصلی: یادگیری آنلاین ماشین یادگیری یک مدل (به عنوان مثال یک طبقهبندی آماری) از طریق گذراندن یک مجموعه آموزش:
کران پایین
کران پایین برای بسیاری از مشکلات جریان داده که مطالعه شدهاند محاسبه شده است. تا کنون، متداولترین روش برای محاسبه این کران استفاده از پیچیدگیهای ارتباطی است.
بیشتر مطالعه کنید
پانویس
- ↑ Munro & Paterson (1980)
- ↑ Flajolet & Martin (1985)
- ↑ ۳٫۰ ۳٫۱ Alon, Matias & Szegedy (1996)
- ↑ Gilbert et al. (2001)
- ↑ Xu (2007)
- ↑ Bar-Yossef, Ziv; Jayram, T. S. ; Kumar, Ravi; Sivakumar, D. ; Trevisan, Luca (2002-09-13). Rolim, José D. P. ; Vadhan, Salil, eds. Counting Distinct Elements in a Data Stream. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1–10. ISBN 978-3-540-44147-2.
- ↑ Flajolet, Philippe (1985-03-01). "Approximate counting: A detailed analysis". BIT Numerical Mathematics. 25 (1): 113–134. doi:10.1007/BF01934993. ISSN 0006-3835
- ↑ Schubert, E. ; Weiler, M. ; Kriegel, H. P. (2014). SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. pp. 871–880. doi:10.1145/2623330.2623740. شابک ۹۷۸−۱−۴۵۰۳−۲۹۵۶−۹
- ↑ Kane, Nelson & Woodruff (2010)
منابع
- 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.
- 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|booktitle=
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
- 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
وبگاه دروس