درخت بازه ای توزیع شده با استفاده از مدل نگاشت - کاهش

درخت بازه ای یکی از مهمترین داده ساختارها با کاربردهای متعدد در محاسبات هندسی بشمار می رود. در این درخت به عنوان یک داده ساختار، هر گره بازه هایی از یک مجموعه مفروض را نگهداری می کند که این امکان را می دهد بصورت پویا، مقادیر اعضای مجموعه تغییر داده شوند و با پیچیدگی زمانی لگاریتمی این تغییرات در درخت بازه ای اعمال گردند. همچنین به ازای هر بازه درخواست شده در مجموعه مفروض، محاسبه مقادیری مانند حاصل جمع، بیشینه، کمینه و غیره در پیچیدگی زمانی لگاریتمی امکان پذیر می باشد. در این مقاله قصد داریم با ارائه یک روش جدید، با استفاده از مدل نگاشت - کاهش، درخت بازه ای توزیع شده ای را ایجاد کنیم، تا با کمک پردازش موازی ایجاد داده ساختار را در پیچیدگی زمانی و جستجوی بازه های درخواست شده از یک مجموعه مفروض را در پیچیدگی زمانی انجام دهد. که n تعداد اعضای مجموعه مفروض و p تعداد پردازشگرهای درون خوشه می باشند.

کلیدواژه ها:

پردازش موازی ، داده ساختار ، درخت بازه ای ، مدل نگاشت - کاهش