Data Streams: Random Order & Multiple Passes

https://people.cs.umass.edu/~mcgregor/slides/09-barbados2.pdf
به جای مدل رقیب (adversary) و اگر بشود فرض کرد که جویبار داده به ترتیب تصادفی داده می‌شود (همان داده‌ها هستند اما ترتیبشان تصادفی است. مثلاً اگر بدترین حالت خیلی به ترتیب داده‌ها بستگی داشته باشد، ممکن است حذف شود) می‌شود به کران پایین‌های بهتری رسید.

در این ارائه trade-off بین تعداد عبورها و حافظه بحث می‌شود و از مسئله‌ی Index استفاده می‌شود.

مسئله‌ی 2level index هم جالب بود: بر خلاف ایندکس معمولی، آلیس این بار t تا عدد tبیتی دارد (x^..ها) و باب t عدد بین 1 تا t دارد (y) و چارلی یک عدد بین ۱ تا t دارد (i). در واقع چارلی یکی از اعداد آلیس را انتخاب می‌کند و باب به ازای هر عدد یک اندیس دارد که می‌فرستد. این مسئله با ۲ راند حداقل به t بیت تبادل داده نیاز دارد.

Lecture 1 – Introduction, Schedule, Approximate Counting

مرجع: http://sublinear.wikischolars.columbia.edu/file/view/scribe1.pdf/559708247/scribe1.pdf

به نظرم مهم‌ترین قسمتش به جز تمرین الگوریتم تصادفی، شکل دیگری از نامساوی چبیشف است که می‌گوید که در واقع یک نتیجه است اما این را خیلی راحت‌تر می‌شود حفظ کرد!

Sublinear-time algorithms (property testing)

http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Draft-Survey-Sublinear.pdf

اثبات کران پایین برای مدل جویباری با چند بار دیدن داده‌ها

مرجع: http://www.cis.upenn.edu/~sudipto/mypapers/finalv.pdf

مسایل زیادی وجود دارند که از آنها می‌شود استفاده کرد:
۱- multi-round communication of multi-player set-disjointness: این مسئله کران پایین به صورت حاصل ضرب تعداد راندها و اندازه‌ی حافظه مورد نیاز می‌دهد.
۲- pointer jumping problems
۳- greater-than problem
در این دو مسئله‌ی آخر دو ایراد وجود دارد: یکی اینکه به دست آوردن کران پایین tight سخت است و دیگری اینکه برای توابعی که ترتیب دارند به دست آوردن الگوریتم جویباری با چند عبور سخت است. در این مسایل از روشی به نام round-elimination استفاده می‌شود که آنها را مستقل از تعداد بارهای عبور می‌کند و با اصلاح آن می‌شود این مشکلات را حل کرد.
۴- Sparse Set Disjointness Problem:
http://www.mit.edu/~mahabadi/SetCoverStreaming.pdf
باز هم در این مورد:
http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/lectures/l05.pdf
http://www.cs.umd.edu/~hajiagha/ALB14/scribe-11-11-2014.pdf
http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec10/lec10.pdf
http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic6/lectureNotes/lec10/lec10.pdf

WAPMDS 2009

http://www2.cse.iitk.ac.in/~fsttcs/2009/wapmds/schedule.php

Algorithmic Techniques for Massive Data

http://sublinear.wikischolars.columbia.edu/Lectures+and+Scribes

سوالهای پایان ترم داده‌های حجیم

۱- قطر یک درخت که یالهای آن داده شده است را حساب کنید. پیچیدگی I/O الگوریتم شما چقدر است؟
۲- همان سوال محاسبه‌ی عنصر اکثریت وقتی دو تا جویبار داده را به هم بچسبانیم.
۳-در پیمایش Van Emde Boas زمان جستجو را به صورت دقیق حساب کنید و ثابت کنید که 4 log_B N/B در بدترین حالت می‌شود و در حالت متوسط 2 log_B N/B می‌شود.
۴- همان سوال نمونه سوالها که گفته بود رنگ یک مولفه همبندی را تغییر بدهید.

نمونه سوال گراف در مدل I/O (داده‌های حجیم)

http://www.cs.au.dk/~gerth/io10graph/assignment.pdf

سوالات از: Norbert Zeh

نمونه سوالهای ناآگاه از کش (الگوریتم‌های داده‌های حجیم)

این بیشتر از نظر سوال اولش برایم جالب بود. چرا زمان گفته اصلاً؟

http://jeffe.cs.illinois.edu/teaching/473/hw3final.pdf

بقیه:

https://algo2.iti.kit.edu/download/homework1.pdf

http://www3.cs.stonybrook.edu/~rezaul/Spring-2013/CSE638/CSE638-hw3.pdf

نمونه سوال پایان ترم داده‌های حجیم

http://www.win.tue.nl/~hermanh/teaching/2IL35/homework.pdf

حلش هم می‌کنم به زودی. فقط اگر در حل‌ها اشکال بود کامنت بگذارید!