Fast Retrieval Algorithm Using EMD Lower and Upper Bounds and a Search Algorithm in multidimensional index

Abstract

Comparison of images requires a distance metric that is sensitive to the spatial location of objects and features. The Earth Mover’s Distance was introduced in Computer Vision to better approach human perceptual similarities. Its computation, however, is too complex for usage in interactive multimedia database scenarios. We develop new upper bounding approximation techniques for the Earth Mover’s Distance which satisfy high quality criteria and fast computation. In order to enable efficient query processing in large databases, we propose an index structure LUBMTree (Lower and Upper Bounds MTree), based of using the lower and upper bounds for the EMD to improve the search time.

Experiments show the performance of research in the  LUBMTree compared with those obtained by  the research in the MTree.

Keywords : indexing, similarity, search, signature, metric EMD, MTree, MAM.