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

۱- با استفاده از روش لگاریتمی یک سری 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 می‌سازیم.

درخت جستجو در مدل I/O. قسمت سوم: داده‌ساختارهای پویا در الگوریتم‌ها (جلسه پنجم)

در حالت عادی (مدل RAM نه I/O)، می‌توانیم از BST برای مرتب کردن عناصر استفاده کنیم. یعنی عناصر را یکی یکی به BST اضافه کنیم و با پیمایش درخت یک لیست مرتب از عناصر در زمان بهینه N log N به دست می‌آید.

اما مثلاً B-tree را با شروع از یک درخت M/B عنصری، به این هزینه می‌رسد:

sum_{i=0}^{N} log_(B) (M/B+Bi) = N log_(B) N/B

که با جواب بهینه در ضریب زیر متفاوت است:

B log_(B) M/B

که مقدار زیادی است.

یک راه حل ساختن B-tree از پایین به بالا است که با مرتب کردن عناصر امکان پذیر است. اما این کار را نمی‌شود با مثلاً persistent B-tree انجام داد. ما دنبال یک روش داده‌ساختارهای پویا در حالت کلی هستیم.

Buffer-tree:

یک B-tree با درجه رأس M/B و تعداد عناصر در هر برگ B در نظر می‌گیریم که هر گره یک بافر با اندازه‌ی M دارد.

هر وقت بافر یک گره پر می‌شود، عناصر را به عمق بعدی درخت می‌فرستیم. هر بلوک در هر عمق تعداد ثابتی بار پردازش می‌شود پس برای خالی کردن بافر، M/B زمان لازم است.

(زمان‌ها مثل قبل)

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

برای مرتب سازی با این درخت، اول عناصر بافر را مرتب کنید، بعد آنها را با عناصر درخت که مرتب هستند ادغام کنید. این کار می‌تواند باعث پر شدن بافر شود که باید آن را در فرزندان تخلیه کنید. این کار را به صورت بازگشتی برای فرزندان هم انجام بدهید.

خالی کردن بافر با اندازه x زمان O(x/B+M/B) می‌برد که به O(x/B) تا I/O نیاز دارد.

ممکن است در این فرایند تعداد عناصر در بافر از M بیشتر باشند (وقتی که از گره بالایی آمده ولی هنوز اضافه نشده) ولی فقط Mتای آنها حداکثر نامرتب هستند.

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

همیشه این حالت برای درخت حفظ می‌کنیم که همه‌ی مسیرهای از ریشه تا برگ بافرشان خالی باشد. با این کار راحت می‌توانیم متوازن کنیم. (با ترکیب و تجزیه گره‌ها)

برای این کار باید به ترتیب BFS بافرها را خالی کنیم.

کاربرد buffer-tree در ساخت صف اولویت:

کوچکترین عنصر، در سمت چپ‌ترین مسیر قرار دارد، پس با O(1/B log_{M/B} N/B) تا I/O می‌توان به آن رسید.

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

اما به صورت سرشکنی همچنان در همان زمان می‌شود عنصر را حذف کرد.

درخت جستجو در مدل I/O: قسمت دوم: ابعاد بالاتر (جلسه چهارم داده‌های حجیم)

در این جلسه هدف جواب دادن کوئری‌های پیدا کردن نقاط در بازه‌ی [x1,x2]*[y1,y2] است.

دو بعدی:

یک BST روی x می‌سازیم و در هر گره‌ی آن یک BST روی y می‌سازیم.

ایراد:

زمانی که می‌خواهیم درخت را روی بعد x آن متوازن کنیم، داده‌ساختارهای روی بعد y باید از اول ساخته شوند.

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

درخت BB[alpha]-tree

نسبت وزن فرزند چپ و راست یک گره بین alpha,1-alpha است (alpha < 1). پس ارتفاع لگاریتم N است.

برای متوازن کردن از چرخش استفاده می‌کنیم. پیاده‌سازی آن در مدل I/O سخت است. ولی مشکل هزینه‌ی بعد دوم در متوازن کردن را حل می‌کند.

Weigh-balanced B-tree

ترکیب BB[alpha]-tree و B-tree است. به جای اینکه محدودیت درجه داشته باشیم، محدودیت وزن داریم. متوازن کردن آن مشابه B-tree با ادغام و جداسازی گره‌ها انجام می‌شود.

دو پارامتر b و k برای این درخت وجود دارد که برگها بین k/4,k عنصر دارند و گره‌های سطح l وزن بین b^l * k, 1/4*b^l *k دارند. (اصلاحیه: در پست جلسه‌ی سوم درخت (a,b) ریشه بین 2,b عنصر دارد استثناً) ریشه هم باید بیشتر از یک فرزند داشته باشد. در نتیجه‌ی این محدودیت وزن گره‌های میانی بین 1/4b,4b فرزند دارند.

بقیه (حذف و درج) مشابه قبل.

persistent tree:

می‌خواهیم امکان درج و حذف (update) روی داده‌ساختار فعلی داشته باشیم و بتوانیم برای بازه‌ای در گذشته هم پرس‌و‌جو داشته باشیم.

راه حل بدیهی: نگه داشتن یک نسخه از ساختمان داده به ازای هر زمان. (اضافه کردن یک بعد به ساختمان داده برای زمان آن)

ایراد: به روز رسانی زمانی معادل خواندن همه‌ی داده‌ها لازم دارد. زمان ساختمان داده هم به طور مشابه متناسب با خواندن توان دوم اندازه ورودی می‌شود.

راه حل بهتر: به هر عنصر یک بازه‌ی زمانی اضافه کنیم. می‌شود این بازه‌های وجود را با تکرار یک عنصر طوری ساخت که یک B-tree روی عناصر زنده داشته باشیم. برای این کار باید بلوک‌هایی که تعداد عناصر حذف شده (که آنها را فقط علامت می‌زنیم چون بعداً برای کوئری به گذشته لازمشان خواهیم داشت) زیادی دارند را به عنوان حذف شده علامت بزنیم. برای این کار بقیه عناصر بلوک حذف شده را به عنوان عنصر جدید درج می‌کنیم. وقتی یک بلوک حذف می‌شود، در پدر آن اشاره‌گرش را هم به عنوان حذف شده علامت می‌زنیم.

جلسه سوم داده‌های حجیم (درخت جستجو در مدل I/O)

اگر مثل حالت معمولی یک BST بسازیم زمان متناسب با log N می‌شود که زیاد است. ما می‌خواهیم به log_B N برسانیمش. (احتمالاً چون با روشی مثل آخر جلسه‌ی قبل می‌شود ثابت کرد که کران پایینش این است.)

برای این کار از روشی به نام BFS Blocking استفاده می‌کنیم که همان طور که از اسمش پیداست مشابه BFS درخت را بلوک‌بندی می‌کند. این درخت جواب بهینه را به ما می‌دهد که O(log_B N) برای کوئری (ارتفاع درخت) است و برای جستجوی یک بازه و گزارش کردن نقاط آن O( log_B N+ T/B) است. (T تعداد عناصر بازه = اندازه خروجی)

ایراد: برای به روز رسانی این درخت باید مثل AVL-tree زحمت زیادی کشید. در ضمن باید برگ‌ها هم بلوک‌بندی شده باشند (داده‌های آنها پشت سر هم باشد).

راه حل: استفاده از B-tree

به جای اینکه بیایم با متوازن کردن ارتفاع درخت را درست نگه داریم، کافی است روی درجه‌ی خروجی (تعداد فرزندان هر گره) شرط بگذاریم. چون این دلیل اصلی حفظ شدن ارتفاع درخت در BFS-blocking است. برای این کار قرار می‌دهیم درجه‌ی هر رأس theta(B) باشد. با این کار به B-tree می‌رسیم که عمل متوازن کردن در آن با ادغام یا جداکردن گره‌ها انجام می‌شود ولی همیشه درجه‌ی رأسها از مرتبه‌ی B است.

(a,b)-tree درختی است که در آن گره‌های یک سطح بین a تا b عنصر دارند. پس ارتفاع آن حداکثر O(log_a N) است. اگر a و b از مرتبه‌ی B باشند به همان جواب بهینه می‌رسیم. اما حالا این ساختمان داده‌ی جدید برای اضافه‌کردن و حذف کردن عنصر هم مشکلی ندارد و می‌تواند در همان زمان بهینه به این کوئری‌ها هم جواب بدهد. با ادغام و جدا کردن گره‌های میانی هر وقت که از بازه‌ی a,b خارج می‌شوند.

با تحلیل سرشکنی (amortized) می‌شود مقادیر a,b را پیدا کرد که بین دو ادغام و جداشدن به مقدار لازم فاصله باشد که سرشکن آن O(1) شود. (که چون در هر عمق انجام می‌شود لگاریتمی می‌شود).

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

در این مدل ترتیب دسترسی به داده‌ها خیلی مهم است. (اگر از قسمت قبل یادتان باشد برای خواندن تصادفی باید زمان متناسب با N مصرف کنیم در حالی که برای خواندن متوالی زمان متناسب با N/B که B یک عدد بزرگ است.)

صف: دو عمل این ساختمان داده اضافه کردن به ابتدا و حذف کردن از انتها است. پس هر کدام یک سری عمل خواندن/نوشتن متوالی است که زمان آن متناسب با میزان داده تقسیم بر B است. پس هر عمل push و pop زمان O(1/B) می‌برد.

پشته: مثل صف می‌شود گفت زمان O(1/B) می‌خواهد.

مرتب‌سازی با استفاده از صف:

ادغام:

کمتر از M/B صف مرتب‌شده داریم. آنها را به این صورت ادغام می‌کنیم که بلوک اول هر کدام را در حافظه‌ی اصلی می‌ریزیم. (چون تعداد لیست‌ها از M/B کمتر است در حافظه جا می‌شود). در هر بار انجام این کار یک بلوک از جواب به دست می‌آید (چون بلوک اول همه‌ی صف‌ها را داریم). آن را در یک صف جدید می‌ریزیم و همین کار را ادامه می‌دهیم. زمان این کار O(N/B) می‌شود.

تقسیم:

برای تقسیم کردن لیست (صف) به کمتر از M/B لیست نامرتب که عناصر هر لیست از لیست بعدی آن کمتر باشد با فرض اینکه مکان برش‌ها (برای حالت دو تایی میانه) را داشته باشیم. هر بلوک را تقسیم می‌کنیم و زمانی که بلوک مربوط به یک صف کامل شد I/O می‌زنیم تا آن را بنویسیم.

مرتب‌سازی ادغامی:

با استفاده از تابع ادغام می‌توانیم با شروع از لیست‌های M عضوی مرتب (چون این تعداد در حافظه جا می‌شود) و ادغام آنها به لیست مرتب شده برسیم. تعداد I/Oها به صورت یک تصاعد هندسی است که جمله‌ی اول آن N/M است (تعداد لیست‌های اولیه) و هر بار چون تعداد لیست‌ها تقسیم بر M/B می‌شود (ادغام می‌شوند)، بر این تعداد تقسیم می‌شود. (چون زمان ادغام متناسب با تعداد لیست‌ها است).

تعمیم مرتب‌سازی سریع:

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

تحلیل پیدا کردن میانه (Selection):

؟؟؟

کران پایین مرتب‌سازی در مدل I/O:

باید بعد از یک I/O بگوید چقدر از N! حالت ورودی حذف می‌شوند و فرض کرده M عدد در حافظه است و با یک I/O حداکثر B عنصر خوانده/نوشته می‌شوند و بیشترین تعداد حالت‌هایی که این کار ایجاد می‌کند را حساب می‌کند. بعد تعداد کل حالت‌ها را بر این تقسیم می‌کند. چون به این بیشترین می‌شود رسید مشکلی پیش نمی‌آید. اما اگر نمی‌شد به نظرم باید این را هم حساب می‌کرد که آیا واقعاً می‌شود که چنین اتفاقی بیفتد یا نه. (پر بودن حافظه و ...)