Online companion caching

Amos Fiat; Manor Mendel; Steven S. Seiden

doi:10.1007/3-540-45749-6_45

Online companion caching

Amos Fiat
, Manor Mendel
, Steven S. Seiden

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

תקציר

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)	https://doi.org/10.1007/3-540-45749-6_45
סטטוס פרסום	פורסם - 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.

גישה למסמך

10.1007/3-540-45749-6_45

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

Link to publication in Scopus

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

Fiat, A., Mendel, M., & Seiden, S. S. (2002). Online companion caching. ב- R. Möhring, & R. Raman (עורכים), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings (עמודים 499-511). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 2461). Springer Verlag. https://doi.org/10.1007/3-540-45749-6_45

@inproceedings{733d5a33acfa44ad8f05e195163cdabd,

title = "Online companion caching",

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

author = "Amos Fiat and Manor Mendel and Seiden, \{Steven S.\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 10th Annual European Symposium on Algorithms, ESA 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45749-6\_45",

language = "אנגלית",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "499--511",

editor = "Rolf M{\"o}hring and Rajeev Raman",

booktitle = "Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings",

address = "גרמניה",

}

Fiat, A, Mendel, M & Seiden, SS 2002, Online companion caching. ב- R Möhring & R Raman (עורכים), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), כרך 2461, Springer Verlag, עמודים 499-511, 10th Annual European Symposium on Algorithms, ESA 2002, Rome, איטליה, 17/09/02. https://doi.org/10.1007/3-540-45749-6_45

Online companion caching. / Fiat, Amos; Mendel, Manor; Seiden, Steven S.
Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. עורך / Rolf Möhring; Rajeev Raman. Springer Verlag, 2002. עמוד 499-511 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 2461).

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

TY - GEN

T1 - Online companion caching

AU - Fiat, Amos

AU - Mendel, Manor

AU - Seiden, Steven S.

PY - 2002

Y1 - 2002

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

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

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

U2 - 10.1007/3-540-45749-6_45

DO - 10.1007/3-540-45749-6_45

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:84938085785

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 499

EP - 511

BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer Verlag

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

Online companion caching

תקציר

סדרות פרסומים

כנס

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

גישה למסמך

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

טביעת אצבע

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