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

۱- برعکس کردن یک آرایه بدون حافظه‌ی اضافی (حافظه O(1))

جواب: از دو طرف scan می‌کنیم و به جای هم می‌نویسیم. (با توجه به اینکه LRU استفاده می‌شود این هم زمانش به اندازه‌ی scan می‌شود.)

۲-درخت بی در مدل ناآگاه از کش: از ترکیب چینش van Emde Boas و استفاده از اشاره‌گر در هر گره ساخته می‌شود. (مشابه فایل مرتب)

زمان حذف و درج در فایل مرتب lg^2 N /B می‌شود که برای درخت بی هم هست فقط زمان جستجوی این log_B N می‌شود. (سرشکن)

۳-هرم در مدل ناآگاه از کش

جواب: مثل روش لگاریتمی و مرتب‌سازی در مدل ناآگاه از کش عمل می‌کنیم. یک سری قیف و یک سری بافر نگه می‌داریم که از نظر سایز هر بار ۲ برابر می‌شوند (نزدیک خروجی کوچکترند) و برای حذف آن مشابه هرم در مدل I/O عمل می‌کنیم.

هزینه‌ی درج و حذف کوچکترین عنصر در آن O(1/B log_{M/B} N/B) است (سرشکن).

۴-لیست پیوندی: فکر کنم این است که لیست‌ها را به زیرلیست‌های r عنصری تقسیم می‌کند و مشابه فایل مرتب (پویا) با آن رفتار می‌کند.

سوالهای مبحث جویباری (داده‌های حجیم)

فصل۲، صفحه ۹:

موضوع: الگوریتم پیدا کردن عنصر با بیشترین تکرار جویباری با یک عبور و حافظه‌ی k

سوال ۱: ثابت کنید که تقریب الگوریتم به جای m/k می‌تواند به (m-m^)/k برسد که m^ مجموع به دست آمده در الگوریتم است.

جواب:

چون m^ بار در شرط حذف نمی‌افتیم، حداکثر تعداد بارهایی که در شرط حذف می‌افتیم m-m^ بار است. چون کل جویبار m تا عنصر داشت و m^ بار هیچ عنصری حذف نشده است. مشابه قبل می‌توانیم بگوییم که حداکثر تعداد بارهایی که از یک عنصر در حافظه مقداری کم شده است (m-m^)/k است.

سوال ۲: فرض کنید الگوریتم را روی دو جویبار s1 و s2 اجرا کنیم و خلاصه‌ی آنها را در شمارنده‌های kتایی نگه داریم. الگوریتم زیر برای ادغام آنها به صورت یک جویبار را در نظر بگیرید:

۱) شمارنده‌ها را ادغام کنید و اگر اعداد متناظر آنها مساوی بودند با هم جمع کنید.

۲)‌اگر بیشتر از k شمارنده هست،

۲-۱) مقدار k+1 امین شمارنده در ترتیب صعودی را c بگیرید.

۲-۲) مقدار c را از همه‌ی شمارنده‌ها کم کنید و مقادیر نامثبت را حذف کنید.

ثابت کنید که خلاصه‌ی به دست آمده برای اتصال جویبارهای s1 و s2 تقریب مشابه قبل می‌دهد.

جواب:

یک شرط لازم دارد که از ابتدا فرکانس عنصر با بیشترین تکرار از (m1+m2)/k بیشتر باشد.

برای ترکیب شمارنده‌ها، چون به ازای هر عنصر، خطای آن جمع می‌شود، خطا برابر است با:

(m1-m1^)/k+(m2-m2^)/k

که چون m=m1+m2 و m1^+m2^>m^ است پس حکم اثبات می‌شود.

---------

فصل ۲ بیشتر سوالهایش از 2-universal hash بود که نمی‌نویسم چون بیشتر تصادفی است. از این الگوریتم هم می‌شود برای همه‌ی توانهای فرکانس‌های اعداد استفاده کرد و حافظه‌اش هم log n است.

در مورد شمارش مثلث‌ها با این روش هم حافظه باز هم log n می‌ماند.

رتبه‌بندی لیست (الگوریتم‌های داده‌های حجیم-قسمت ۱)

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

معمولی هر کردن مسأله به تعداد عناصر عمل ورودی-خروجی لازم دارد. پس به جای این کار، سعی می‌کنیم زیرمسأله برای آن به دست بیاوریم. برای این کار، یک مجموعه‌ی مستقل پیدا می‌کنیم و آن را حذف می‌کنیم و رتبه‌ی آن را به عنصر بعدی‌اش می‌دهیم. چون هیچ دو تای متوالی در این مجموعه نیستند مشکلی در رتبه‌ها به وجود نمی‌آید و برای اینکه تعداد عناصری که حذف می‌کنیم تأثیری روی رتبه‌هایی که حساب می‌کنیم نداشته باشد، تعدادشان را به بعدی می‌دهیم.

حالا برای به دست آوردن مجموعه‌ی مستقل، چون یک لیست است اگر همین طوری حریصانه حساب کنیم، به یک مجموعه‌ی مستقل با n/3 رأس می‌رسیم. برای ساختنش هم کافی است یک فایل بسازیم و هر بار عنصر بعدی (و احتمالاً قبلی؟) هر عنصر را اضافه کنیم. حالا رأس بعدی را که انتخاب می‌کنیم اول چک می‌کنیم در فایل آنهایی که همسایه‌شان قبلاً انتخاب شده نباشد.

T(N) = T(2/3N)+O(Sort(N)) (N>M)

T(N) = N/B (N<= M)

==> T(N) = O(Sort(N))

اسلایدهای ارائه داده‌های حجیم

دریافت
حجم: 59.4 کیلوبایت

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

۱- با استفاده از روش لگاریتمی یک سری B-tree بسازید که کافی است فقط عمل درج را پشتیبانی کند.

۲- سوال جستجوی بازه‌ی تمرین Arge

۳- اگر b<B و m<M باشد در Buffer-tree، تعداد IO جستجو و درج چقدر می‌شود؟ اگر روی هر بافر یک B-tree بسازیم و m=B^2 باشد، زمان جستجو و درج چقدر می‌شود؟

۴- می‌خواهیم یک لیست پیوندی بسازیم که زمان درج در آن O(1) باشد و حافظه‌ی آن 4/3ceil{N/B} باشد. اگر بخواهیم فضا ۱+اپسیلون برابر N/B باشد و زمان کوئری یک بر اپسیلون باشد باید چه کار کنیم؟

۵- تقاطع‌های تعدادی پاره‌خط افقی با تعدادی خط عمودی را پیدا کنید. اگر به جای خط، پاره‌خط عمودی داشته باشیم چطور؟

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

این تمرین تئوری کسی بوده است که مقاله‌اش منبع درس است.

http://www.daimi.au.dk/~large/ioS13/project3.pdf

جواب‌ها:

۱- کافی است وقتی که در حافظه‌ی اصلی تکراری دیدیم حذفش کنیم و فقط یکی ازش نگه داریم.

در بهترین حالت همه‌ی اعداد یکسان پشت سر هم میان و زمان حذف کردنشان میشه Sort(Ni). پس حداقل این قدر زمان از کل زمان کم میشه.

اگر همه مساوی باشند جمله‌ی اولی صفر می‌شود. پس باید در نظر بگیریم که حداقل به اندازه‌ی خواندن همه‌ی ورودی زمان لازم داریم.

۲- پیمایش لیست‌ها زمان خطی می‌برد پس نمی‌شود از درخت بازه استفاده کرد. به جای آن از 2d range-tree استفاده می‌کنیم که برای پیاده‌سازی‌اش باید از Weighted B-tree استفاده کنیم. فقط هم باید این تغییر را بدهیم که در گره‌های میانی وقتی دیدیم یک زیردرخت کامل جزو جواب است همانجا تعدادش را برگردانیم و دیگر ادامه ندهیم.

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

داده‌های حجیم: درخت مستطیلی و پرس‌و‌جوهای شامل شدن نقطه

این در مقاله بود اما در اسلایدها نبود.

http://www.cs.au.dk/~large/ioS13/Lecture6.pdf

R-tree

ساختار این داده‌ساختار شبیه B-tree است فقط در هر گره مستطیل نگه می‌داریم. برگ‌ها که مستطیل‌های ورودی هستند و گره‌های میانی کوچکترین مستطیل محیطی مستطیل‌های زیردرخت آن گره هستند.

برای پرس‌و‌جو از ریشه چک می‌کنیم که نقطه در کدام مستطیل می‌افتد.

حالا سوالی که پیش میاد این است که ترتیب مستطیل‌ها را چطور انتخاب کنیم که کمترین زمان را ببرد. چیزی که می‌دانیم این است که هر چه مستطیل‌ها کوچکتر باشند، عمق کمتری باید پایین برویم پس بهتر است.

سه ایده برای دسته بندی مستطیل‌ها در گره‌های میانی داریم:

- مینیمم کردن مساحت مستطیل محیطی

- مینیمم کردن محیط مستطیل محیطی

- مینیمم کردن تقاطع مستطیل‌ها

* اضافه کردن مستطیل:

مستطیل را به آن مستطیلی اضافه کنید که بعد از این کار مساحتش کمتر از همه زیاد می‌شود. به طور بازگشتی ادامه بدهید.

در برگ اگر جا بود اضافه کنید وگرنه split انجام بدهید. (سعی کنید مساحت مینیمم شود.)

(با این کار به گره یک عمق بالاتر یک گره اضافه می‌شود.)

* حذف کردن مستطیل:

حذف می‌کنیم اگر خیلی مستطیل محیطی خالی بود آن را حذف می‌کنیم و به بقیه اضافه می‌کنیم.

...

PR-tree:

مستطیل‌های با بیشترین و کمترین مختصات را در برگ‌ها می‌گذاریم. بقیه را مثل kd-tree تقسیم می‌کنیم.

قابل تعمیم به d بعد است.

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

پیدا کردن پاره‌خط‌های متقاطع با فرض پاره‌خط‌های موازی محورهای مختصات: (در مدل IO)

الگوریتم جاروب معمولی حتی با B-tree هم زمان O(N log_B N+T/B) دارد که خوب نیست. (به خاطر ضریب N)

راه حل: الگوریتم جاروب توزیع شده:

صفحه را به M/B-1 نوار (slab) تجزیه کنید که هر کدام O(N/(M/B)) تا نقطه انتهایی دارند.

در هر نوار از بالا به پایین عمودی جاروب کنید و پاره‌خط‌های متقاطع را به دست بیاورید.

آنهایی که در بیشتر از یک نوار تقاطع دارند را توزیع کنید.

در هر نوار به صورت بازگشتی مسأله را حل کنید.

کاربرد: پیدا کردن مستطیل‌های متقاطع با فرض مستطیل‌های با اضلاع موازی محورهای مختصات

جلسه هشتم: جستجوی بازه‌ای

4-sided

Base tree درخت weight-balanced b-tree با درجه log_B N و تعداد عناصر برگ B روی مولفه x

ارتفاع: log_{log_B N} N

نقاط زیرمجموعه‌ی هر گره را در چهار ساختار ذخیره می‌کنیم: درخت اولویت راست، درخت اولویت چپ، B-tree on y، درخت بازه (priority search)

زمان: O(N/B log_B N / log_B log_B N)

داده‌ساختار ثانویه: (بعد دوم)

نقطه‌های هر slab را به ترتیب y به هم وصل کنید. آنها را روی محور y تصویر کنید.

بازه‌های به دست آمده را در درخت بازه نگه دارید بر حسب y. برای خود نقطه (مثلاً x) یک B-tree بسازید.

درخت kd:

(ادامه دارد.)

جلسه هفتم داده‌های حجیم: جستجوی بازه‌ای

3-sided

راه اول: جاروب صفحه

ایراد: ایستا

پویای آن در مدل RAM ممکن است.

priority search tree (مدل RAM): بر حسب x درخت دودویی جستجو است و بر حسب y هرم است. موقع پرس‌و‌جو اول روی y بعد روی x جستجو می‌کنیم.

مدل IO:

بلوک بندی کنیم.

Base-tree: Weight-balanced B-tree with branching factor B/4 & leaf parameter B on x

Bتای اول هر فرزند را نگه دارد.

برای حالت ایستا persistent B-tree

فضای خطی

برای حذف از ساخت دوباره زیردرخت استفاده کنید.

برای درج به درخت اضافه کنید و rebalance کنید.

برای تجزیه باید ریشه را به روز کنید.

پیدا کردن B تای اول باعث می‌شود زمان بر حسب تعداد اعداد زیر درخت است.

جلسه ششم داده‌های حجیم: درخت بازه‌ها

۱-بعدی: هدف پیدا کردن بازه‌هایی است که شامل یک نقطه‌ی داده شده هستند.

اگر از B-tree روی دو سر بازه‌ها استفاده کنیم به زمان O(log_B N) می‌رسیم.

ایراد: باید به ازای هر بازه یک کوئری بزنیم! O(N log_B N/B) می‌شود.

راه حل: استفاده از persistent B-tree: با جاروب از چپ به راست، فرض می‌کنیم هر بازه زمان وجود یک چیز است و با شروع بازه آن را به درخت اضافه می‌کنیم و با پایان بازه آن را حذف می‌کنیم.

ایراد: نمی‌توان پس از یک بار پردازش بازه اضافه کرد. (چون درخت ایستا است.)

راه حل: از درخت بازه استفاده می‌کنیم.

درخت بازه معمولی (مدل RAM):

برای این کار سر بازه‌ها را به صورت نقطه در نظر می‌گیریم. میانه‌ی این نقاط را پیدا می‌کنیم و ریشه می‌گذاریم و بر اساس آن دو لیست راست و چپ را می‌سازیم. بازگشتی بقیه درخت را می‌سازیم.

فضا: خطی، زمان به روز رسانی: O( log n)

پرس و جو: در هر گره x را با نقطه‌ی آن مقایسه می‌کنیم، بر اساس آن به لیست راست یا چپ (هر کدام که شامل x است) مراجعه می‌کنیم و آن را پیمایش می‌کنیم. اگر به یک بازه‌ی غیرشامل آن نقطه (x) برسیم، بازگشتی مسأله را حل می‌کنیم وگرنه کل آن گره را گزارش می‌کنیم.

درخت بازه در مدل I/O:

درخت را بلوک بندی می‌کنیم و از B-tree برای نگه‌داشتن لیست‌های درون گره‌ها استفاده می‌کنیم.

ایراد: ممکن است مجبور شویم O(log N) تا I/O بزنیم در حالتی که تعداد بازه‌های متقاطع در هر گره کم (یا صفر) باشد.

راه حل: درجه‌ی رأسهای را رادیکال B کنیم. با این کار در هر گره B تا بازه داریم (شروع و پایان آنها رادیکال B حالت دارد). با این کار به جای اینکه به O(log B) تا بازه نگاه کنیم، به ۲ تا بازه نگاه می‌کنیم. (چون قبلاً باید بین کل گره‌های درون بلوک درخت جستجو می‌کردیم الآن فقط در لیست زیربازه‌ها نگاه می‌کنیم.

همان طور که در قسمت ۴ گفتیم، چون در هر گره‌ی این درخت یک داده‌ساختار ثانویه هم دارد ذخیره می‌شود، باید از Weighted B-tree استفاده کنیم.

برای گره‌های با تعداد عنصر کم از persistent B-tree استفاده می‌کنیم.

زمان کوئری در لیست یک گره چون B تا زیربازه داریم، O(B/B log_B B+T_v/B) است که یعنی O(1+T_v/B) که T_v تعداد جوابها است.

فضای کل خطی خواهد بود.

چون در هر گره از مرتبه‌های چندجمله‌ای بر حسب B عنصر داریم، زمانها تغییر نمی‌کنند. پس از B درج در B-tree یک لیست، آن را دوباره می‌سازیم. (چون هزینه‌اش کمتر می‌شود).

ممکن است مجبور شویم از داده‌ساختار زیرلیست‌ها به داده‌ساختار برای مقادیر کوچک عناصر را جابه‌جا کنیم. (به B برسد به multislab list (زیرلیست‌ها) می‌بریم و به B/2 برسد به underflow structure (برای مقادیر کوچک) می‌بریم.)

متوازن کردن آن بر اساس وزن گره (تعداد عناصر در زیردرخت با ریشه آن گره) است و مثل Weighted B-tree انجام می‌شود. فقط برای بازه‌ها، باید آنها را دوباره تقسیم کنیم و آن multislab listهایی که کامل در یکی می‌افتند نگه می‌داریم و بقیه را دیگر لازم نداریم. آنهایی که جداست را با یک پیمایش می‌شود پیدا کرد. باید پدر این گره را هم لیست بازه‌هایش را به روز کنیم چون فرزندان آن تغییر کرده‌اند که این کار را از روی تقسیم بازه‌ها انجام می‌دهیم. برای بازه‌های جدید بعد از تقسیم کردن دوباره multislab list می‌سازیم.