Online companion caching

M. Mendel, Steven S. Seiden

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

This paper is concerned with online caching algorithms for the (n,k)-companion cache, defined by Brehob et al. (J. Scheduling 6 (2003) 149). In this model the cache is composed of two components: a k-way set-associative cache and a companion fully associative cache of size n. We show that the deterministic competitive ratio for this problem is (n+1)(k+1)-1, and the randomized competitive ratio is O(lognlogk) and Ω(logn+logk).

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)183-200
عدد الصفحات18
دوريةTheoretical Computer Science
مستوى الصوت324
رقم الإصدار2-3 SPEC. ISS.
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 20 سبتمبر 2004
منشور خارجيًانعم

ملاحظة ببليوغرافية

Funding Information:
Preliminary version of this paper appeared in [7]. ∗Corresponding author. E-mail address: mendelma@cs.huji.ac.il (M. Mendel). 1The 'rst named author would like to dedicate this paper in memory of Steven Seiden. 2Partially supported by the Louisiana Board of Regents Research Competitiveness Subprogram

بصمة

أدرس بدقة موضوعات البحث “Online companion caching'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا