تعمیم توری شش وجهی و EJ Networks (موازی)

دریافت
حجم: 3.94 مگابایت

موتور جستجوی گراف موازی

http://graphlab.org/files/osdi2012-gonzalez-low-gu-bickson-guestrin.pdf

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

این مقاله فکر کنم یک روش خاص GAS (Gather Add Scatter) را به کار می‌برد که با توجه به مثالی که زده است تقریباً نیاز به توضیح بیشتری ندارد:

اما چیزی که فکر کنم من شنیده بودم قبلاً GraphLab بود. چون یادم است که اسم ساده‌ای داشت، موازی بود و یک framework برای جستجو بود که بر اساس abstraction بود.

http://en.wikipedia.org/wiki/GraphLab

تابع به روز رسانی page rank به زبان ML

منبع: http://select.cs.cmu.edu/code/graphlab/abstractiononly.pdf

نیمکره راست یا چپ

همین الآن تست نیمکره راست و چپ مغز را دادم و نیمکره راستم فعال‌تر بود که تمایل به بی‌نظمی و خلاقیت و ... دارد. (در مقابل نیمکره چپ که تمایل به منطق و ... دارد.)

الآن تازه می‌فهمم چرا من سوالهای کتاب creative را راحت حل می‌کردم و اینکه چرا سر کلاس دکتر آبام هیچی از درس نمی‌فهمم! چون مثل این است که آدم نسبت به یک رنگ کوررنگی داشته باشد و استاد با آن رنگ روی تخته درس بدهد.

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

جلسه هشتم هندسه محاسباتی پیشرفته

*جستجوی نزدیک‌ترین همسایه

ساختمان داده‌ای بسازید روی مجموعه نقاط d-بعدی P که به ازای نقطه کوئری داده شده نزدیک‌ترین نقطه را به آن برگرداند.

روش دقیق:

دیاگرام ورونوی و point location: پیش پردازش O(nlogn) و کوئری O(log n) و حافظه O(n) (دو بعدی)

برای ابعاد بالاتر حافظه O(n^ceil(d/2)) می‌شود یا می‌توان زمان کوئری را بیشتر کرد و O(n) کوئری (توان کمتر از ۱ بود) و O(n) حافظه داشت.

روش تقریبی:

تعریف مسأله: به ازای نقطه کوئری و شعاع همسایگی داده شده نقطه‌ای برگردانید که فاصله‌ی آن حداکثر ۱+اپسیلون برابر جواب بهینه باشد.

نسخه تصمیم گیری: اگر نقطه‌ای با مشخصات مورد نظر وجود داشت آن را برگردان و در غیر این صورت جواب بده وجود ندارد.

؟؟؟ فکر کنم نسخه‌ی تصمیم گیری فقط این باشه که این نقطه برای این مسأله جواب هست یا نه. (بله/خیر)

*روش ساده برای حالتی که شعاع همسایگی ثابت باشد:

یک توری با اندازه خانه‌های epsilon*r/sqrt(d) می‌سازیم و چک می‌کنیم که آیا هیچ خانه‌ی توری با توپ حول نقطه کوئری تقاطع دارد یا نه. روش: هشینگ

وقتی هش می‌کنیم یک مجموعه از خانه‌های توری برگردانده می‌شوند و باید کل آنها را بگردیم و نقاط آنها را چک کنیم که درون دایره می‌افتند یا نه و در بدترین حالت می‌شود که همه‌ی نقاط درون مکعب و خارج توپ بیفتند. اما چون از هر خانه فقط یک نقطه را نگه داریم مشکل قبلی حل می‌شود و زمان الگوریتم هم epsilon^-d می‌شود که تعداد خانه‌های توری است. دانستن شعاع هم برای ساختن توری لازم است.

*روش ساده ۲ برای حالتی که شعاع همسایگی ثابت باشد:

به جای پیدا کردن همسایه‌های نقطه کوئری، خانه‌های همسایه‌ی نقاط اصلی را پیدا کنیم و به ازای نقطه کوئری فقط باید چک کنیم که خانه‌ی شامل آن نقطه در همسایگی کدام مجموعه از نقاط آمده است. کوئری آن زمان O(1) می‌برد و فضای لازم آن O(epsilon^-d * n) است. چون به ازای هر خانه‌ی توری حداکثر n نقطه همسایه باید برای آن نگه داریم.

Parallel LSH

مرجع: http://padas.ices.utexas.edu/static/papers/sc11-knn.pdf

این پوستر(!) مربوط به LSH موازی است. با دیدن اینکه فقط به عنوان پوستر پذیرفته شده حس می‌کنم هدف الگوریتم‌های sublinear موازی حل کردن مسأله است و تازه می‌فهمم ایده‌ی Hashing چرا برای حل این مسأله استفاده شده است.

نزدیک‌ترین همسایه تقریبی موازی

مرجع: کتاب هندسه محاسباتی موازی Akl S.G., Lyons K.

البته کتاب قدیمی است و نتایج هم احتمالاً قدیمی اند!

کوئری نزدیک‌ترین همسایه و جستجوی بازه‌ای

مرجع: http://cs-wwwarchiv.cs.unibas.ch/lehre/ws06/cs342/slides/6_en_SimilaritySearch_2.pdf

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

(سوال اول تمرین این سری هندسه را هم غلط حل کردم. البته قسمت اولش رو چون بعدی ها رو مستقل ثابت کردم ولی احتمالاً نمره‌ی هیچ کدوم رو نمی‌گیرم.)

نزدیک‌ترین همسایه با درخت چهارتایی

منبع: http://sarielhp.org/teach/1999/course.html

مرجع جدید موازی

http://laurel.datsi.fi.upm.es/_media/proyectos/gopac/programming_massively_parallel_processors.pdf

David B. Kirk and Wen-mei W. Hwu, Programming Massively Parallel Processors, A Hands-on Approach, Morgan Kaufmann, 2010 (supplementary for multicore programming in CUDA)

حل سوالهای الگوریتم پیشرفته یک دانشگاه دیگر

http://pages.cs.wisc.edu/~shuchi/courses/787-F09/sol/

دریافت

دریافت

دریافت

دریافت