Browsing catalogue graphs: Content caching supercharged!!

We consider a generic scenario of content browsing where a client is presented with a catalogue of items of interest. Upon the selection of an item from a page of the catalogue, the client can choose the next item to browse from a list of related items presented on the same page. The system has limited resources to have all items available for immediate access by the browsing client. Therefore, it pays a penalty when the client selects an unavailable item. Conversely, there is a reward that the system gains when the client selects an immediately available item. We formulate the optimization problem of selecting the subset of items that the system should have for immediate access such that its profit is maximized, for the given system resources. We design two techniques for solving the optimization problem in linear time, as a function of the catalogue size. We examine their performance via numerical simulations that reveal their core properties. We also study their operation on actual YouTube data and compare their efficiency relative to conventional solutions. Substantial performance gains are demonstrated, due to accounting for the content graph imposed by the catalogue of items.