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)
סטטוס פרסוםפורסם - 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'. יחד הם יוצרים טביעת אצבע ייחודית.

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