Online companion caching

被引：8

作者：

Mendel, M ^{[1
]}

Seiden, SS

机构：

[1] Hebrew Univ Jerusalem, Sch Engn & Comp Sci, Dept Comp Sci, IL-91904 Jerusalem, Israel

[2] Louisiana State Univ, Dept Comp Sci, Baton Rouge, LA 70803 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2004年 / 324卷 / 2-3期

关键词：

caching; online algorithms; paging;

D O I：

10.1016/j.tcs.2004.05.015

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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, and the randomized competitive ratio is O(log n log k) and Omega(log n + log k). (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：183 / 200

页数：18

共 12 条

[1] Competitive analysis of randomized paging algorithms [J].

Achlioptas, D ;

Chrobak, M ;

Noga, J .

THEORETICAL COMPUTER SCIENCE, 2000, 234 (1-2) :203-218

[2] A STUDY OF REPLACEMENT ALGORITHMS FOR A VIRTUAL-STORAGE COMPUTER [J].

BELADY, LA .

IBM SYSTEMS JOURNAL, 1966, 5 (02) :78-&

[3] On-line restricted caching [J].

Brehob, M ;

Enbody, R ;

Torng, E ;

Wagner, S .

JOURNAL OF SCHEDULING, 2003, 6 (02) :149-166

[4] Optimal replacement is NP-hard for nonstandard caches [J].

Brehob, M ;

Wagner, S ;

Torng, E ;

Enbody, R .

IEEE TRANSACTIONS ON COMPUTERS, 2004, 53 (01) :73-76

[5]

CHAN KK, 1996, HEWLETT-PACKARD J, V47, P1

[6]

Fiat A, 2002, LECT NOTES COMPUT SC, V2461, P499

[7] COMPETITIVE PAGING-ALGORITHMS [J].

FIAT, A ;

KARP, RM ;

LUBY, M ;

MCGEOCH, LA ;

SLEATOR, DD ;

YOUNG, NE .

JOURNAL OF ALGORITHMS, 1991, 12 (04) :685-699

[8]

JOUPPI N, 1990, P 17 ANN INT S COMP, V18, P364

[9] COMPETITIVE SNOOPY CACHING [J].

KARLIN, AR ;

MANASSE, MS ;

RUDOLPH, L ;

SLEATOR, DD .

ALGORITHMICA, 1988, 3 (01) :79-119

[10]

MCGEOCH LA, 1991, ALGORITHMICA, V6, P816, DOI 10.1007/BF01759073

← 1 2 →