基于图的大规模特征库高维索引技术研究

摘要

高维索引是基于内容的多媒体检索及地理、生物数据库等需要运用到高维数据库的系统中一个至关重要的部分，其性能直接影响整个查询系统的查询速度和准确率，但高维情况下的“维度灾难”问题始终困扰着高维特征向量查询的性能提升，使得高维索引常常成为相关系统的性能瓶颈之一。自上世纪六七十年代起，研究人员提出了许多种类的高维索引解决方案，但迄今仍然没有出现一种各方面性能都能令人满意的索引技术，使得当前高维索引技术的发展仍然纷乱而迫切。
　　 本文参考目前热门的图上的随机游走算法，设计了一种融入了图上游走思想的新型高维索引技术，称为逼近索引，并给出了相应的逼近游走相似性查询算法。同时，通过分析逼近游走算法和一般高维索引算法的优缺点，本文进一步提出了一套基于逼近游走的分层组合索引思想，并按照此思想给出了一种新的相似逼近索引算法。具体而言，本文的详细工作包括:
　　 第一，本文分析总结了向量空间和度量空间中的各种常见索引结构的基本思想和优缺点，阐述了高维索引算法的发展趋势。然后融合向量空间和度量空间索引特点，设计了一种不与特征向量维度直接相关，能有效减少高维向量查询中对特征向量库访问比例的逼近索引及相关相似性查询算法。该索引将高维特征向量库表示成图的形式，引入逼近游走来进行近似近邻查询和范围查询。
　　 第二，本文进一步分析了目前逼近索引算法的优点和不足之处，联合多种现有的高维索引和逼近索引，提出了一种基于逼近索引的多层组合索引算法的思路。其中，完整地给出了近似逼近索引的生成维护及查询算法，并对该索引的综合性能进行了详细的评测。此外，对于超高维数据，本文提出了包含向量降维和一维转换算法的组合索引设想。
　　 第三，在向量降维部分，本文引入了近年来热门的压缩感知理论，设计了一种利用压缩采样的思想进行高维向量降维的线性降维算法。该算法具有需要信息少，计算时间和空间复杂度低以及能处理特别高维度向量的特点。
　　 实验数据表明，本文算法适合应用于大型特征库的相似性查询，具有访问特征库中记录条数少，查询准确性高的特点，综合性能要优于近期提出的多个索引算法，对高维索引技术的发展具有很好的参考价值。

目录

声明

摘要

表格

插图

第1章 绪论

1．1 研究背景

1．2 国内外研究现状

1．3 论文研究思路

1．4 论文组织架构

第2章 相关技术

2．1 高维向量近似性查询概述

2．2 树型结构索引算法

2．2．1 向量空间树型索引

2．2．2 度量空间树型索引

2．2．3 混合空间树型索引

2．2．4 树型结构与一维转换的组合索引

2．3 非树型索引算法

2．3．1 空间填充曲线

2．3．2 量化近似索引

2．3．3 基于Hash的索引算法

2．4 其它高维索引算法

第3章 逼近索引算法

3．1 逼近索引算法概述

3．1．1 逼近索引基本思想与查询流程

3．1．2 特征库的图表示

3．2 逼近游走算法

3．2．1 逼近游走相似性查询算法

3．2．2 算法的启动终止与参数浅析

3．3 逼近索引的维护

第4章 基于逼近索引的分层组合索引

4．1 分层组合索引概述

4．2 近似逼近索引

4．3 降维组合索引与压缩感知降维

4．4 其它分层组合索引算法

第5章 实验与评测分析

5．1 实验环境与数据参数

5．2 逼近索引性能评测

5．2．1 范围查询实验

5．2．2 KNN查询实验

5．3 近似逼近索引性能评测

5．3．1 范围查询实验

5．3．2 KNN查询实验

5．4 性能对比与总结

第6章 总结与展望

6．1 研究总结

6．2 下一步工作展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果