Part II: Efficient matching

Speaker: Herve Jegou
Large scale image recognition requires handling and searching into databases containing from millions to billions of high-dimensional vectors. This raises an efficiency problem, but also the problem of memory resources. In this part, we will present the main strategies to address these issues, namely hashing techniques and encoding techniques. As an important example, we will consider the case of Locality Sensitive Hashing [IM98, Ch02]. We will cover the main advances and trends in this field, including several binarization strategies (see [WTF08, RL09, WFT12] as a few examples) and the use of asymmetric distances [DCL08, JDS11, GP11]. We will then show that the search problem is advantageously viewed as a compression problem and present recent techniques based on compression [CTC09] such as Product Quantization (PQ) compressed-domain search [JDS11]. Finally, we will present the most successful hybrid approaches [JDS08, JDS11, JPD12] which combine the advantages of hashing (sub-linearity) with the compactness of encoding techniques.
Hervé Jégou,
Jun 28, 2013, 9:56 AM