کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427705 | 686545 | 2012 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
List update with probabilistic locality of reference
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality.
► We introduce a probabilistic model for list update with locality of reference.
► This model is based on the diffuse adversary model.
► We prove that MTF outperforms other algorithms in this model.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 13, 15 July 2012, Pages 540–543
Journal: Information Processing Letters - Volume 112, Issue 13, 15 July 2012, Pages 540–543
نویسندگان
Reza Dorrigiv, Alejandro López-Ortiz,