Saturday, July 18, 2009

Caching and Similarity

Can you increase the hit ratio in a cache, when you allow a similarity match instead of an exact match?

Yahoo's paper "Nearest-Neighbor Caching for Content-Match Applications" answers this question in the context of search ads matching. Similarity is defined by using LSH, and different cache eviction strategies are compared.

One observation that I have is that Ads are continuosly changing their costs and benefits as time passes. As a consequence, cache should prevent similarity match with an ad that changed his value in the meantime. I think there is an additional constrain which have not been considered in the paper.

No comments:

Post a Comment