A method to Improve metric index VP-tree for multimedia databases
A method to Improve metric index VP-tree for multimedia databases
复制标题
DOI：
10.1109/fcv.2011.5739700
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
M. Shishibori;S. Lee;K. Kita
中科院分区：
文献类型：
--
作者：
M. Shishibori;S. Lee;K. Kita
在多媒体数据库中，为了实现快速访问，需要采用多维数据空间的索引方法。然而，由于使用欧几里得距离作为距离度量是前提，因此该方法缺乏灵活性。另一方面，也有一些度量索引方法只需要满足距离公理。由于度量索引方法也可以应用于除了欧几里得距离之外的距离度量，因此这些方法具有高灵活性。本文对度量索引方法之一的VP-树进行了改进。VP-tree在搜索时从路由节点开始跟踪适合搜索范围的节点。计算查询与从叶节点链接的所有最终到达的对象之间的距离，并调查每个对象是否包含在搜索范围内。然而，如果叶节点中的距离计算的数量增加，则搜索速度将变慢。因此，我们关注的候选人选择方法使用三角不等式在一个叶子节点。作为改进的方法，我们提出了一种使用最近邻对象点作为三角不等式的基准点的方法。通过这些改进的方法，可以使搜索范围更小，并减少距离计算的次数。从使用10，000个图像数据的评估实验中发现，我们提出的方法可以减少传统方法的搜索时间的5%-12%。
On multimedia databases, in order to realize the fast access method, indexing methods for the multi-dimension data space are used. However, since it is a premise to use the Euclid distance as the distance measure, this method lacks in flexibility. On the other hand, there are metric indexing methods which require only to satisfy distance axiom. Since metric indexing methods can also apply for distance measures other than the Euclid distance, these methods have high flexibility. This paper proposes an improved method of VP-tree which is one of the metric indexing methods. VP-tree follows the node which suits the search range from a route node at searching. And distances between a query and all objects linked from the leaf node which finally arrived are computed, and it investigates whether each object is contained in the search range. However, search speed will become slow if the number of distance calculations in a leaf node increases. Therefore, we paid attention to the candidates selection method using the triangular inequality in a leaf node. As the improved methods, we propose a method to use the nearest neighbor object point for the query as the datum point of the triangular inequality. It becomes possible to make the search range smaller and to cut down the number of times of distance calculation by these improved methods. From evaluation experiments using 10,000 image data, it was found that our proposed method could cut 5%∼12% of search time of the traditional method.