Computer Science – Data Structures and Algorithms
Scientific paper
2006-01-30
38th Annual Symposium on Foundations of Computer Science (FOCS '97), 1997, pp. 326
Computer Science
Data Structures and Algorithms
37 pages. Preliminary version appeared in FOCS '97
Scientific paper
10.1109/SFCS.1997.646121
The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model, which attempts to capture the locality of reference. However, the access graph model has a number of troubling aspects. The access graph has to be known in advance to the paging algorithm and the memory required to represent the access graph itself may be very large. In this paper we present truly online strongly competitive paging algorithms in the access graph model that do not have any prior information on the access sequence. We present both deterministic and randomized algorithms. The algorithms need only O(k log n) bits of memory, where k is the number of page slots available and n is the size of the virtual address space. I.e., asymptotically no more memory than needed to store the virtual address translation table. We also observe that our algorithms adapt themselves to temporal changes in the locality of reference. We model temporal changes in the locality of reference by extending the access graph model to the so called extended access graph model, in which many vertices of the graph can correspond to the same virtual page. We define a measure for the rate of change in the locality of reference in G denoted by Delta(G). We then show our algorithms remain strongly competitive as long as Delta(G) >= (1+ epsilon)k, and no truly online algorithm can be strongly competitive on a class of extended access graphs that includes all graphs G with Delta(G) >= k- o(k).
Fiat Amos
Mendel Manor
No associations
LandOfFree
Truly Online Paging with Locality of Reference does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Truly Online Paging with Locality of Reference, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Truly Online Paging with Locality of Reference will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-353601