الگوریتم جریان دادهها
در علم رایانه الگوریتم جریان دادهها (به انگلیسی: Streaming algorithm) الگوریتمی ست برای پردازش جریان دادهها که به صورت توالی از آیتمها به عنوان ورودی هستند و از یک یا تعداد محدودی گذرگاه میتوانند مورد بررسی قرار بگیرند. در واقع این الگوریتم دنبالهای از داده را به عنوان ورودی دریافت کرده و یک سری تابع روی آنها اعمال میکند. این الگوریتم حافظه مورد نیاز (کمتر از اندازه واقعی خود ورودی) و زمان پردازش هر آیتم را هم محدود میکند. این محدودیتها به این معناست که این الگوریتم جواب تقریبی بر اساس یک خلاصه یا «طرحی» از جریان دادهها در حافظه تولید میکند.
تاریخچه
اگرچه مطالعه الگوریتم جریان توسط مونرو و پاترسون دراوایل ۱۹۸۰ آغاز شد اما توسط Philippe Flajolet و نایجل مارتین در ۱۹۸۲–۱۹۸۳ باعث شد موضوعات مرتبط به الگوریتمهای جریان برای اولین بار به رسمیت شناخته شود و در یک مقاله در سال ۱۹۹۶ توسط نوگا آلون، یوسی ماتیاس، و ماریو محبوب شد. نویسندگان این مقاله بعداً جایزه گودل در سال ۲۰۰۵ را «برای سهم بنیادی شان نسبت به الگوریتمهای جریانی» کسب کردند. از آن زمان کار زیادی حول الگوریتمهای جریان داده انجام شد که طیف متنوعی از زمینههای علوم کامپیوتر از قبیل تئوری، پایگاه داده، شبکه و پردازش زبان طبیعی را گسترش داد. الگوریتمهای نیمه جریانی در سال ۲۰۰۵ به عنوان یک فرمت از الگوریتمهای جریانی ارائه شد که برای تعداد ثابت یا لگاریتمی از گذرگاهها روی مجموعهٔ دادهها امکانپذیر است.
مدلها
در مدل جریان دادهها، برخی یا همه دادههای ورودی که قابل عملیات هستند، برای دسترسی تصادفی از روی دیسک یا حافظه در دسترس نیستند، اما به عنوان یک جریان داده پیوسته سریع تر میرسند. جریان را میتوان به صورت دنبالهای از نقاط تعریف کرد که میتواند تنها یک بار یا تعداد کمی در دسترس قرار بگیرد. بسیاری از ادبیات جریانی با آمار کامپیوتری روی دادههای توزیعی که برای ذخیره کردن بسیار بزرگ هستند، مرتبط است. برای این دسته از مشکلات یک بردار a = (
علاوه بر مشکلاتی که در فرکانس بالا ایجادمیشود، مشکلات دیگر نیز بررسی شدهاست. تعدادی از مسائل گراف، با ماتریس همسایگی یا فهرست همسایگی که به صورت جریانی تعریف شده باشند، حل شدهاست. تعدادی از مشکلات این حوزه نیز به order(حجم و ترتیب و تعداد آیتمها) یک جریان بستگی دارد. (مثلاً توابع نامتقارن) بهطور مثال شمارش تعداد نابه جاییها در یک توالی داده مثلاً یک آرایه و یافتن طولانیترین زیررشته صعودی . در واقع الگوریتمهای مطرح برای رسیدن به این خواستهها به طول رشته داده بستگی دارد و هرچه تعداد آیتمهای این توالی دادهها بیشتر باشد، زمان اجرای الگوریتم و رسیدن به مطلوب سؤال یشتر میشود، در واقع مفهوم order به معنی میزان زمان اجرای الگوریتم و تعداد عملیاتهای انجام شده در یک الگوریتم و پیچیدگی الگوریتم میباشد. با توجه به حجم دادهها، مدل جریان دادهها در پیدا کردن نابه جاییها یک محیط طبیعی برای طراحی کارآمد است. ما مجموعهای از الگوریتمهای جریانی کارآمد، برای تخمین تعداد نابه جاییها در یک جایگشت به دست میآوریم. بهترین order برای این الگوریتمها الگوریتم قطعی (deterministic) است که در
تحلیل و ارزیابی
عملکرد یک الگوریتم در جریانی از دادهها توسط سه عامل اساسی اندازهگیری میشود:
- تعداد عملیاتها و گذرهایی که روی اعضای آن توالی داده انجام میشود.
- حافظه موجود.
- زمان اجرای الگوریتم
این الگوریتمها شباهتهای بسیاری با الگوریتم برخط دارند، زیرا هر دو نیاز به تصمیمگیری و پردازش و اجرای عملیات دارند قبل از اینکه تمام دادهها در دسترس باشند، یعنی در ابتدای شروع کار الگوریتم، ورودی این الگوریتمها بهطور کامل در اختیار الگوریتم نیست و به صورت ترتیبی و مرحله مرحله انجام میشود اما این شباهت به معنی یکسانی نیست. الگوریتمهای جریان دادهها تنها حافظهٔ در دسترس را محدود کردهاند اما آنها ممکن است انجام یک عمل را به تأخیر بیندازند تا یک گروه از نقاط برسند، در حالی که الگوریتمهای برخط به محض اینکه نقطهای برسد، عملیات را انجام میدهند. در واقع الگوریتمهای جریانی حافظهٔ در دسترس شان را میتوانند تغییر دهند و حافظهشان از
اگر الگوریتمی تقریبی باشد، دقت جواب فاکتور کلیدی میشود. دقت پاسخ اغلب به صورت (
کاربردها
الگوریتم جریان دادهها چندین کابرد در حوزه شبکه رایانهای از قبیل کنترل پیوندهای شبکه برای جریانهای بزرگ داده، شمارش تعداد جریانهای متمایز، برآورد توزیع اندازه جریان و غیره دارد. همچنین تعدادی کابرد در زمینهٔ پایگاه داده دارد مانند تخمین اندازه پیوندها.
به عنوان مثال در زمینه ارتباطات :۳ میلیارد تماسهای تلفنی در آمریکا هر روز ۳۰ میلیارد ایمیلهای روزانه، ۱ میلیارد اساماس وجود دارد که ذخیره تمام این دادهها در حافظه با دسترسی تصادفی برای پردازش غیرممکن است؛ که راه حل این مسئله پردازش دادهها به عنوان یک جریان و بردازش روی این دادهها میباشد.
چندمسئله حل شده با الگوریتم جریان دادهها
ممان فرکانسی
k مین ممان فرکانسی از مجموعه فرکانسها به اسم a ایگونه تعریف میشود:
اولین ممان
مقاله بدوی از آلون، ماتیاس و Szegedy به مشکل برآورد لحظات فرکانس پرداخته است.
محاسبه ممان فرکانسی
یک روش مستقیم برای پیدا کردن ممانهای فرکانس نیاز به حفظ یک ثبات
محاسبه عناصر متمایز در جریان داده
الگوریتم FM-Sketch
فلاجولت (به انگلیسی: Flajolet) وهمکاران در روش احتمالاتی از شمارش که از یک مقاله نوشتهٔ رابرت موریس الهام گرفته شده بود، شمارش تعداد زیادی از حوادث در ثباتهای کوچک را معرفی کرد. موریس در مقاله خود میگوید که اگر نیاز به دقت، کاهش یافتهاست، یک شمارنده
فرض کنید bit(y,k) نشاندهنده بیت k ام در عدد باینری y است :
فرض کنید
فرض کنید A یک دنبالهای از دادهها به طول M است که کاردینالیتی مورد نیاز را مشخص میکند. فرض کنید BITMAP[0..L-1] فضای هش میباشد که
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 عنصر متمایز و جدا در جریان داده وجود داشته باشد:
برای همه
برای همه
برای همه
الگوریتم ارزش k امین مینیمم
الگوریتم قبلی اولین تلاش و مرحله برای تقریب
باریوسف و همکاران الگوریتم مقدار k امین مینیمم برای تعیین تعداد عناصر متمایز در جریان دادهها را معرفی کردند. آنها از یک تابع هش مشابه استفاده کردند که مقادیر رو بین ۰ و ۱ میبرد (عملیات نرمال کردن)
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 امین مینیمم میتواند در
محاسبه
آلون و همکاران
طول داده m از قبل محاسبه شدهاست.
متغیر تصادفی X اینگونه تعریف میشود:
- یک مقدار تصادفی از دنباله A با شماره p میباشد:
- فرض کنید نشاندهنده تعداد رخداد l به عنوان عضوی از دنباله A با تعریف ap
- متغیر تصادفی X با تعریف میباشد.
فرض کنید
اکنون مقدار
پیچیدگی
باتوجه به الگوریتم بالا برای محاسبه
روش مشابه برای محاسبه
الگوریتم قبلی
بزرگان الگوریتمهای جریان دادهها
برخی از الگوریتمهای قابل توجه به جهت یافتن شایعترین و محبوبترین عناصر در یک جریان دادهها:
- Boyer–Moore majority vote algorithm
- Karp-Papadimitriou-Shenker algorithm
- تعداد مینممهای مطرح
- نمونه مهم شده
- شمارشسازی با اتلاف
- نمونهگیری و نگهداری
- چند مرحله فیلتر بلووم
- طرح شمارش
- نمونهگیری کمککننده طرح
تشخیص رویداد
تشخیص رویدادها در جریان داده اغلب با استفاده از یک الگوریتم بزرگان که در بالا ذکر شدهاست، انجام میشود. شایعترین عناصر و میزان فرکانس و تکرار با استفاده یکی از این الگوریتمها تعیین میشود، سپس بیشترین افزایشی که در طول زمان گذشته رخ داده گزارش شود. این رویکرد میتواند با استفاده از میانگین متحرک نمایی و واریانس عادی و نرمال شده تصفیه شود. .
شمارش عناصر متمایز
شمارش تعداد عناصر متمایز در یک جریان (گاهی اوقات ممان
آنتروپی
با استفاده از آنتروپی توزیع ترافیک میتوان نشان داد در طیف گستردهای از برنامههای کاربردی نظارت بر شبکه مانند تشخیص ناهنجاری، خوشه بندی برای آشکار ساختن الگوهای جالب، و طبقهبندی ترافیک ازآن استفاده میشود. با این حال، تحقق این سود بالقوه در عمل نیاز به الگوریتمهای دقیق است که بتوانند بر روی لینکهای با سرعت بالا با پردازنده و حافظه مورد نیاز پایین عمل کنند. در این راستا دو الگوریتم وجود دارد که اولین الگوریتم برای برآورد آنتروپی توسط شباهت ساختاری با کار منی آلون و همکاران الهام گرفتهاست که برای برآورد ممانهای فرکانس از آن استفاده میشود و الگوریتم دوم که در آن با مشاهدات عملکرد الگوریتم جریان به جدا کردن آیتمهای فرکانس بالا (یا فیلها) از موارد با فرکانس پایین میرسیم.
آنتروپی یک مجموعه از فرکانسهای
- 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, 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 .
- 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
وبگاه دروس