Efficient algorithms for multi-file caching Page: 4 of 18
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
Fig. 1. A bipartite graph depiction of a set of jobs and their file requests.
1. Identification of a new caching problem that arises frequently in applications
that deal with vertically partitioned files.
2. Derivation of heuristic algorithms that are simple to implement and take
into account the dependencies among the files.
3. Analysis of the heuristics and derivation of tight bounds from the optimal
solution
4. Extensive simulation results comparing the new algorithm with the tradi-
tional first come first serve.
The rest of the paper is organized as follows. In Section 2 we formally describe
the MFC problem and discuss its complexity. In Section 3 a heuristic greedy al-
gorithm, called Greedy Request Value (GRV) is proposed and its bounds from
the optimal solution are shown using Linear Programming (or LP) relaxation. In
Section 4 a variation on the GRV algorithm is proposed with improved bounds.
In Section 5, we present a simulation framework for evaluating the performance
of the proposed GRV algorithm. Results of the simulation studies, i.e., work-
load characterization and measurements of performance metrics are presented
in Section 6. Conclusions and future work are presented in Section 7.
2 Related Problems and Approximation Complexity
The Multi-File Caching (MFC) problem is defined as follows: Given a collec-
tion of requests R {ri, r2, ... , rn}, each with associated value v(r,), defined
over a set of files F {F1, F2, . .. , Fm}, each with size s(Fl) and a constant M,
a bound on the maximum total values, find a subset R' of the requests, R' C R,
of maximum total value such that the total size of the files needed by R' is at
most M. It is easy to show that in the special case that each file is needed by
exactly one request the MFC problem is equivalent to the knapsack problem.
The MFC problem is NP-hard even if each request has exactly 2 files. This is
done by reduction from the Dense k-subgraph (DKS) problem [2]. An instance
of the DKS problem is defined as follows: Given a graph G (V, E) and a pos-
itive integer k, find a subset V' C V with V' = k that maximizes the totalS 1 2 3 4 5 6 Requests
a b G d e f g Files
W W Cache
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Otoo, Ekow J.; Rotem, Doron & Seshadri, Sridhar. Efficient algorithms for multi-file caching, article, March 15, 2004; Berkeley, California. (https://digital.library.unt.edu/ark:/67531/metadc787058/m1/4/: accessed April 19, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.