Metric Indexing for the Earth Mover's Distance

The Earth Mover's Distance (EMD) has become a popular choice for applications in similarity search, particularly in applications such as few-shot image classification where it is observed to match human perceptions of image differences better than other distance measures such as the Euclidean distance. Currently, in domains such as few-shot image classification, it is common to use exhaustive search during query time which is inefficient in applications using distances with high computational complexity such as the EMD. Since the space in these applications is not guaranteed to be a vector space, existing techniques such as product quantization cannot be applied. In this paper, we study the application of metric space indexing structures towards the reduction of the number of EMD computations needed during query time. We conduct experiments on several image datasets in order to identify the advantages and disadvantages of different metric space data structures. These experiments have not been performed in the context of the EMD before and demonstrate that the VP-tree is more robust to increases in dataset complexity in this domain than comparable metric indexing data structures. Furthermore, we combine these data structures with deep feature extraction to develop a method for efficient deep image retrieval in metric spaces. Taking inspiration from distance stretching methods in the previous literature, we develop a novel approximate nearest neighbor algorithm for k-NN search that can greatly reduce the number of distance computations needed for retrieval without significantly changing k-NN accuracy.