加速最大内积检索的两个ball-树优化

发布时间：2021-10-07 20:50

　　最大内积检索是一个相对比较新的问题,但在许多应用中都发挥着重要作用,如基于矩阵分解的协同过滤、文档检索、最大核搜索等。其正式的定义如下：给定一个有n个数据点的集合D（?）sRd,一个查询q∈sRd,最大内积检索问题要求我们快速地找到一个向量v*∈D,使得,其中<*,*)表示两个向量间的内积。由于问题的重要性,目前已经有很多文献针对最大内积检索提出（精确或近似的）解决方案。ball-树是目前最大内积检索中常用的数据结构。其具有高效、简单以及易于实现等优点。我们对ball-树的性能分析结果指出,ball-树在搜索的过程中超过90%的时间都是花费在内积计算上。因此,内积计算是提升算法性能的一个瓶颈。搜索过程中有两个地方需要进行内积计算：（1）每次上界计算都需要一次内积计算。我们用瓜表示搜索过程中上界计算的次数；（2）搜索访问到的叶子中的每个数据点都需要与查询计算一遍内积。我们用Xv表示需要与查询计算内积的数据点的个数。很明显,如果我们能将XN和Xv降下来,我们将能够更快地进行最大内积检索。本文通过挖掘内积计算的性质,提出了两个简单且高效的优化,分别降低了XN和Xv,从而提高了ball-... 

【文章来源】：中山大学广东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：65 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 引言
    1.1 最大内积检索问题
    1.2 最大内积检索问题的应用
    1.3 最大内积检索的难点
    1.4 论文的贡献
    1.5 论文的安排
第二章 相关工作
    2.1 精确算法
    2.2 近似算法
第三章 我们的优化
    3.1 ball-树的代价模型
    3.2 点级别的剪枝
    3.3 协同上界计算
    3.4 算法
第四章 实验与分析
    4.1 实验介绍
    4.2 实验结果
第五章 总结与展望
    5.1 研究总结
    5.2 未来工作
参考文献
致谢



本文编号：3422751