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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 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

!!Conference10th Annual European Symposium on Algorithms, ESA 2002
الدولة/الإقليمإيطاليا
المدينةRome
المدة١٧/٠٩/٠٢٢١/٠٩/٠٢

ملاحظة ببليوغرافية

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

بصمة

أدرس بدقة موضوعات البحث “Online companion caching'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا