جستجوی موازی در درختهای IPR به شکل بهینه

سال انتشار: 1384
محل انتشار: یازدهمین کنفرانس سالانه انجمن کامپیوتر ایران
کد COI اختصاصی: ACCSI11_146
زبان مقاله: فارسی
تعداد مشاهده: 1094

نویسندگان

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

چکیده

درخت IPR متوازن ترین نوع درخت جستجوی دودویی است این ساختمان داده کارامد، دارای کاربردهای فراوانی در سیستمهای ذخیره و بازیابی اطلاعات می باشد و به عنوان یک شاخص استاندارد، جهت پیاده سازی عملیات لغتنامه ای مورد ا ستفاده قرار می گیرد . ما در اینجا، الگوریتمی برای انجام عمل موازی جستجویk کلید به صورت همزمان، در درخت IPR ارائه می کنیم. عمل مذکور با هزینه بهینه، روی مدل موازی EREW PRAM با به کارگیری k پردازشگر در زمان O(log k+log n قابل پیاد هسازی است، که n تعداد گر ه های موجود در درخت IPR می باشد. جهت جلوگیری از تداخل و دسترسی همزمان به حافظه مشترک PRAM یک روش زمانبندی عملی پردازشگرها، پیشنهاد کرده ایم، که احتیاج به حافظه اضافی ندارد و در مرتبه زمانی الگوریتم، نیز بی تاثیر است

کلیدواژه ها

درختIPR،درخت ج ستجوی متوازن، الگوریتم موازی، عملیات لغتنامه ای PRAM

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.