Similarity caching Export

@inproceedings{citeulike:5848031, abstract = {We introduce the similarity caching problem , a variant of classical caching in which an algorithm can return an element from the cache that is similar, but not necessarily identical, to the query element. We are motivated by buffer management questions in approximate nearest-neighbor applications, especially in the context of caching targeted advertisements 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 sufficiently close to p , i.e., for a threshold radius r , we have d ( p,q ) \&\#8804; r . The goal is then to minimize the number of cache misses, vis-\&\#224;-vis the optimal algorithm. As with classical caching, we use the competitive ratio to measure the performance of different algorithms.}, address = {New York, NY, USA}, author = {Chierichetti, Flavio and Kumar, Ravi and Vassilvitskii, Sergei}, booktitle = {PODS '09: Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems}, citeulike-article-id = {5848031}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1559795.1559815}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1559795.1559815}, doi = {10.1145/1559795.1559815}, isbn = {978-1-60558-553-6}, keywords = {caching, evolution, tagging, theory, thesis, vocabulary}, location = {Providence, Rhode Island, USA}, pages = {127--136}, posted-at = {2009-09-29 05:23:58}, priority = {0}, publisher = {ACM}, title = {Similarity caching}, url = {http://dx.doi.org/10.1145/1559795.1559815}, year = {2009} }

TY - CONF ID - citeulike:5848031 L3 - citeulike-article-id:5848031 N2 - We introduce the similarity caching problem , a variant of classical caching in which an algorithm can return an element from the cache that is similar, but not necessarily identical, to the query element. We are motivated by buffer management questions in approximate nearest-neighbor applications, especially in the context of caching targeted advertisements 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 sufficiently close to p , i.e., for a threshold radius r , we have d ( p,q ) ≤ r . The goal is then to minimize the number of cache misses, vis-à-vis the optimal algorithm. As with classical caching, we use the competitive ratio to measure the performance of different algorithms. CY - Providence, Rhode Island, USA SN - 978-1-60558-553-6 AD - New York, NY, USA EP - 136 TI - Similarity caching PB - ACM T2 - PODS '09: Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems SP - 127 KW - caching KW - evolution KW - tagging KW - theory KW - thesis KW - vocabulary AU - Chierichetti, Flavio AU - Kumar, Ravi AU - Vassilvitskii, Sergei PY - 2009/// UR - http://dx.doi.org/10.1145/1559795.1559815 ER -