ملخص
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 |
| المعرِّفات الرقمية للأشياء | |
| حالة النشر | نُشِر - 2002 |
| منشور خارجيًا | نعم |
| الحدث | 10th Annual European Symposium on Algorithms, ESA 2002 - Rome, إيطاليا المدة: ١٧ سبتمبر ٢٠٠٢ → ٢١ سبتمبر ٢٠٠٢ |
سلسلة المنشورات
| الاسم | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| مستوى الصوت | 2461 |
| رقم المعيار الدولي للدوريات (المطبوع) | 0302-9743 |
| رقم المعيار الدولي للدوريات (الإلكتروني) | 1611-3349 |
!!Conference
| !!Conference | 10th Annual European Symposium on Algorithms, ESA 2002 |
|---|---|
| الدولة/الإقليم | إيطاليا |
| المدينة | Rome |
| المدة | ١٧/٠٩/٠٢ → ٢١/٠٩/٠٢ |
ملاحظة ببليوغرافية
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
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.