کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4943707 1437639 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Refreshment of the shortest path cache with change of single edge
ترجمه فارسی عنوان
بقای کوتاهترین حافظه کش با تغییر لبه تک
کلمات کلیدی
کوتاهترین مسیر ذخیره سازی، استراتژی بازخورد پنهان، تغییر شبکه جاده، کوتاهترین مسیرهای تحت تاثیر،
ترجمه چکیده
مشکل کشیدن کوتاهترین مسیرها به طور گسترده مورد مطالعه قرار گرفته است. تمام روش های موجود که به این مسئله پرداخته اند فرض می کنند که شرایط شبکه های جاده با زمان تغییر نمی کند. در این مقاله، ما در حال مطالعه نحوه یابی یک حافظه پنهان در هنگام تغییر یک لبه شبکه جاده زیرزمینی (گراف) هستیم. ساختار حافظه پنهان مبتنی بر بیت مپ برای نگهداری و دسترسی به کوتاهترین مسیر پیشنهاد شده است. در زیر، الگوریتم های توسعه یافته برای شناسایی کوتاه ترین مسیر هایی که تحت تاثیر تغییر لبه قرار دارند. پس از تشخیص مسیرهای آسیب دیده، چندین استراتژی بازخورد مبتنی بر اکتشافی پیشنهادی برای بهروزرسانی حافظه پنهان ارائه شده است. ما یک سری آزمایش ها برای مقایسه عملکرد استراتژی های پیشنهاد شده انجام داده ایم. این نشان می دهد که جایگزین کردن مسیرهای کوتاه شده با مسیرهای جدید که مقادیر سود آنها بزرگترین هستند، باید در برنامه های ذخیره سازی کوتاه ترین مسیر مانند خدمات ناوبری و نقشه ها استفاده شود.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی
The problem of caching shortest paths has been widely studied. All of existing methods that address this problem assume that the condition of road networks does not change with time. In this paper, we study how to refresh a cache when one edge of the underlying road network (graph) changes. A bitmap-based cache structure is proposed to store and give access to shortest paths. In the following, algorithms are developed to detect shortest paths that are affected by the change of edge. After detecting affected paths, several heuristic-based refreshment strategies are proposed to update the cache. We have conducted a series of experiments to compare the performance of proposed strategies. It shows that replacing affected shortest paths with new paths whose benefit values are the largest should be applied in the shortest path caching applications such as navigation and map services.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Expert Systems with Applications - Volume 67, January 2017, Pages 1-11
نویسندگان
, , , , , ,