A metric cache for similarity search

Similarity search in metric spaces is a general paradigm that can be used in several application fields. It can also be ef-fectively exploited in content-based image retrieval systems, which are shifting their target towards the Web-scale dimen-sion. In this context, an important issue becomes the design of scalable solutions, which combine parallel and distributed architectures with caching at several levels. To this end, we investigate the design of a similarity cache that works in metric spaces. It is able to answer with exact and approximate results: even when an exact match is not present in cache, our cache may return an approximate re-sult set with quality guarantees. By conducting tests on a collection of one million high-quality digital photos, we show that the proposed caching techniques can have a significant impact on performance, like caching on text queries has been proved effective for traditional Web search engines