一种基于R-Tree的改进多维索引
摘要：为了适应空间多维索引技术在视频数据库中的应用
关键词：R-Tree 视频数据库 多维索引 数据空间分割
1 引言
信息的膨胀导致了现代多媒体数据库检索需要面对的问题越来越多。在构建索引方面，最主要面临的则是如何构造高效的索引算法来支持多媒体数据库系统，特别是如何有效的利用算法来实现加速检索。概括地说多媒体数据库索引结构要做到：支持高维数据空间；有效分割数据空间，来适应索引的组织；高效的实现多种查询方式系统中的统一。新近提出的索引结构很多都是单纯为了加速某种查询方式或提高某个方面的性能的，却常常忽略了其他方面的效果，很可能造成更多不必要的性能消耗。
现在已经有很多学者提出了他们对多媒体数据库，特别是视频数据库的空间模型，在空间索引结构方面，已经有了大量的成果。比如，R-Tree[1]、kd-Tree[]、网格文件[]、以及基于这些结构之上扩展而来的结构体[ ]等等。
由于索引结构如grid file(网格文件)、线性四分树对高维数据的扩展上性能不佳，因而动态可扩展的索引结构R-Tree[]、R*-Tree[]得到了普遍的应用。
本文集中研究基于向量空间模型的相似性检索的动态索引结构。在向量空间中对对象采用固定维数的向量表示，然后基于此研究其索引结构。
本文第2节提出数据模型与定义，第3、4节提出改进算法与测试实验，第5节实验结果分析，最后给出结论。
2、数据库模型与基本定义
2、1模型假设定义
特征提取算法提取出的各种特征矢量记为 ；系统反馈得到不同的特征对应的权重记为 ；图像联合特征 ；图像模型 ；
则A、B图像的相似度 可用特征在欧氏空间的距离 ，来描述。 为权重因子。特征距离 越小，相似度 越大。
通过图像联合特征和相似度的定义，充分利用图像内容信息，这就使对图像内容的检索转化为寻找与待检索图像联合特征相似度最大的联合特征，即为求联合特征的最小欧氏距离的问题。
2、2基于特征的分类模型
如图2-1所示，第一层次属于全局或者说基于基本语义的分类，这一分类由手工或各类已有的分类器或者聚类算法来进行。本文研究时笼统的分为视频、音频、文本等；第二层次的分类，可以使用多种索引方式，如领域分类，特征分类或注释分类。分类方式同样采用手工或分类器的方式；第三层次的终端则涉及到了具体的视频流，对视频流进行镜头分割、特征提取，最终处理的将是每一帧的特征图片集。最后基于颜色直方图信息利用本文研究的索引结构来进行索引组织。
2、3基于PCA的图像特征信息表示
本文着重讨论的高维索引结构的对多媒体数据库的适应，因而直接采用颜色特征作为研究对象。
对于给定的图像/视频帧I , 获取其相应的色度图像I′。设向量x 表示I′经过离散付氏变换(DFT)后得到的幅值向量,x是将傅立叶频谱(幅值谱) 矩阵的元素按行列顺序排列成一个向量而形成的. 这样, 我们就得到了图像的一个高维颜色特征x。在图像检索应用中, 一般不直接使用高维特征向量, 而是要先对其进行降维处理, 然后使用降维后的低维特征进行图像检索[12, 13]. 下面我们将应用主分量分析方法(PCA) 或K-L 变换对高维特征向量x 进行降维, 将x中包含的信息压缩到其中的少数维之中, 并将其作为图像的颜色表示用于图像检索中。
本文中的数据图像表示就是使用的[]中所述的PCA，K-L变换的方式。采用这种方式，对图像集中的每个图像, 采用离线方式进行K-L 变换, 并将得到的图像特征向量存入数据库中。在实际的图像检索系统中, 一般只选取前k个K-L 变换系数(k < q（q代表PCA训练的图像数）) 用于图像检索, k 的选取是根据系统所允许的均方误差而确定的.
应当指出, K-L 变换可以在数据库的一个具有统计意义的子集上采取脱机方式进行计算. 另一方面, 只要数据库的规模足够大, 当新的图像加入数据库后, 也不需要重新计算K-L 变换.
3、R-Tree数据空间分割算法改进
3、1 R-Tree算法的基本改进
如图2-1，模型采用多层次结构。使用层次索引就相应减小索引文件的大小；对于不同层次，可选用的索引结构也可不同，增加了索引体系的灵活性。当然，这种模式的选用，带来另一个问题，即层次结构中数据分类的实现。
采用了层次结构，数据的分类就显得很重要。数据分类后，要进行的便是数据空间分割。进行MBR的数据空间分割的目的就在于提高R-Tree在区域查询和k-NN（最近邻）查询上的效率不足。通过改进的数据空间分割方法可以达到简化k-NN查询与区域查询的目的，主要的改进是通过两层MBR结构设计使得查询时的数据及缩小的速度加快。具体的空间分割算法见[3、2数据空间分割算法]
3、2 数据空间分割算法
具体设计如下：
代表FirstBR即第一层次的数据块
代表SecondBR即最小层次的数据点集
代表整个数据集所产生的最小全覆盖矩形
图3-1 数据分布在空间分割的示意图
对分类数据集DataSet，采用偏移最优矩形算法进行数据空间第一层划分，得到一系列的FirstBRs（第一层划分所得的矩形）。
然后，在FirstBRs中，采用k-偏移最优矩形算法进行二次划分，得到FirstBRs中的一系列SecondBRs（第二层划分所得的矩形）其中各包含k个数据点（存在一个矩形可能少于k个）。
1、对于区域查询，只要比较数个FirstBRs的中心点与查询条件的相似度，选取适合的FirstBRs再进行细化比较，而无需对全部数据集进行查询。查询的数据集由全体数据集减少为邻近的几个数据集。
2、对于k-NN查询：先进行FirstBRs的比较，得到适合的FirstBRs的位置，然后只要在这个FirstBRs中在进行SecondBRs的中心点与查询条件的相似度比较，最后确定几个SecondBRs，利用基本比较操作查找出k个结果数据点。同样这也在查询数据量上得到了简化。
〖偏移最优矩形算法〗
前提： n个数据点，分布在R维空间中，各个数据点的表示如
算法功能： 对n个数据点进行区域划分，获得多个FirstBRs（矩形），保证矩形整体数据覆盖率最小。区域矩形的域值为 （即区域矩形中心到矩形边界的半径为 ）。
算法步骤：
1、在n个点中，取一点A ，则立即构成区域矩形 ，即
` ；
2、判定是否有一个数据点B （或多个）在 中，判定方法：
对于 ，如果 ，那么B点在 中。
如果不满足条件继续2查找。若最终没有一个数据点满足要求，那么对该点进行预留操作（所谓预留，就是将该点信息保存到一个临时的列表TempList中），然后跳到1操作，重新选点；若找到一个B数据点，则继续；
3、对于2中找到的B数据点，A、B两点构成一个矩形区域 ，移动 的中心至 中心，则 （平移）；
4、循环操作23，直到没有数据点可以插入 ；重新取点 进行1~4的操作；
5、最终，无数据点在上述过程结束后遗留，那么算法结束。
如果TempList存在未划分的数据点，则查找与该数据点距离最近的数据点C构成区域 （i代表可能存在的这样的区域的个数）。
至此，算法结束，数据集得到了有效空间划分，结果为一系列的FirstBRs。
〖k-偏移最优矩形算法〗实际上这个算法是偏移最优矩形算法的派生，简单的改变在于限定划分所得区域中数据点个数为k。其余算法同于偏移最优矩形算法。
不可否认的，这种分裂方法，对于数据常更新的数据集，存在性能不佳的缺陷，但考虑到对应的多媒体数据库中的数据本身的更新基本没有。因为对于多媒体数据，特别是视频数据其内容是不能有随意添加或删除形式的更新，有的只是视频数据整个的更新变化，同时本文考虑的不是独立视频数据间的索引，考虑的是每个视频数据内部镜头分割后的索引。所以，这种分裂算法的使用，适合应用本文研究的索引。
4、改进算法的实现及实验分析
为了适合上述的数据分割算法的改进，将R-Tree的数据结构进行一定的改进。
4、1改进的R-Trees结构图示
改进的R-Tree结构可以用如下图简明表示：
图4-1 改进R-Tree的结构简明示意图
4、2改进算法验证实验设计
采用的数据源是经过处理的实际图片数据。
特征向量表示，采用颜色直方图特征在进行了PCA变换后图像表示作为特征向量，其表示为：每个r维数据点
；其中 代表第i维上的颜色直方图的数值。
假设查询图像间的相似度的度量式： ；
验证实验设计
1、改进方案正确性实验
对于数组数据集，利用R-Tree与改进后算法分别进行构建索引和相似查询。比较两者的结果数据集以及两者的耗时。
2、改进方案的性能测试
对于同一图片集，采用不同的数据提取方法提取几组维数不同的数据集。用R-Tree与改进后算法分别进行构建索引和相似查询。比较两者的结果与耗时。
本次实验使用的数据集为人工设计，其中数据点分布大致如下图：
代表整个数据集所产生的最小全覆盖矩形
代表FirstBR即第一层次的数据块
代表SecondBR即最小层次的数据点集
代表
图4-2 人工数据示意图
〈说明：左图是平均分布的数据点的图例，右图是不均匀分布数据点的图例〉
4、3实验结果分析
反馈相似节点数量
实验结果图示：
数据集大小
数据集大小
随机查询节点数
随机数据集 图4-3-1 随机数据集 图4-3-2
实验1 采用随机分布数据，数据个数为50、100、200、500、1000，数据空间维数20以内（本次实验选取为20）。如图4-3-1给出的是查询执行的阈值（相似度）在0.75的条件下的结果（每个实验5次，取平均结果），图4-3-2给出的是查询执行后反馈的相似节点数的结果（同样每个实验5次，取平均值）。
改进的R-Tree算法的查询节点数明显少于原始的R-Tree而且随着数据量的增大这种表现越发明显（图4-3-1），而两者反馈的相似节点集则相对差不多（图4-3-2）；改进的R-Tree算法在查询方面较原始R-Tree要好，尤其当对应数据量庞大的时候。
实验选择计算访问节点数代替计时的方案。由于改进的R-Tree的算法在使用的比较数据对象相似性的公式与R-Tree相同，即单位耗时t相同，而R-Tree查询访问点数与改进的算法查询访问点数存在关系 ，所以，明显的有
这一点就证明了我们采用这个方案的可行性和正确性。
总之，从上述两图，在对同一数据使用R-Tree和改进后R-Tree两种方法查询时，后者的平均访问数据数基本的低于前者，这就从另一个侧面反映了后者在CPU时间上的低消耗。
从这一点上，说明改进的算法有效的达到了查询提速的功能。
均匀分布数据集 图4-3-3 非均匀分布数据集 图4-3-4
实验2 判定数据分割的有效性实验，采用不同数据分布模式的数据集，进行建树时耗和树结构大小的判定。图4-3-3均匀数据分布条件下节点产生数量统计图；图4-3-4非均匀数据分布条件下节点产生数量统计图。
特殊数据集模式 即稀疏模式
如图4-3-3与图4-3-4给出的右图，数据节点构成线性表示图，可以看出随着数据数的增加，节点数增加的幅度很大，这便反映出了R-Tree在索引构建上的一个缺点，索引文件增大很快，对数据库存储的压力会越来越大。在内存使用方面，对检索的加速功能产生一定的影响。
对于均匀分布的数据，依据数据对象个数变化进行实验，结果如图4-3-3所示，R-Tree算法产生索引的结点数增大趋势较改进后的算法明显的多。
图4-4
对于非均匀分布的数据，采用的是一种极端分布数据及数据分布存在区域性很强，如下图4-4，从这一点出发，对于改进算法，该组数据所产生的主节点数则必然由于两层矩形区域（FirstBR和SecondBR）的采用而减少，在数据量越大的情况下，将表现得越加明显。容易知道，当次层树的大小与CPU每次运行查询操作所调用页面大小像同时，改进的算法的时耗将达到最优（当然此处考虑的是理想状态不考虑I/O是页面的大小与时耗对本结构运行带来的影响，仅当页面大小=次层树的数据大小）。同样，从图4-3-4的两图中我们得到了与图4-3-3中一样的结果。
采用改进后R-Tree算法，随着数据对象的增加，其产生索引的结点数增大趋势不再如R-Tree算法所反应的那么明显，图4-3-3右图与图4-3-4右图，比较图中的两条曲线，改进算法产生的曲线较为平坦，变化缓和。这说明了R-Tree在改进后所得到的算法在减小索引文件的大小的工作上达到了预期的效果。
********
实验数据
匹配结果
新闻频段视频
足球频段视频
电影片段视频
表4-1
实验3 判定索引使用针对性实验，采用不同实验数据的数据集，进行建树时耗和树结构大小的判定。
*********
****** 对背景变化不是很大的视频段 其索引查询功能的效果较优！
分析总结：
通过以上的实验数据分析，改进的R-Tree算法在总体上性能较经典的R-Tree算法有了很好的改进。特别是对多媒体流式数据的支持上，采用层次索引，通过优化组合增加了索引结构的适应性与可选择性。在数据处理方式上的改进提高了算法在检索提速方面的作用，同时避免了索引文件的过分庞大，较好的避免了内存调用索引是可能出现的重复页面转换时间的消耗。
6、结束语
本文结合高维向量空间索引相关知识，对经典的多维空间索引（重点是R-Tree）算法进行了一定的研究。对现有多种流行索引结构模型的基本思想进行了扩充，提出了一个具有较高适应度的多媒体数据库索引模型，并基于此利用数据降维、数据集层次结构、数据的初始化等方面的算法与设计的改进，以弥补经典算法的缺陷，并达到了预期的实验效果。
本文仅就R-Tree中数据空间分割方法进行了分析改进，下一步研究将要面对的就是，构建索引的时间的减少，更好的支持多媒体数据存储查询的性能，更好的对k-NN相似查询的支持，优化数据分类器的设计实现（根据语义），相应存储结构的设计。
