SPTAG组合的两种结构
作者说明区分SPTAG-KDT(kd-tree与relative neighborhood graph)和SPTAG-BKT(balanced k-means tree与RNG)。BKT不是沿某坐标中位数二分的另一名字。树提供一组搜索种子,图增强连通和导航,树与图搜索可交替进行。
也不能假定每个叶子独立建朴素kNN图、只有几个切分面边界点拥有跨叶边;这种限制不是作者给出的SPTAG结构合同。
本卷可核对的最小组合
教学树用两个初始中心,按各点到两中心的距离差排序,等量分配后更新中心,有限轮后递归;叶上限4,16点形成4个叶。这个平衡聚类过程有真实成员和中心,不是仅返回“叶数4”的公式。
查询用中心距离优先访问树节点以取得有限叶种子,再从种子中选入口,在一个全局相对邻域风格图上搜索。图用alpha1几何规则构造,可拥有跨叶边。测试让图从种子所在叶跨到邻叶,并与Flat TopK对照。
哪些细节不能冒充SPTAG
本模型没有SPTAG的全部候选调度、树图交替策略、参数、并行构建、动态维护或存储文件。叶中心距离也不被当作严格距离下界,不能据此声称精确剪枝保证。固定源码提交cafdd0abf261可沿BKTree的BuildTrees/SearchTrees、RelativeNeighborhoodGraph和BKTIndex的BuildGraph/SearchIndex对照;教学组合并不复刻全部调度。
原稿中“diskann模块用例6实现BKT切分”的声明并不存在;实验包提供实际树与图结构,但仍明确它只是教学组合,不是移植或部署SPTAG。
验收看跨结构传递
必须保存树种子ID、后续图候选和最终结果,证明不是先全库精确排序再贴上树/图名字。树只找到种子却不能让图继续搜索,或只有叶内图而没有跨区路径,都不能用“与穷举一致”的单个数字掩盖。
架构与流程
flowchart TD
P["库向量"] --> B["平衡聚类树:中心与成员"]
P --> G["全局RNG风格邻接;含跨叶边"]
Q["查询"] --> S["按树搜索取得种子ID"]
B --> S
S --> NAV["用种子启动图导航"]
G --> NAV
NAV --> TOP["有限候选与TopK"]
TOP --> GT["同数据Flat真值对照"]
实现与验证边界
模型构建平衡聚类树和全局几何图,测试跨叶导航。SPTAG产品没有部署,本节主要一手依据为作者仓库,删除错误的域泛化论文链接。
下载卷十三实验包
。Java 8入口为 lab.RunAll;本节对应 diskann.DiskannSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。