جلسه پنجم

مدل جویبار داده (Streaming Model)

تعریف: یک الگوریتم stream الگوریتمی است که ورودی را در یک عبور (pass) می بیند و حافظه محدود دارد. {بهتر است بگوییم جویبار داده نامحدود است!}

*حل مساله قطر با جویبار داده

الگوریتم دقیق:

برای یک بعد: با محاسبه مینیمم و ماکسیمم با O(1) حافظه به دست می آید و با یک pass انجام پذیر است.

برای دو بعد: حداقل به اندازه ی تعداد نقاط حافظه نیاز داریم چون ممکن است نقطه ای که آن را حذف می کنیم (هر نقطه ای!) در آینده یکی از دو نقظه ی مرزی در محاسبه قطر نقاط باشد.

پس برای بیشتر از یک بعد نمی توانیم الگوریتم جویبار داده ی دقیق بدهیم.

الگوریتم تقریبی:

روش 0 (پیدا کردن دورترین نقطه از یک نقطه): O(1) حافظه می خواهد و در یک عبور امکان پذیر است.

روش 1 (پیدا کردن دورترین نقطه از یک نقطه و دورترین نقطه از آن): به دو عبور نیاز دارد. (نمی شود)

روش 2 (توری): نمی شود چون برای به دست آوردن تقریب اندازه خانه های توری (که گفتیم با یکی از الگوریتم های قبلی انجام می شود) به 2 عبور نیاز خواهد داشت.

روش 3 (رند کردن نقاط در جهت های مختلف): می شود چون بیشتر از یک عبور نیاز نداریم. حافظه ی O(1/epsilon^((d-1)/2)) می خواهد.

* مزیت الگوریتم 0 این است که در ابعاد بالا هم کار می کند، اما الگوریتم 3 نمایی است.

---------------------------------

*آیا می توان مساله نزدیک ترین دو نقطه را در مدل جویبار داده حل کرد؟ خیر، حتی نمی توان تقریب زد.

*آیا می توان مساله عرض نقاط را با این حل کرد؟ بله، با همان coreset گستره نقاط (extent)

*محاسبه عرض نقاط

الگوریتم 1: یک epsilon-هسته از نوع گستره نقاط پیدا کن

ایده: ادغام و کاهش (به آن روش لگاریتمی هم می گویند.)

اضافه کردن نقطه:

1) یک هسته شامل مجموعه تک عضوی {p} بساز. (سطح 0)

2) تا وقتی 2 هسته ی S1 و S2 به ترتیب برای مجموعه نقاط P1 و P2 وجود دارند و در یک سطح هستند:

2-1) اپسیلون هسته ی S که اجتماع S1 و S2 است محاسبه کن.

2-2) S را به عنوان هسته ی P1 U P2 در سطح i برچسب بزن. {حس می کنم اینجا باید i+1 باشه!}

2-3) S1 و S2 را حذف کن.

{جواب هم باید هسته ای باشه که در مرحله ی آخر =بالاترین سطح درخت باقی می ماند.}

دلیل نام گذاری این است که مجموعه نقاط هم سطح را ادغام می کند و وقتی برای سطح بالاتر هسته ساخت هسته های سطح پایین تر را حذف می کند.

{البته فکر کنم کاهش منظور همان ساختن هسته و کاهش نقاط است.}

تحلیل

تعداد سطح ها: O(log n)

فضای لازم: O(1/epsilon^d lg n) (اصطلاحاً polylog( n))

زمان: O(1/epsilon^d n)

( ضریب 1/epsilon^d از اندازه ی هسته می آید. lg n از عمق درخت. n از تعداد ادغام ها= کل گره های درخت)

دلیل حفظ ضریب تقریب هسته (هنگامی که دو هسته ادغام می شود) این است که هسته های قبلی نقاط مجزا داشته اند:

*اگر S1 یک اپسیلون-هسته برای P1 و S2 یک اپسیلون-هسته برای P2 باشد، S1 U S2 یک اپسیلون-هسته برای P1 U P2 است.

*اگر S یک اپسیلون-هسته برای Q باشد و Q یک اپسیلون پریم-هسته برای P باشد، آنگاه S یک (اپسیلون+اپسیلون پریم) - هسته برای P است.

(چون ضریب تقریب های آنها جمع می شود.)

در کل یک O(epsilon* log n)-هسته به دست می آید. اپسیلون را طوری تعیین می کنیم که log n حذف شود:

epsilon' = epsilon/lg n

و با این اپسیلون جدید هسته ها را به دست می آوریم.

فضای کل لازم O( 1/epsilon^(d-1) log^d n) است.

این مدل برای جویبار داده قابل استفاده هست اما می خواهیم مستقل از n کنیم.