Efficient Filter Approximation Using the Earth Mover's Distance in Very Large Multimedia Databases with Feature Signatures
Efficient Filter Approximation Using the Earth Mover's Distance in Very Large Multimedia Databases with Feature Signatures
复制标题
DOI：
10.1145/2661829.2661877
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
M. S. Uysal;C. Beecks;Jochen Schmücking;T. Seidl
中科院分区：
文献类型：
--
作者：
M. S. Uysal;C. Beecks;Jochen Schmücking;T. Seidl
在计算机视觉中提出的地球移动器的距离作为反映人类感知相似性的基于距离的相似性模型，已被广泛用于许多领域，用于特征直方图和签名的相似性搜索。虽然对地球移动器的距离的效率提高方法经常调查的功能直方图，没有太多的工作是已知的，研究这种相似性模型的特征签名表示对象特定的功能表示。给定一个非常大的多媒体特征签名数据库，如何使用地球移动器的距离有效地处理k-最近邻查询？在本文中，我们提出了一个有效的过滤器近似技术，通过限制本地地球流量的数量来降低地球移动器的距离特征签名。在真实的世界数据上的实验表明，该方法具有较高的效率，对于高维特征签名，查询处理时间开销降低了一个数量级。
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.