Similarity caching in large-scale image retrieval

Abstract

Feature-rich data, such as audio-video recordings, digital images, and results of scientific experiments, nowadays constitute the largest fraction of the massive data sets produced daily in the e-society. Content-based similarity search systems working on such data collections are rapidly growing in importance. Unfortunately, similarity search is in general very expensive and hardly scalable.

In this paper we study the case of content-based image retrieval (CBIR) systems, and focus on the problem of increasing the throughput of a large-scale CBIR system that indexes a very large collection of digital images. By analyzing the query log of a real CBIR system available on the Web, we characterize the behavior of users who experience a novel search paradigm, where content-based similarity queries and text-based ones can easily be interleaved. We show that locality and self-similarity is present even in the stream of queries submitted to such a CBIR system. According to these results, we propose an effective way to exploit this locality, by means of a similarity caching system, which stores the results of recently/frequently submitted queries and associated results. Unlike traditional caching, the proposed cache can manage not only exact hits, but also approximate ones that are solved by similarity with respect to the result sets of past queries present in the cache. We evaluate extensively the proposed solution by using the real query stream recorded in the log and a collection of 100 millions of digital photographs. The high hit ratios and small average approximation error figures obtained demonstrate the effectiveness of the approach.

Introduction

Content-based image retrieval (CBIR) (Datta, Joshi, Li, & Wang, 2007) systems support a search paradigms that is becoming day by day more important. Given an image, used as a query by example, users can ask the CBIR system for identifying a given number of images that are the most similar to the query by comparing their visual contents. More specifically, this content-based similarity search is realized in terms of k nearest neighbors (kNN) queries that exploit an appropriate distance measure, defined over the vectors of visual features extracted from each image.

Indeed, such search paradigm fits not only digital images, but also other data types, such as audio-videos, bio-medical data, financial data, and many other scientific data. They constitute the largest fraction of data produced daily in the e-society. All these dominant data sets can be represented in feature spaces that are inherently multi-dimensional. Providing an effective and efficient way to search such multi-dimensional data sets is very challenging. This is not only due to the curse of dimensionality of the visual feature spaces used to represent images, but also to the colossal size of multimedia data over which such content-based search paradigm could be applied. Just to mention some numbers about the hugeness of such data sets, we can refer to a report by an EMC-sponsored research team of International Data Corporation (IDC). This report states that about 281 exabytes (281 billion gigabytes) of digital data were available in the world in 2007, and that by 2011 the aggregate amount of digital data will reach about 1.8 zettabytes (1800 exabytes) (John et al., 2008). Already in 2008, more than 80% of the size of digital contents was related to images: pictures, surveillance videos, TV streams, and so forth. Moreover, if we consider the Web, we know that about 15 billions of images and 220 millions of new photos per week were uploaded to Facebook in May 2009, and about 4 billions of images and 100 millions of new photos per month were uploaded to Flickr in October 2009.

In this paper we focus on the general issue of making CBIR systems scalable, and tackle this goal by proposing a novel similarity cache that intercepts the kNN content-based similarity queries directed to a CBIR system. We show that our cache is able to satisfy a large number of these requests, with exact or approximate results. Since a hit on our cache requires a time much shorter than a kNN query on the whole index, the overall query throughput of the CBIR system is remarkably improved.

Our similarity cache differs from a traditional query result cache (e.g., the one exploited by Web search engines (Fagni, Perego, Silvestri, & Orlando, 2006)), and is based on the mathematical foundations of metric spaces (Chávez, Navarro, Baeza-Yates, & Marroquín, 2001). More specifically, the measurable similarity between the query and the cached objects is exploited for increasing the cache hit rate by allowing approximate cache hits. Besides the traditional exact answers, which occur when the same image query has been submitted in the past and its result set has not yet evicted from the cache, our cache can also return approximate answers. To this end, we exploit the cached visual features of the images belonging to the result sets of previous queries, and use them to identify the associated images that are closest to the query. Obviously, the effectiveness of our similarity cache approach cannot be evaluated in terms of the usual hit ratio only. So in our tests we also considered the quality of the approximate results returned by the cache to show the effectiveness of our approach.

It is worth remarking that, given a query q, when the result set returned by the cache is the same as the one retrieved in the past by the back-end for the same query q, we consider it as an exact hit. Obviously, the CBIR back-end can in turn exploit any query answering approach and return either exact or approximate kNN results sets. In the last case also a cache exact hit actually returns an approximate kNN result. Our similarity cache is thus a general approach to improve CBIR throughput since it can improve the response time of any exact or approximate CBIR back-end.

In Falchi, Lucchese, Orlando, Perego, and Rabitti (2009) we investigated an important characteristic of our similarity cache for CBIR systems: its robustness with respect to the near-duplicate images. A popular image has in fact thousands of slightly different versions in the Web. In case of near-duplicate queries, that are variants of previously cached queries, our similarity cache can return high-quality answers, namely approximate hits, without querying the CBIR back-end.

The experimental setting exploited for testing and evaluating our similarity cache is unique in the panorama of multimedia search. We refer to a real CBIR system, which indexes five MPEG-7 visual descriptors (Scalable Color, Color Structure, Color Layout, Edge Histogram, Homogeneous Texture) of a collection of 100 millions of Flickr photos. The set of visual descriptors associated with this image collection is publicly available for research purposes (CoPhIR: Content-based Photo Image Retrieval Test-Collection (Bolettieri et al., 2009)¹). The CBIR is MUFIN Image Search,² where query images can be either internal or external images – i.e. images belonging to the indexed CoPhIR collection or uploaded by the user.

We analyzed a log of the queries submitted to MUFIN CBIR system between March 20th and October 28th, 2009, with the aim of devising common patterns of user behaviors that can be exploited to better understand user desiderata, improve the design of a large-scale CBIR system and its caching system, and tune its performance. To the best of our knowledge, no similar analysis was conducted before on such kind of query logs. Even if this query log is not huge if compared to the size of commonly studied query logs of Web Search engines, it can be considered representative of Web user behavior. The log in fact records 65,063 queries issued during 5004 sessions by 3390 distinct users. We experimentally show that the distribution of topic popularity existing for text queries (Fagni et al., 2006, Silvestri, 2010) is confirmed to some extent also for content-based image queries. In particular a high level of locality and of self-similarity can be found in the results of the queries submitted by the same and different users during their search sessions, so that the distribution of the popularity of such results is highly skewed. Moreover, we mined from the log of the MUFIN system providing the novel content-based similarity search paradigm, the most common behaviors of users, and measured their preferences for using similarity and/or text queries.

Moreover, we exploited the large experimental setting illustrated above, the MUFFIN query log and the CoPhIR collection, in order to evaluate carefully our similarity caching strategy. To this end we collected, for each similarity query in the log, the Top-200 exact closest results present in the CoPhIR collection, and used them as a sort of ground truth to estimate the quality of the approximate results returned by our cache, and thus to evaluate the actual benefits of using the cache in terms of improved query throughput and approximation error. It is worth mentioning that the preliminary conclusions reported in Falchi et al., 2008, Falchi et al., 2009, where we exploited a synthetic query log and a smaller image database, were not only confirmed but made remarkably stronger: our caching strategy behaves much better with a larger database and a real-life query log.

The rest of the paper is organized as follows. Section 2 reviews related work, while Section 3 discusses the results of the analysis conducted on the query log recording the content-based similarity queries issued by Web users to the MUFIN Image Search system. In Section 4 the issues related to caching the results of similarity search queries are outlined, and the framework for evaluating the efficiency and effectiveness is presented. Section 5 describes experimental settings, and reports on the results of the experiments conducted. Finally, Section 6 draws some conclusions.