基于导向性分散伸展图的高效近似最近邻搜索

发布时间：2022-11-05 10:13

　　近似最近邻搜索问题是数据库、数据挖掘、人工智能等领域中的一个基本问题。一个具有实际应用价值的近似最近邻搜索算法必须同时具有极高的搜索速度以及合理的内存用量。相比于传统的基于树结构、基于哈希和基于量化的搜索算法,基于图索引的近似最近邻搜索算法因其搜索高且速度快的特点,吸引了来自学术界和工业界的大量关注。虽然许多早期的基于图结构的近似最近邻搜索算法算法在理论上具有十分低的搜索时间复杂度,但这些图结构索引的索引构建算法往往具有极高的时间复杂度,从而使其在目前的大数据时代场景中无法有效应用。因此近年来学界提出了诸多新的图结构索引,以期能够降低索引构建的时间复杂度。虽然这些方法取得了许多革命性的进步,但其仍旧不够高效从而限制了其在更大规模数据集上的应用。本文结合近年来的最新研究成果,对图结构索引进行了更深入的探究,以希望能够更有效地解决上述困难。具体来讲,本文从以下四个方面出发对用于近似最近邻搜索的图结构进行了探究:（1）保证图的连通性;（2）降低图中节点的平均出度已获得更快的遍历速度;（3）降低查询在图上的搜索路径长度;（4）减小基于图结构的索引的大小。基于以上四点,本文在理论上提出了一种全新... 

【文章页数】：71 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景
    1.2 研究现状
    1.3 本文研究内容与贡献
    1.4 本文章节安排
第2章 相关工作概述
    2.1 问题定义
    2.2 研究前提
    2.3 基于非图结构的近似最近邻搜索算法
        2.3.1 基于树结构的算法
        2.3.2 基于哈希的算法
        2.3.3 基于空间量化的算法
        2.3.4 总结与讨论
    2.4 基于图结构的近似最近邻搜索算法
        2.4.1 德劳内图
        2.4.2 相对近邻图RNG
        2.4.3 可通航小世界网络NSWN
        2.4.4 随机化近邻图RANG
        2.4.5 单调搜索网络MSNET
    2.5 本章小结
第3章 MRNG算法介绍与分析
    3.1 引言
    3.2 单调路径与单调搜索网络MSNET
    3.3 单调相对近邻图MRNG
    3.4 MRNG的构建算法
    3.5 本章小结
第4章 NSG算法介绍与分析
    4.1 设计思想与构建算法
        4.1.1 设计思想
        4.1.2 算法实现
    4.2 时间复杂度分析
        4.2.1 构建时间复杂度
        4.2.2 搜索时间复杂度
    4.3 分布式搜索系统设计方案
    4.4 本章小结
第5章 实验与分析
    5.1 数据集
    5.2 对比算法
    5.3 实验环境
    5.4 百万级数据实验结果与分析
        5.4.1 图结构算法优势分析
        5.4.2 NSG算法对比验证与分析
        5.4.3 其他结论与分析
    5.5 NSG算法时间复杂度验证
        5.5.1 索引构建时间复杂度
        5.5.2 搜索时间复杂度
    5.6 亿级数据实验结果与分析
        5.6.1 NSG性能对比测试
        5.6.2 分布式搜索系统可行性验证
        5.6.3 分析与结论
    5.7 本章小结
第6章 总结与展望
    6.1 总结
    6.2 展望
参考文献
攻读硕士学位期间的主要研究成果
致谢



本文编号：3702419