English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider a generalization of the standard cache problem called file-bundlecaching, where different queries (tasks), each containing $l\ge 1$ files,sequentially arrive. An online algorithm that does not know the sequence ofqueries ahead of time must adaptively decide on what files to keep in the cacheto incur the minimum number of cache misses. Here a cache miss refers to thecase where at least one file in a query is missing among the cache files. Inthe special case where $l=1$, this problem reduces to the standard cacheproblem. We first analyze the performance of the classic least recently used(LRU) algorithm in this setting and show that LRU is a near-optimal onlinedeterministic algorithm for file-bundle caching with regard to competitiveratio. We then extend our results to a generalized $(h,k)$-paging problem inthis file-bundle setting, where the performance of the online algorithm with acache size $k$ is compared to an optimal offline benchmark of a smaller cachesize $h<k$. In this latter case, we provide a randomized $O(l \ln\frac{k}{k-h})$-competitive algorithm for our generalized $(h,k)$-pagingproblem, which can be viewed as an extension of the classic marking algorithm.We complete this result by providing a matching lower bound for the competitiveratio, indicating that the performance of this modified marking algorithm iswithin a factor of two of any randomized online algorithm. Finally, we look atthe distributed version of the file-bundle caching problem where there are$m\ge 1$ identical caches in the system. In this case we show that for $m=l+1$caches, there is a deterministic distributed caching algorithm which is$(l^2+l)$-competitive and a randomized distributed caching algorithm which is$O(l\ln(2l+1))$-competitive when $l\ge 2$.

Optimal Online Algorithms for File-Bundle Caching and Generalization to Distributed Caching