Earth Mover's Distance
For modern information systems, the efficient retrieval of multimedia data and complex objects is a crucial task for many applications including medical imaging, video analysis, molecular biology or mechanical engineering. Whereas the mapping of complex objects to feature vectors has proven its usefulness in many examples, the limitations of the common Euclidean distance become obvious in case of correlated dimensions in the feature space. In order to face these problems, the Earth Mover's Distance (EMD) explicitly regards connections of the components while being based on a ground distance schema. Whereas algorithms to compute the EMD for pairs of vectors exist, they are too expensive to be applied to large database of 100,000 or millions of objects. The goal of this research is to develop new algorithms to efficiently support EMD-based similarity search on very large databases.