GRADES: Gradient Descent for Similarity Caching
- Others:
- University of Massachusetts [Amherst] (UMass Amherst) ; University of Massachusetts System (UMASS)
- Université Côte d'Azur (UCA)
- Network Engineering and Operations (NEO ) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- Università degli studi di Torino = University of Turin (UNITO)
- Politecnico di Torino = Polytechnic of Turin (Polito)
Description
A similarity cache can reply to a query for an object with similar objects stored locally. In some applications of similarity caches, queries and objects are naturally represented as points in a continuous space. Examples include 360° videos where user's head orientation-expressed in spherical coordinates determines what part of the video needs to be retrieved, and recommendation systems where the objects are embedded in a finite-dimensional space with a distance metric to capture content dissimilarity. Existing similarity caching policies are simple modifications of classic policies like LRU, LFU, and qLRU and ignore the continuous nature of the space where objects are embedded. In this paper, we propose GRADES, a new similarity caching policy that uses gradient descent to navigate the continuous space and find the optimal objects to store in the cache. We provide theoretical convergence guarantees and show GRADES increases the similarity of the objects served by the cache in both applications mentioned above.
Abstract
International audience
Additional details
- URL
- https://hal.archives-ouvertes.fr/hal-03484133
- URN
- urn:oai:HAL:hal-03484133v1
- Origin repository
- UNICA