תקציר
This paper is concerned with online cachingalgorithms for the (n, k)-companion cache, defined by Brehob et. al. [3]. 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(log n log k)and Ω(log n + log k).
| שפה מקורית | אנגלית |
|---|---|
| כותר פרסום המארח | Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings |
| עורכים | Rolf Möhring, Rajeev Raman |
| מוציא לאור | Springer Verlag |
| עמודים | 499-511 |
| מספר עמודים | 13 |
| מסת"ב (אלקטרוני) | 3540441808, 9783540441809 |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - 2002 |
| פורסם באופן חיצוני | כן |
| אירוע | 10th Annual European Symposium on Algorithms, ESA 2002 - Rome, איטליה משך הזמן: 17 ספט׳ 2002 → 21 ספט׳ 2002 |
סדרות פרסומים
| שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| כרך | 2461 |
| ISSN (מודפס) | 0302-9743 |
| ISSN (אלקטרוני) | 1611-3349 |
כנס
| כנס | 10th Annual European Symposium on Algorithms, ESA 2002 |
|---|---|
| מדינה/אזור | איטליה |
| עיר | Rome |
| תקופה | 17/09/02 → 21/09/02 |
הערה ביבליוגרפית
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 2002.