多媒体海量处理中的多维索引方法与应用

需积分: 10 144 浏览量更新于2024-08-07 收藏 437KB PDF 举报

本文主要探讨了多维索引方法在多媒体信息海量处理中的关键作用，特别是在大规模多媒体应用中的效率和性能优化。作者Norio Katayama和Shin-ichi Satoh来自日本国家科学信息系统中心的科研团队，他们的研究着重于两种多维索引策略：索引构建方法和基于集合的最近邻搜索。索引构建方法部分，论文提出了一种创新的球体/矩形树的静态构造技术。这种树状数据结构在处理静止图像的相似性检索时表现出高效性，通过将图片特征进行空间划分，能够快速定位与查询图像相近的样本，显著降低了搜索成本。这种方法在处理大量图像数据时具有良好的扩展性，有助于提升系统的响应速度和资源利用率。另一方面，基于集合的最近邻搜索方法被用于处理特征向量集合的匹配问题。这种方法强调的是整体的相似度匹配，而非单一特征的精确匹配，适用于人脸识别等场景中的序列匹配任务。通过这种方法，可以有效地处理包含多个特征维度的复杂查询，提高了人脸识别算法的准确性和鲁棒性。评估部分，作者通过实际应用到人脸序列匹配中，验证了这两种多维索引方法的有效性和实用性。实验结果显示，这些方法不仅在处理效率上有所提升，还展现了良好的可扩展性，对于大规模多媒体信息处理有着明显的优势。此外，文章还提到了关键词“多维索引结构”、“最近邻搜索”、“相似图像检索”和“图像序列匹配”，这些都是理解论文核心内容的关键术语。这篇学术论文对多媒体信息处理中的多维索引技术进行了深入研究和实践，对于多媒体数据库系统设计者和研究人员来说，提供了重要的理论支持和技术参考，有助于推动大规模多媒体应用的高效处理和检索技术的发展。

the R-tree divides the search space by minimum bounding

rectangles with allowance of the overlap between them.

Among these structures, the R-tree is the most efficient for

dynamic updates. With allowing overlap between minimum

bounding rectangles, the R-tree is kept balanced even after

dynamic updates. Therefore, the R-tree is regarded as one

of the most suitable index structures for the online database

applications.

The method of the region split has great influence on

the performance of index structures. Both the SS-tree and

the SR-tree are derived from the R-tree, and thus their

structure is similar to the R-tree. However, the SS-tree and

the SR-tree have better performance than the R-tree with

respect to the nearest-neighbor search. This performance

improvement comes from the modification of the region

split. The tree construction algorithm is common to the

SS-tree and the SR-tree. It is originally designed for the

SS-tree; the SR-tree borrows it from the SS-tree. This

algorithm splits regions based on the variance of coordi-

nates. According to the performance evaluation, it is shown

that this algorithm generates regions with shorter diameters

than does the algorithm of the R

-tree [1, 2].

While the region shape of the SS-tree is a bounding

sphere, that of the SR-tree is the intersection of a bounding

sphere and a bounding rectangle (Fig. 2). The SR-tree

employs bounding rectangles in addition to bounding

spheres because this enables regions to be smaller. Bound-

ing rectangles and bounding spheres are complementary to

each other in high-dimensional space. Bounding rectangles

reduce the volume of regions while bounding spheres re-

duce the diameter of regions. When employing both, the

SR-tree outperforms the SS-tree. Therefore, this paper em-

ploys the SR-tree for a multidimensional indexing method.

2.3. Nearest-neighbor search algorithms for

multidimensional index structures

The nearest-neighbor search finds such a point that is

closest to a given query point. This search is widely used in

multimedia applications, such as the similarity retrieval of

images based on feature vectors. Two types of search algo-

rithms have been proposed for multidimensional index

structures: the depth-first algorithm [7] and the breadth-first

algorithm [8]. The fundamental flow is common to both

algorithms. The search starts from the root node and visits

regions in ascending order of the distance from the query

point. On visiting each region, the candidate of the nearest

neighbor is determined by choosing the nearest point en-

countered so far. The search continues as long as there

remains such a region that is not visited so far and that is

closer than the candidate. The search terminates when no

region remains to be visited. The final candidate is the

answer of the query.

Both algorithms require a priority queue to keep the

nodes of the tree structure in ascending order of the distance

from the query point. On visiting a node, the children of the

node are pushed into the priority queue and then the first

node in the queue is chosen to be visited next. The differ-

ence between the depth-first and the breadth-first algorithm

resides in the method of maintaining the priority queue and

consequently makes a difference in the order of tree tra-

versal: one is depth-first and the other is breadth-first.

The depth-first algorithm allocates a priority queue

at each internal node and visits its child nodes recursively

in ascending order of the distance from the query point, that

is, a priority queue is allocated independently at each inter-

nal node and nodes are visited recursively along tree

branches. In this case, the second child node of an internal

node is visited only after the first node and its descendants

have been visited. Therefore, the tree is traversed in depth-

first fashion. On the other hand, the breadth-first algorithm

uses only one priority queue for the entire tree. On visiting

a node, its children are pushed into the single priority queue.

In this case, the search is not recursive. The closest node

among all of the nodes encountered so far is chosen for the

next visit.

Each of these algorithms has pros and cons. Neither

of them is completely superior to the other. With respect to

the number of nodes to be visited, the breadth-first algo-

rithm is proven to be optimal [9], that is, it visits the

minimum number of nodes. However, the priority queue

used by the breadth-first algorithm is more likely to be

longer than the one used by the depth-first algorithm. Since

the depth-first algorithm allocates the priority queue for

each visited internal node, the length of the priority queue

is never longer than the number of children of an internal

node. On the other hand, the priority queue used by the

breadth-first algorithm can be longer than the number of

children in an internal node; in the worst case, it is possible

that every node of the tree is pushed into the priority queue.

A longer priority queue might require more computational

cost. Therefore, with respect to the computational cost of

the priority queue, the depth-first algorithm is more advan-

Fig. 2. Structure of the SR-tree.

剩余10页未读，继续阅读

weixin_38746818

粉丝: 7
资源: 910

多媒体海量处理中的多维索引方法与应用

一种多维向量并行查询算法

大规模多媒体信息处理中的多维索引方法应用

多媒体信息处理中的多维索引技术应用探讨

空间数据库索引技术：提升海量空间数据处理效率

空间数据库索引技术在商用数据库中的应用

时空数据索引技术：3DR树在空间数据库中的应用

空间数据库索引技术：理论与应用

空间数据库索引技术详解：２１类定义与S3C44B0+JLink+Keil在SDRAM调试应用

网格文件：S3C44B0+JLink+Keil在SDRAM中调试空间数据库索引技术

空间数据库与索引技术：S3C44B0+jLink+Keil在SDRAM调试

最新资源