基于增长网络的索引结构优化与更新维护算法

摘要

随着互联网和数字多媒体技术的高速发展，社交平台和即时通信软件的迅速普及，图片、视频等多媒体数据出现爆炸式增长，这些数据普遍具有高维度和海量的特点。目前，云计算或大数据研究领域对这些数据处理技术的研究也正如火如荼地进行。研究如何管理这种海量高维数据库，并能同时在数据库中快速地查询到所需数据十分重要。对数据建立索引结构，然后在这些高维索引中研究有效的查询技术是其中一种解决方案。传统的索引方案在面临高维且海量数据时都会表现出一系列问题:树形结构索引有“维度灾难”问题;降维类索引会出现信息丢失;哈希类索引设计出优秀的哈希函数比较困难。基于小世界网络的高维索引技术是针对这些问题的一个有效解决方案，能够应用于高维海量数据检索，具有广阔的研究和发展前景。本文将增长网络模型应用于高维索引技术的研究与优化中，主要研究内容分为两部分:
　　(1)基于增长网络的索引结构及生成算法优化。在深入研究小世界基本理论及增长网络模型、传统高维索引技术以及原有基于小世界网络的索引技术的基础上，提出基于增长网络模型的索引结构模型，同时理论分析该索引结构的基本特征参数，证明该索引模型具有小世界特性;其次，基于增长网络模型提出新的索引生成算法，该算法具有更低的时间复杂度，并且实现更简单。通过实验验证该索引结构模型及相应索引生成算法不仅高效，还具有与原有索引模型相似的查询性能。
　　(2)基于增长网络的高维索引更新维护研究。在研究原有基于小世界网络的索引技术更新维护算法和其他高维索引技术的更新维护算法的基础上，本文借鉴增长网络模型，提出高效的插入和删除节点后索引的更新和维护算法。本文算法包括插入或删除一个或多个节点后，索引的更新操作，并确保插入或删除节点后索引可以继续维持小世界特性及算法的收敛性。
　　实验结果表明，本文提出的基于增长网络的高维索引技术相较于原有基于小世界模型的索引技术具有更好的索引生成性能，同时提出的更新维护算法确保了该索引技术是动态的。

目录

声明

摘要

表格

插图

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 传统高维索引技术研究现状

1．2．2 小世界网络模型及应用现状

1．3 论文研究思路

1．4 论文组织架构

第2章 相关技术

2．1 传统高维索引技术

2．1．1 “维度灾难”及其起源

2．1．2 树形结构索引算法

2．1．3 非树形结构索引算法

2．2 小世界理论及相关研究

2．2．1 小世界理论及发展

2．2．2 小世界网络模型及应用

2．3 基于小世界模型的高维索引方案

2．3．1 逐跳逼近索引结构及其模型

2．3．2 基于逐跳逼近索引的查询算法

2．4 本章小结

第3章 基于增长网络的索引结构研究

3．1 基于增长网络的高维索引概述

3．2 索引模型及理论基础

3．2．1 索引模型

3．2．2 索引模型理论分析

3．3 索引生成算法形式化描述

3．4 实验结果及分析

3．4．1 实验设计

3．4．2 实验环境及数据来源

3．4．3 实验内容及结果分析

3．5 本章小结

第4章 更新维护算法研究

4．1 添加数据时索引的更新算法

4．1．1 增加单个元素时索引的更新算法

4．1．2 增加多个元素时索引的更新算法

4．2 删除数据时索引的更新算法

4．3 实验结果与分析

4．3．1 实验设计

4．3．2 实验环境及数据来源

4．3．3 实验内容与结果分析

4．4 本章小结

第5章 总结与展望

5．1 总结

5．2 展望

参考文献

致谢

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

攻读硕士学位期间参与的科研课题