论文题目: 高维数据索引结构研究
论文类型: 博士论文
论文专业: 计算机应用技术
作者: 董道国
导师: 薛向阳
关键词: 信息检索,索引结构,相似查询,多媒体数据库
文献来源: 复旦大学
发表年度: 2005
论文摘要: 随着互联网和多媒体技术的迅速发展,人们可以访问到的多媒体数据急剧增长,如何实现多媒体数据对象的相似检索成为一个非常重要的研究课题。通常,人们利用特征提取算法从多媒体数据对象中提取出特征矢量,然后利用特征矢量之间距离表示多媒体对象之间相似度。相似性检索的实现就是通过计算查询矢量与数据库中矢量之间距离以找出满足条件的对象。当数据库中矢量很多时,简单的顺序扫描搜索将导致极大查询代价,无法满足用户需求。为了有效实现快速相似性检索,就必须借助于高效的高维数据索引结构。 在最近几十年中,人们提出了很多高维数据索引结构,其中大多是树形结构,如R-Tree、R~*-Tree等,这些索引结构在维数升高时性能会急剧下降,即所谓的“维数灾难”,为此,有人提出了通过近似压缩矢量来减少磁盘I/O代价的VA-File,但仍不能为高维数据的相似性检索提供良好的查询性能。针对高维数据索引结构的现状,我们在该领域进行了深入研究,取得了一定的成果。 首先,我们提出了四种新的索引结构:1) Angle-Tree:用高维空间中单位超球面上的超弧对空间进行划分,并借助于树形结构实现索引,可有效支持以矢量之间夹角余弦为相似度度量的查询方式;2) VAR-Tree:将VA-File与R-Tree有机结合起来,用R-Tree来管理和组织近似矢量数据,并借助R-Tree类相似查询算法实现基于VAR-Tree的查询;3) VA-Trie:利用Tile结构来索引VA-File中近似矢量,有效实现了高维数据的相似性检索;4) OVA-File:将VA-File中近似矢量插入到近似文件中合适位置,使得在高维空间中相邻数据尽量存放在近似文件的相近位置上,从而在查询过程中仅访问部分近似矢量,就可快速得到质量很高的相似查询结果。 其次,在高维数据索引结构研究基础上,本文分别给出了基于VA-File和OVA-File的、以高维矢量序列为查询对象的视频片断相似查询方法,以有效利用高维索引结构同时支持视频信息检索中的镜头检索和视频片断检索。 最后,结合一个实际的多媒体信息检索系统,进一步阐述高维索引结构在实际系统中的应用。我们利用OVA-File管理来自于海量视频数据的高维矢量,基于镜头和视频片断相似查询模型实现了视频数据的快速相似性检索。
论文目录:
摘要
ABSTRACT
第一章 简介
1.1 研究背景及意义
1.2 研究目标及主要贡献
1.3 论文结构及主要内容
第二章 高维数据索引结构综述
2.1 高维数据及索引结构的特点
2.2 高维数据查询方式
2.3 向量空间与度量空间索引结构及其异同点
2.4 向量空间高维索引结构
2.4.1 向量空间高维索引结构分类
2.4.2 几种代表性的向量空间高维数据索引结构
2.5 度量空间高维索引结构
2.5.1 度量空间高维索引结构分类
2.5.2 几种有代表性的度量空间索引结构
2.6 相似性检索
2.6.1 简介
2.6.2 相似性检索算法
2.6.3 近似k近邻查询
2.7 本章总结
第三章 高维数据索引结构研究
3.1 研究思路
3.2 ANGLE-TREE
3.2.1 简介
3.2.2 相似度度量方法与索引结构的关系
3.2.3 Angle-Tree的结构
3.2.4 插入算法
3.2.5 删除算法
3.2.6 范围查询
3.2.7 实验及分析
3.2.8 总结
3.3VAR-TREE
3.3.1 简介
3.3.2 VAR-Tree的原理
3.3.3 相似性查询
3.3.4 实验与分析
3.3.5 总结
3.4 VA-TRIE
3.4.1 简介
3.4.2 VA-Trie的原理
3.4.3 近似k近邻查询
3.4.4 实验与分析
3.4.5 总结
3.5 OVA-FILE
3.5.1 简介
3.5.2 OVA-File的原理
3.5.3 查询算法
3.5.4 N和M的选取原则
3.5.5 实验与分析
3.5.6 总结
3.6 本章总结
第四章 基于高维数据索引结构的视频片断检索方法研究
4.1 视频片断检索简介
4.1.1 视频信息检索
4.1.2 视频表示
4.1.3 视频片断相似度定义
4.1.4 视频片断的k近邻检索
4.2 相关工作
4.2.1 S~2-Tree的原理
4.2.2 基于S~2-Tree的视频片断检索
4.3 基于VA-FILE的视频片断检索方法
4.3.1 简介
4.3.2 相似度度量模型
4.3.3 基于近似矢量的相似度计算
4.3.4 基于VA-File的视频片断k近邻查询算法
4.3.5 实验与分析
4.3.6 总结
4.4 基于OVA-FILE的视频片断检索方法
4.4.1 简介
4.4.2 视频片断相似度度量
4.4.3 基于OVA-File的视频片断查询算法
4.4.4 实验与分析
4.4.5 总结
4.5 本章总结
第五章 高维数据索引结构应用
5.1 简介
5.1.1 视频信息检索
5.1.2 多媒体信息的描述—MPEG7
5.1.3 索引结构在视频信息系统中的应用
5.2 系统简介
5.2.1 应用背景
5.2.2 系统功能简介
5.3 系统框图
5.3.1 硬件设备图
5.3.2 体系结构图
5.4 主要功能模块
5.4.1 视频信息采集接收模块
5.4.2 视频信息过滤模块
5.4.3 存储与组织模块
5.4.4 视频内容处理模块
5.4.5 索引模块
5.4.6 浏览和检索模块
5.5 高维数据索引结构在系统中的应用
5.5.1 系统中的高维数据
5.5.2 查询方式与高维数据
5.5.3 高维索引结构的选择
5.5.4 实际应用中的OVA-File结构
5.5.5 OVA-File的构造原则
5.5.6 OVA-File的查询应用
5.5.7 镜头查询
5.5.8 视频片断查询
5.6 本章总结
第六章 总结与展望
引用文献
发表论文及专利申请
致谢
论文独创性声明
发布时间: 2005-09-19
参考文献
- [1].高维数据下的几类因果推断算法研究[D]. 麦桂珍.广东工业大学2018
- [2].基于特征选择的高维数据统计分析[D]. 苏锦霞.兰州大学2018
- [3].高维数据的若干分类问题及算法研究[D]. 吴庆耀.哈尔滨工业大学2013
- [4].人脸识别中高维数据特征分析[D]. 刘翠响.河北工业大学2008
- [5].面向大数据的高维数据挖掘技术研究[D]. 楼巍.上海大学2013
- [6].基于稀疏表示的高维数据无监督挖掘研究[D]. 冯小东.北京科技大学2015
- [7].高维数据的K-harmonic Means聚类方法及其应用研究[D]. 陈建娇.上海大学2012
- [8].基于图的高维数据聚类方法研究[D]. 杜宁.东北师范大学2017
- [9].高维数据降维可视化研究及其在生物医学中的应用[D]. 徐微微.武汉大学2016
- [10].高维数据交互特征选择和分类研究[D]. 李静.燕山大学2015
相关论文
- [1].大规模图像库的高维索引技术研究[D]. 梁俊杰.华中科技大学2007
- [2].高维数据挖掘中若干关键问题的研究[D]. 杨风召.复旦大学2003
- [3].面向大规模图像库的索引和检索机制研究[D]. 叶航军.清华大学2003
- [4].高维数据的特征选择及基于特征选择的集成学习研究[D]. 张丽新.清华大学2004
- [5].XML索引和过滤查询若干关键技术研究[D]. 雷向欣.复旦大学2005
- [6].高维数据的降维理论及应用[D]. 谭璐.国防科学技术大学2005
- [7].基于R-树的空间数据库查询技术研究[D]. 黄继先.中南大学2005
- [8].高维索引技术中向量近似方法研究[D]. 崔江涛.西安电子科技大学2005
- [9].支持最近邻查找的高维空间索引[D]. 张军旗.复旦大学2007
- [10].面向大规模图像库的层次化索引机制研究[D]. 贺玲.国防科学技术大学2006