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.
מזהי עצם דיגיטלי (DOIs)	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

תקציר

הערה ביבליוגרפית

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי