Efficient Filter Approximation Using the Earth Mover's Distance in Very Large Multimedia Databases with Feature Signatures

The Earth Mover's Distance, proposed in computer vision as a distance-based similarity model reflecting the human perceptual similarity, has been widely utilized in numerous domains for similarity search applicable on both feature histograms and signatures. While efficiency improvement methods towards the Earth Mover's Distance were frequently investigated on feature histograms, not much work is known to study this similarity model on feature signatures denoting  object-specific feature representations. Given a very large multimedia database of features signatures, how can k-nearest-neighbor queries be processed efficiently by using the Earth Mover's Distance? In this paper, we propose an efficient filter approximation technique to lower bound the Earth Mover's Distance on feature signatures by restricting the number of earth flows locally. Extensive experiments on real world data indicate the high efficiency of the proposal, attaining order-of-magnitude query processing time cost reduction for high dimensional feature signatures.

Authors: Uysal M., Beecks C., Schmücking J., Seidl T.
Published in: Proc. ACM 23rd International Conference on Information and Knowledge Management (CIKM 2014), Shanghai, China.
Publisher: ACM
Language: EN
Year: 2014

(full paper acceptance rate 20.3% in database track, and 20.9% for the whole conference)

Pages: 979-988
ISBN: 978-1-4503-2598-1
Conference: CIKM
Url:CIKM 2014
Type: Conference papers (peer reviewed)
Research topic: