On Efficient Query Processing with the Earth Mover's Distance

The Earth Mover's Distance which is proposed in computer vision as a distance-based similarity model has been widely used and investigated in various domains for similarity search.  Although there exists the opportunity to apply this well-known similarity model reflecting the human perceptual similarity both on feature histograms and signatures as feature representation techniques, efficiency improvement approaches towards the Earth Mover's Distance were often investigated on feature histograms. Thus, it can be brought into question how k-nearest-neighbor queries can be processed efficiently by using this distance-based similarity model in a database of feature signatures, such as in a multimedia database. In this paper, the work in progress is presented regarding the new lower bound Independent Minimization for Signatures (IM-Sig) to the Earth Mover's Distance on feature signatures as an efficient filter approximation approach. Furthermore, the problems and challenging issues regarding efficient query processing on feature signatures are presented. The ongoing experimental evaluation on real data points out the high efficiency of the proposed lower bound, contributing to a promising start in the research field of efficient query processing with the Earth Mover's Distance. 

Authors: Uysal M., Beecks C., Seidl T.
Published in: Proc. of the 7th Workshop for Ph.D. Students (PIKM) at 23rd International Conference on Information and Knowledge Management (CIKM 2014), Shanghai, China.
Language: EN
Year: 2014
Pages: 25-32
ISBN: 978-1-4503-1481-7
Conference: PIKM
DOI:10.1145/2663714.2668047
Url:PIKM 2014
Type: Conference papers (peer reviewed)
Research topic: