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

تعریف مدل I/O:

مدل حافظه خارجی (External Memory) که به آن مدل آگاه از کش (Cache Aware) هم می‌گویند. در این مدل ما اندازه‌ی بلوک دیسک (B) و اندازه‌ی حافظه RAM یعنی M را می‌دانیم. هدف این است که با کمترین تعداد I/O، (در هر I/O یک بلوک از حافظه خوانده یا نوشته می‌شود) را به دست آوریم.

در این مدل فرض می‌کنیم که M>B^2 است. (در یک سری الگوریتم‌ها لازم می‌شود!)

زمان عملیات متداول در این مدل:

خواندن متوالی: در حالت عادی زمان آن متناسب با N (تعداد عناصر ورودی) است اما اینجا N/B است چون Bتا Bتا خوانده می‌شود.

مرتب‌سازی: در حالت عادی زمان آن N log N است اما اینجا N/B log_(M/B) N/B است.

جایگشت دادن: (فکر کنم منظور پیدا کردن جایگشت بعدی باشد) درحالت عادی زمان N می‌برد، در این مدل زمان مینیمم N و N/B log_(M/B) N/B می‌برد.

جستجو: در حالت عادی (جستجوی دودویی) زمان log N می‌برد. اینجا زمان log_B N می‌برد.

* B خیلی در این روابط مهم است چون بزرگ است و باعث می‌شود مثلاً N/B<<N باشد.

مدل بی‌خبر از کش:

در این مدل ما B را نمی‌دانیم و می‌تواند حتی سلسله مراتبی باشد. برای حالت سلسله مراتبی من اولش فکر می‌کردم باید یک B معادل پیدا کنیم اما الآن دیدم نوشته است که به ازای هر مرحله‌ی کش یک بار اجرای الگوریتم را در نظر می‌گیریم. یعنی مثل این است که به تعداد سلسله مراتب آن داریم مسأله را حل می‌کنیم. (این مدل پروژه کارشناسی ارشد یک نفر توی ام‌آی‌تی بوده!)

مدل جویباری:

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