Similarity caching
Authors:
Open Access
- 29 June 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 127-136
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.Keywords
This publication has 15 references indexed in Scilit:
- Incremental Clustering and Dynamic Information RetrievalSIAM Journal on Computing, 2004
- Better streaming algorithms for clustering problems2003
- Predictive caching and prefetching of query results in search engines2003
- Randomized algorithms for metrical task systemsTheoretical Computer Science, 1998
- Buffer management in relational database systemsACM Transactions on Database Systems, 1986
- An evaluation of buffer management strategies for relational database systemsAlgorithmica, 1986
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985
- Principles of database buffer managementACM Transactions on Database Systems, 1984
- Operating system support for database managementCommunications of the ACM, 1981