document: Nearest-neighbor caching for content-match applications Motivated by contextual advertising systems and other web applications involving efficiency-accuracy tradeoffs , we study similarity caching . Here , a cache hit is said to occur if the requested item is similar but not necessarily equal to some cached item . We study two objectives that dictate the efficiency-accuracy tradeoff and provide our caching policies for these objectives . By conducting extensive experiments on real data we show similarity caching can significantly improve the efficiency of contextual advertising systems , with minimal impact on accuracy . Inspired by the above , we propose a simple generative model that embodies two fundamental characteristics of page requests arriving to advertising systems , namely , long-range dependences and similarities . We provide theoretical bounds on the gains of similarity caching in this model and demonstrate these gains empirically by fitting the actual data to the model .
doc_bio_tags: O B O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O