SPTAG (Space Partition Tree And Graph，空间分区树与图) 是一种高性能的向量相似度搜索算法，它结合了空间分区树和可导航小世界图的优点。该算法由微软开发，特别适用于大规模、高维度的最近邻搜索问题。
本演示实现了以下功能：
sptag/
├── index.html # 主页面
├── sptag.js # SPTAG实现
└── style.css # 样式文件
class SPTAGNode {
constructor(vector, id) {
this.vector = vector;
this.id = id;
this.neighbors = new Set();
this.treeChildren = [null, null];
}
}
function buildKDTree(points, depth = 0) {
if (points.length === 0) return null;
const axis = depth % dimension;
points.sort((a, b) => a.vector[axis] - b.vector[axis]);
const median = Math.floor(points.length / 2);
const node = points[median];
node.treeChildren[0] = buildKDTree(points.slice(0, median), depth + 1);
node.treeChildren[1] = buildKDTree(points.slice(median + 1), depth + 1);
return node;
}
function buildGraph(nodes, k) {
for (const node of nodes) {
const neighbors = findApproximateNN(node, nodes, k);
for (const neighbor of neighbors) {
node.neighbors.add(neighbor);
neighbor.neighbors.add(node);
}
}
}