Method for information retrieval in broadcast disk systems

Abstract

A paging method for information retrieval from broadcast disk systems is described. In response to a page request (e.g., a request for an item of data), the method selectively stores and evicts, in and from a fast memory, pages of data broadcasted by the broadcast disk system. The methods proceeds using a three-“color” labelling scheme, wherein the label assigned to a broadcasted page is based on how recently a given page was last requested. If a requested page is stored in fast memory, then the request is immediately served. If the requested page is not stored in fast memory, the request cannot be served until the requested page is broadcasted. While waiting for the requested page to be broadcasted, certain “somewhat-recently” requested pages are “prefetched,” wherein they are stored in fast memory even though there is no pending request for such pages. Since the size of the fast memory is very small compared to the amount of information being broadcasted, only a small amount of the available information can be stored and there will be significant turnover in the particular stored pages as a function of the page requests. Pages are selected for eviction based upon the “cost” (to the competitive performance of the method) to replace the evicted page, wherein the least costly page to replace is evicted. The present method achieves a bounded competitive ratio of O (n log k), where n is the number of pages being broadcasted and k is the size of the fast memory.