Skip to Main content Skip to Navigation
Conference papers

Similarity Caching: Theory and Algorithms

Abstract : This paper focuses on similarity caching systems, in which a user request for an object o that is not in the cache can be (partially) satisfied by a similar stored object o , at the cost of a loss of user utility. Similarity caching systems can be effectively employed in several application areas, like multimedia retrieval, recommender systems, genome study, and machine learning training/serving. However, despite their relevance, the behavior of such systems is far from being well understood. In this paper, we provide a first comprehensive analysis of similarity caching in the offline, adversarial, and stochastic settings. We show that similarity caching raises significant new challenges, for which we propose the first dynamic policies with some optimality guarantees. We evaluate the performance of our schemes under both synthetic and real request traces.
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/hal-02411268
Contributor : Giovanni Neglia <>
Submitted on : Thursday, January 23, 2020 - 6:59:41 PM
Last modification on : Tuesday, November 17, 2020 - 12:10:13 PM
Long-term archiving on: : Friday, April 24, 2020 - 4:57:22 PM

File

report.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02411268, version 2

Collections

Citation

Michele Garetto, Emilio Leonardi, Giovanni Neglia. Similarity Caching: Theory and Algorithms. IEEE INFOCOM 2020 - IEEE Conference on Computer Communications, Apr 2020, Beijing, China. ⟨hal-02411268v2⟩

Share

Metrics

Record views

359

Files downloads

623