Online companion caching

M. Mendel; Steven S. Seiden

doi:10.1016/j.tcs.2004.05.015

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.
المعرِّفات الرقمية للأشياء	https://doi.org/10.1016/j.tcs.2004.05.015
حالة النشر	نُشِر - 20 سبتمبر 2004
منشور خارجيًا	نعم

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

Funding Information:
Preliminary version of this paper appeared in [7]. ∗Corresponding author. E-mail address: [email protected] (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

الوصول إلى المستند

10.1016/j.tcs.2004.05.015

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@article{7253d868bf5744cb9a220e1410d7c929,

title = "Online companion caching",

abstract = "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).",

keywords = "Caching, Online algorithms, Paging",

author = "M. Mendel and Seiden, \{Steven S.\}",

note = "Funding Information: Preliminary version of this paper appeared in [7]. ∗Corresponding author. E-mail address: [email protected] (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",

year = "2004",

month = sep,

day = "20",

doi = "10.1016/j.tcs.2004.05.015",

language = "אנגלית",

volume = "324",

pages = "183--200",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier BV",

number = "2-3 SPEC. ISS.",

}

TY - JOUR

T1 - Online companion caching

AU - Mendel, M.

AU - Seiden, Steven S.

N1 - Funding Information: Preliminary version of this paper appeared in [7]. ∗Corresponding author. E-mail address: [email protected] (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

PY - 2004/9/20

Y1 - 2004/9/20

N2 - 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).

AB - 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).

KW - Caching

KW - Online algorithms

KW - Paging

UR - https://www.scopus.com/pages/publications/4444264827

U2 - 10.1016/j.tcs.2004.05.015

DO - 10.1016/j.tcs.2004.05.015

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:4444264827

SN - 0304-3975

VL - 324

SP - 183

EP - 200

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2-3 SPEC. ISS.

ER -

Online companion caching

ملخص

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

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا