بررسی دسته بندی و مقایسه الگوریتم های ساخت درخت R با مجموعه درخت های (*)R و (+)R

با توجه به رشد شبکه اینترنت و مطرح شدن کیفیت سرویس های متفاوتی که شبکه ها باید به کاربران ارایه دهند،طبقه بندی بسته ها به عنوان یکی از نیازمندی های مهم و حساس شبکه، هرروز اهمیت بیشتری به خود می گیرد.به گونه ای که می توان گفت برای اغلب سرویس هایی که شبکه ارایه می دهد، مسیریاب ها نیاز دارند که عملطبقه بندی را با سرعت بالا و میزان حافظه مصرفی کم انجام دهند. طبقه بندی بسته ها، مسیریاب های شبکه را قادر بهفراهم کردن خدمات پیشرفته شبکه می کند. عملیات طبقه بندی در درخت R به صورت هندسی صورت میگیرد.نظریه اصلی شاخص فضایی که مهمترین نظریه اساسی پرس و جو می باشد ، محاسبه نظریه ی نزدیکی است.معروف ترین ساختار شاخص ، درخت R می باشد. استراتژی اصلی درخت R جمع آوری نودهای فضایی چندبعدی با مستطیل حداقل محدوده (MBR) می باشد که کوچکترین نود فضایی داخلی مستطیل باشد. بعد از شاخصبندی، بهینه سازی بازیابی اطلاعات در پایگاه داده ی فضایی مهم است. از اینرو جهت بررسی بیشتر موضوع،در این مقاله، شاخص فضایی جدید که متعلق به خانواده R+tree می باشد و مفهوم همپوشانی گره ها راحفظ می کند و R++tree نام دارد، بررسی شده است . نتایج این مقاله نشان می دهد که R++tree در دامنه یپرس و جو ، پرس و جو KNN و پرس و جو Top-k بسیار کارآمدتر از R∗tree می باشد.

Keywords:

درخت (*)R , درخت های R , بسته ها , طبقه بندی