Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams

https://arxiv.org/abs/1902.10328

حل تمرین‌های فصل ۲ مبحث جویباری از درس داده‌های حجیم

بعد از کامنت دوستان متوجه شدم مطلب قبلی حل سوالهای فصل ۱ بود در حالی که در عنوان گفته بودم فصل ۲ است.

مرجع: https://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf

۱- 

pr( h(x)=y , h(x')=y' ) = pr( Ax+b (mod 2)= y, Ax'+b (mod 2)=y') = pr( for all i: sum_j a_ij x_j +b_i = y_i, sum_j a_ij x'_j +b_i = y'_i) = prod_i pr( sum_j a_ij x_j +b_i = y_i, sum_j a_ij x'_j +b_i = y'_i) = prod_i pr( sum_j a_ij (x_j-x'_j)=y_i-y'_i) pr( sum_j a_ij x_j +b_i = y_i) = prod_i pr( sum_j a_ij x_j +b_i = y_i)^2

می‌توانیم ماتریس را به صورت k تا بردار n بعدی (هش با بردار) مستقل در نظر بگیریم. هش با بردار تصادفی دودویی روی یک بردار دودویی داده شده را می‌خواهیم احتمالش را حساب کنیم. از آنجا که به ازای هر بردار تصادفی هش، برداری هست که بیت‌هایش برعکس این است (اگر ۰ باشد ۱ است و برعکس)، پس احتمال اینکه صفر آمدنش با یک آمدنش برابر است. پس حالا جمع (xor) دو تا عدد تصادفی یکنواخت باید بشود یک مقدار داده شده، پس احتمالش ۱/۲ است.

= prod_i 1/4 = 1/4^k = 1/(2^k)^2 = 1/|Y|^2

۲- در ورودی دو تا بردار n-بعدی تصادفی a,b و بردار n-بعدی x را داریم، احتمال اینکه k بیت آخر ax+b هر مقداری بگیرد چقدر است؟

چون تناظر یک به یک داده شده است، پس احتمال اینکه هر برداری انتخاب شود برابر است با:

1/|Y|

مشابه بالا به دست می‌آید:

pr( ax+b = y, ax'+b=y') = pr(ax+b=y) pr(a(x-x')+b=y-y') = pr(ax+b=y)^2 = 1/|Y|^2

در مورد مقایسه این روش با قسمت قبل هم می‌بینیم که فرقی ندارند. قسمت قبل حالت خاص این است. چون احتمالها یکسان به دست می‌آیند.

CS294: Property Testing (F2016)

https://people.eecs.berkeley.edu/~alexch/classes/CS294-F2016.html
جلسه ۱۲

کران پایین در مدل جویبار داده با پیچیدگی ارتباطات

مرجع: فیلم کلاس دکتر آبام (مکتب‌خونه گذاشته)
سوال ۱: آلیس و باب هر کدام یک رشته دارند، می‌خواهیم ببینیم اینها با هم مساوی هستند یا نه. دنبال راه حل تصادفی هستیم که کمتر از خطی تبادل داده داشته باشیم. من فکر کردم که یک تعدادی از بیت‌ها را به صورت تصادفی انتخاب کنیم و بفرستیم، مشکل این خواهد بود که فرستادن همان بیت‌ها حجمش زیاد خواهد بود. log n بیت برای اندیس هر کدام لازم است که برای k تا می‌شود k log n. احتمال اینکه درست تشخیص بدهیم هم می‌شود k/n. برای رسیدن به همان احتمال ثابت ۱/۳ هم لازم است که k=n/3 باشد یعنی n/3 log n که از n هم بیشتر می‌شود! پس اینجا معجزه‌ی نظریه اعداد را می‌بینیم که با انتخاب یک عدد اول می‌آید همین کار را با log n بیت انجام می‌دهد.

سوال ۲: اینکه ما یک قسمت از ورودی را می‌دهیم دست آلیس و یک قسمت را دست باب و می‌گوییم الگوریتم را اجرا کنیم و مقدار حافظه‌اش را بفرستیم مثل این است که تا یک زمان از اجرا را به آلیس بدهیم و بقیه را به باب. بعدش هم اینکه بخواهیم کاری کنیم که آن کسی که اندیسش را باب دارد عنصر با بیشتر از n/2 تکرار بشود باید همه‌ی اندیس‌ها را بنویسیم و این اندیس را n/2 بار تکرار کنیم. از روی داده‌ها می‌شود فهمید هر قسمت را باید چه کسی انجام بدهد چون اندیس را فقط آلیس دارد باید n/2 تکرار را آلیس انجام دهد و بقیه را بدهیم به باب.

تفاوت coreset و sketch

https://www.cs.utah.edu/~jeffp/papers/chap48-coreset+sketch.pdf

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

مجموعه‌ی هسته‌ی وزن‌دار (weighted coreset) یک مجموعه‌ی هسته است که به نقاط وزن داده شده است که می‌تواند با وزن اولیه آنها متفاوت باشد.

مجموعه‌ی هسته‌ی ضعیف (weak coreset) برای یک مجموعه از پرسه‌ها (query) تعریف می‌شود که یک شرط را تقریباً برای بعضی از پرسه‌ها بهینه می‌کند.

مجموعه‌ی هسته‌ی قوی (strong coreset) برای همه‌ی پرسه‌های یک مجموعه‌ی داده شرط را بهینه می‌کند.

----------

خلاصه (sketch) یک تصویر فشرده شده از همه‌ی داده‌های یک داده‌ساختار است که می‌تواند به سادگی به روز رسانی شود و داده‌های آن تغییر کند و به آن داده‌ی جدید اضافه شود. همچنین پرسه‌های خاصی برای آن تعریف می‌شود که ویژگی‌هایی از کل داده‌ها را تقریب می‌زند.

خلاصه خطی (linear sketch) خلاصه‌ای است که تصویر داده‌ها تابعی خطی از هر داده است، در نتیجه اضافه، حذف و تغییر را ساده‌تر می‌کند.

--------

شباهت هر دو در این است که اندازه‌ی آنها تابعی از ضریب تقریب است و نه اندازه‌ی ورودی. هرچند در برخی موارد وابستگی لگاریتمی به اندازه ورودی دارد.

تعداد حالت‌های ساخت مجموعه‌ها با شرط روی اندازه اشتراک

این سوال در الگوریتم میکاوا برای انحصار متقابل توزیع شده و در الگوریتم محاسبه‌ی فرکانس هست.
https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pdf
https://ac.els-cdn.com/S0022000097915452/1-s2.0-S0022000097915452-main.pdf?_tid=17567bfe-0830-11e8-98fd-00000aab0f02&acdnat=1517586508_dc4612d9ce69164d6268953577dd6e24
راه‌حلی که به نظر من می‌رسد این است که اول تعداد حالت‌های اشتراک مجموعه‌ها را بسازیم، بعد عناصر را توی آنها بچینیم.
کلاً شمارش آن تا وقتی دو تا مجموعه باشد خیلی سخت نیست، مشکل از وقتی شروع می‌شود که اشتراک سه تا مجموعه که توی سوال برایش هیچ شرطی گذاشته نشده چه چیزی باید باشد.
خب توی خود مقاله نوشته است که در نظریه کدگذاری این بحث شده.
این داستان ادامه دارد...

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

http://www.cse.psu.edu/~sxr48/slides/WIM-sublinear-algorithms-lec2.pdf

تشخیص نیم‌صفحه بودن در زمان زیرخطی

http://www.cse.psu.edu/~sxr48/slides/WIM-sublinear-algorithms-lec1.pdf

طراحی الگوریتم‌های داده‌های حجیم

http://www.win.tue.nl/~mdberg/Teaching/2IMA10-Material/AA-extra-lecture.pdf
بخش ۲ و ۳:
http://www.win.tue.nl/~mdberg/Teaching/2IMA10-Material/course-notes-AA.pdf

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering

http://drops.dagstuhl.de/opus/volltexte/2016/6322/pdf/LIPIcs-ICALP-2016-42.pdf