Efficient EMD-based similarity search in multimedia databases via flexible dimensionality reduction

ABSTRACT

The Earth Mover's Distance (EMD) was developed in computer vision as a flexible similarity model that utilizes similarities in feature space to define a high quality similarity measure in feature representation space. It has been successfully adopted in a multitude of applications with low to medium dimensionality. However, multimedia applications commonly exhibit high-dimensional feature representations for which the computational complexity of the EMD hinders its adoption. An efficient query processing approach that mitigates and overcomes this effect is crucial. We propose novel dimensionality reduction techniques for the EMD in a filter-and-refine architecture for efficient lossless retrieval. Thorough experimental evaluation on real world data sets demonstrates a substantial reduction of the number of expensive high-dimensional EMD computations and thus remarkably faster response times. Our techniques are fully flexible in the number of reduced dimensions, which is a novel feature in approximation techniques for the EMD.

REFERENCES

• 1: Ira Assent , Andrea Wenning , Thomas Seidl, Approximation Techniques for Indexing the Earth Mover's Distance in Multimedia Databases, Proceedings of the 22nd International Conference on Data Engineering, p.11, April 03-07, 2006 [doi>10.1109/ICDE.2006.25]
• 2: C. Bauckhage. Tree-based signatures for shape classification. In Proceedings of the IEEE International Conference on Image Processing (ICIP), pages 2105--2108, 2006.
• 3: Thomas Deselaers , Daniel Keysers , Hermann Ney, Discriminative Training for Object Recognition Using Image Patches, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.157-162, June 20-26, 2005 [doi>10.1109/CVPR.2005.134]
• 4: Anthony Y. Fu , Liu Wenyin , Xiaotie Deng, Detecting Phishing Web Pages with Visual Similarity Assessment Based on Earth Mover's Distance (EMD), IEEE Transactions on Dependable and Secure Computing, v.3 n.4, p.301-311, October 2006 [doi>10.1109/TDSC.2006.50]
• 5: F. Hillier and G. Lieberman. Introduction to Linear Programming. McGraw-Hill, 1990.
• 6: P. Indyk and N. Thaper. Fast image retrieval via embeddings. In Workshop on Statistical and Computational Theories of Vision (SCTV), 2003.
• 7: K. Grauman and T. Darrell. Fast contour matching using approximate Earth Mover's Distance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR), pages 220--227, 2004.
• 8: L. Kaufman and P. J. Rousseeuw. Finding groups in data. An introduction to cluster analysis. Wiley-Interscience, 1990.
• 9: O. Klein and R. C. Veltkamp. Approximation algorithms for the Earth Mover's Distance under transformations using reference points. Technical Report UU-CS-2005-003, Department of Information and Computing Sciences, Utrecht University, 2005.
• 10: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 11: Yingmei Lavin , Rajesh Batra , Lambertus Hesselink, Feature comparisons of vector fields using earth mover's distance, Proceedings of the conference on Visualization '98, p.103-109, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 12: T. M. Lehmann, M. O. Güld, C. Thies, B. Fischer, K. Spitzer, D. Keysers, H. Ney, M. Kohnen, H. Schubert, and B. B. Wein. Content-based image retrieval in medical applications. Methods of Information in Medicine, 43(4):354-361, 2004.
• 13: T. Lehmann et al. IRMA project site. http://www.irma-project.org/datasets en.php, 2005.
• 14: V. Ljoså, A. Bhattacharya, and A. K. Singh. Indexing spatially sensitive distance measures using multi-resolution lower bounds. In Proceedings of the International Conference on Extending Database Technology (EDBT), pages 865--883, 2006.
• 15: Jan Puzicha , Joachim M. Buhmann , Yossi Rubner , Carlo Tomasi, Empirical Evaluation of Dissimilarity Measures for Color and Texture, Proceedings of the International Conference on Computer Vision-Volume 2, p.1165, September 20-25, 1999
• 16: Yossi Rubner , Carlo Tomasi, Perceptual Metrics for Image Database Navigation, Kluwer Academic Publishers, Norwell, MA, 2001
• 17: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, A Metric for Distributions with Applications to Image Databases, Proceedings of the Sixth International Conference on Computer Vision, p.59, January 04-07, 1998
• 18: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 19: R. Typke, P. Giannopoulos, R. C. Veltkamp, F. Wiering, and R. van Oostrum. Using transportation distances for measuring melodic similarity. In Proceedings of the International Conference on Music Information Retrieval (ISMIR), 2003.
• 20: Z. Yu and G. Herman. On the Earth Mover's Distance as a histogram similarity metric for image retrieval. In Proceedings of the IEEE International Conference on Multimedia and Expo (ICME), pages 686--689, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Multimedia databases

General Terms:
Algorithms, Performance

Keywords:
dimensionality reduction, earth mover's distance, filter distance, lower bound, multimedia databases