AMethod for similarity based retrieval for a large multimedia database

提出了一种基于Jaccard系数的快速相似度计算算法和数据结构，用于图像的合成检索。相似性度量图像的区域与另一图像的区域之间的重叠程度。快速计算相似度的关键思想是使用图像的游程描述来计算图像的区域与另一图像的区域之间的重叠像素的数量。我们提出了一个算法和数据结构，并在30,000幅图像上进行实验，以评估我们的算法的性能。实验表明，该算法是5.49（2.36）倍的速度比一个天真的算法的平均（最坏的）。最后，我们从理论上给出了相当好的估计的运行次数，计算时间和运行长度文件的大小。

We propose an algorithm and data structure for fast computation of similarity based on Jaccard coefficient to retrieve images by composition. The similarity measures the degree of overlap between the regions of an image and those of another image. The key idea for fast computation of the similarity is to use the runlength description of an image for computing the number of overlapped pixels between the regions of an image and those of another image. We present an algorithm and data structure, and experiment on 30,000 images to evaluate the performance of our algorithm. Experiments show that the proposed algorithm is 5.49 (2.36) times faster than a naive algorithm on the average (the worst). Finally, we theoretically give fairly good estimations of the number of runs, computation time and the size of a runlength file.