On the Similarity Search With Hamming Space Sketches

Introduction

The ability to produce and store vast volumes of data has brought new challenges to data processing. We focus on the problem of efficient searching in big complex data such as images, videos, sounds, movements and biometrics. Many real-life applications of searching in these domains require efficient processing based on a pairwise similarity of data objects instead of the exact matching. This is caused by the narrow applicability of exact match in real-life scenarios. A typical example of searching that has to utilise similarity instead of the identity is given by the identification of people based on biometric data, e.g. fingerprints, body motions and images of irises, faces and retinas. The biometric data are slightly different when taken repeatedly (Jafri et al., 2009, Hua et al., 2011, Daugman, 2003, Mehrotra et al., 2013) and therefore exact matching cannot be exploited to identify people according to biometrics. We illustrate this by Figure 1 that contains two images of the same iris. Even though both images show the same iris, they are not identical but just quite similar. The appearance of the iris is inferred mainly by the illumination, blinking and even by a particular camera that took the image. Therefore, photos of the same iris are not identical in general.

Figure 1.

Two images of the same iris: identification of a person based on the iris image illustrates the need for search based on the similarity. Images are reprinted from Mehrotra et al., 2013.

Searching based on similarity is also advantageous when searching for general images, sounds, time series, videos, movements, and other complex data, e.g. datasets in biology and chemistry. The complexity of all these data types leads to a usual need to search for similar items instead of the identical. For instance, event detection in videos from surveillance cameras is a nice example of application of a similarity search in these domains, as it is usually implemented as matching scenes similar to given patterns (Turaga et al., 2008). Also, recommender systems (Adomavicius & Tuzhilin, 2005) usually find people who make similar choices as a given person and then recommend the choices of these similar people. Customers can also exploit a similarity search actively to find goods or items. This use-case includes for example the finding of images for websites or wallpapers for electronic devices as illustrated by Figure 2.

Figure 2.

A similarity search may be also exploited to find wallpaper for an electronic device

This chapter is focused on a particular approach to efficient similarity search in complex data domains, such as in multimedia. It targets big data processing, data and information science, and technology. Presented techniques are applicable in services, management, as well as in the government.

The pairwise similarity of complex multimedia objects is not usually evaluated directly using the raw data. Instead, the characteristic features are extracted to describe objects from a specific point of view. We denote these features descriptors, and we assume the global descriptors that describe the whole data objects. The similarity of descriptors thus expresses the similarity of original data objects. We consider these similarities to be the same unless we do not have to distinguish them. This allows us to use term object to denote both, the data object and its descriptor. The ability of descriptors to capture properties and semantics of complex objects has rapidly increased in recent years. With it, the descriptors have grown as well, which has made their efficient processing more difficult. Our goal is not to define new and better descriptors. Our research is motivated by the need to search efficiently in big volumes of data.