Similarity caching

Authors:

Abstract
We introduce the similarity caching problem, a variant of classical caching in which an algorithm can return an el- ement from the cache that is similar, but not necessarily identical, to the query element. We are motivated by buer management questions in approximate nearest-neighbor ap- plications, especially in the context of caching targeted ad- vertisements on the web. Formally, we assume the queries lie in a metric space, with distance function d( ; ). A query p is considered a cache hit if there is a point q in the cache that is suciently close to p, i.e., for a threshold radiusr, we have d(p;q) r. The goal is then to minimize the number of cache misses, vis- a-vis the optimal algorithm. As with classical caching, we use the competitive ratio to measure the performance of dierent algorithms. While similarity caching is a strict generalization of clas- sical caching, we show that unless the algorithm is allowed extra power (either in the size of the cache or the thresh- old r) over the optimal oine algorithm, the problem is intractable. We then proceed to quantify the hardness as a function of the complexity of the underlying metric space. We show that the problem becomes easier as we proceed from general metric spaces to those of bounded doubling dimension, and to Euclidean metrics. Finally, we investi- gate several extensions of the problem: dependence of the threshold r on the query and a smoother trade-o between the cache-miss cost and the query-query similarity.

This publication has 15 references indexed in Scilit: