用钻石采样实现最大全对点点积(MAD)近似搜索
本文提出了一种名为 BanditMIPS 的随机算法,解决了在高纬度情况下复杂度至少为 O (根号 d) 的 MIPS 任务。此算法通过自适应子采样和多臂老虎机策略来估计每个原子的内积,并在理论和实验中都得到了证明。
Dec, 2022
本文介绍了一种新的基于 MapReduce 算法的 WHIMP,结合了 Cohen-Lewis 的 wedge-sampling 方法和 Charikar 的 SimHash 随机投影技术,在处理具有数十亿边的大型社交网络上,具有近乎最佳的通信成本,同时保持了与现有技术相当的计算成本,成功地处理了 Twitter 等大型数据集,准确地找到了高相似度对。
Mar, 2017
本文提出了针对内积最优匹配问题的新型分支边界算法,包括使用树形结构的一般分支边界算法、针对多个查询的双树算法以及新型数据结构等,实验结果表明与朴素搜索技术相比,该算法能使查询时间提升高达 5 个数量级。
Feb, 2012
我们提出了一种能够以比现有技术快 12 倍以上的速度压缩矢量并加速近似向量操作的矢量量化算法,用于计算近似点积等操作的速度可提高 10 倍以上,可以加速最近邻搜索和最大内积搜索 100 倍以上,并且与现有的矢量量化算法相比误差竞争力强。
Jun, 2017
该研究探讨了分布式协议用于在大型数据集中查找所有相似向量对的方法,重点关注 Hamming 距离,提出了一种新型组合优化问题来捕捉分析上的核心,展示了边等周形状的设计方法和新的距离相关性界限。
Nov, 2016
本文提出了一种新的随机方法来计算两个 n x n 矩阵的 min-plus product,从而在具有任意边权的密集 n 节点有向图中解决全对最短路径问题,该算法在 word RAM 上的运行时间为 n^3 / 2^(Ω((logn)^1/2)) + n^(2 + o (1)) log M,这个新算法应用了电路复杂性中的工具,即 Razborov-Smolensky 多项式来近似表示 AC^0 [p] 电路,以有效地将在(min,+)代数上的矩阵乘积减小到一些相对较小的矩形矩阵乘积中,每个矩阵乘积都可以使用 Coppersmith 的一种特别有效的方法进行计算。
Dec, 2013
本文主要探讨了最大内积搜索的效率问题,提出了一种基于 k 均值聚类算法的简单方法,在保证检索准确率的同时显著提高检索速度,并在两个标准推荐系统基准测试和大词汇量词嵌入上进行了实验证明。
Jul, 2015
本文考虑利用 Wang 等人(2013)的算法对图进行主动搜索,通过在数据上的相似函数来最小化图上的能量函数以选择点,并且提出了一些关键修改,使其能够跨大规模数据集进行扩展,并实现了与现有半监督方法相竞争的实验结果。
Apr, 2017
通过使用混合逻辑 (MoL) 模型代替点积来准确表示复杂的用户 - 物品互动,结合 extit {h-indexer} 层级检索策略能够在单个 GPU 上扩展到 1 亿个语料库,并在公共数据集中取得了高达 77.3%的命中率提高。
Jun, 2023