摘要：ICDE 2025IEEE 41st International Conference on Data Engineering 是数据库三大国际顶级学术会议之一，中国计算机学会（CCF）推荐的A类国际学术会议，今年的 ICDE 于 5 月 19 日到 23 日

ICDE 2025IEEE 41st International Conference on Data Engineering 是数据库三大国际顶级学术会议之一，中国计算机学会（CCF）推荐的A类国际学术会议，今年的 ICDE 于 5 月 19 日到 23 日在香港举行。 每届会议集中展示了当前数据库研究的前沿方向、工业界的最新技术和各国的研发水平，吸引了全球顶级研究机构投稿。其中来自新加坡国立大学和字节跳动数据库图团队的 《Vista: Vector Indexing and Search for Large-Scale Imbalanced Datasets》论文被 ICDE2025 收录为 Research Track 论文。

论文链接：https://github.com/YujianFu97/Vista-Technical-Report/blob/main/Vista_Technical_Report.pdf

作者：

Fu Yujian (新加坡国立大学/字节跳动）

Chen Cheng* (字节跳动）

Chen Yao (新加坡国立大学）

Wong Weng-Fai (新加坡国立大学）

He Bingsheng (新加坡国立大学）

随着生成模型的迅猛发展，如何高效构建其生成的高维嵌入向量的近似最近邻搜索（ANNS）索引，成为提升下游任务性能的关键。然而，现有ANNS方法在面对如GNN或GPT生成的分布不均衡的向量时，检索效率往往大幅下降。为了解决这一挑战，我们提出了Vista—— 一种基于动态索引构建的全新方案。Vista 通过感知向量分布，动态优化图索引结构，显著提升了在数据分布不平衡场景下的搜索效率。实验结果显示，无论是在公开数据集还是工业级真实环境中，Vista 相比主流索引算法HNSW在字节超大数据集上吞吐提升9.1倍， 在公有数据集上和如 Vamana、HCNNG等索引比实现了数倍至数十倍的检索性能提升，同时保持了高召回率和良好的可扩展性。

随着生成模型如GPT以及GNN在文本数据领域与图数据领域的广泛应用，其生成的高维嵌入向量表现出更加复杂且高度不均衡的分布特性。传统的近似最近邻搜索（ANNS）索引算法在面对此类不均衡数据时，往往因稀疏区域的点缺乏足够的图结构连接而导致查询效率骤降，难以满足工业级应用对高吞吐与低时延的需求。

1.ANNS基础与图索引现状

k 近邻搜索（k-NN）是机器学习、推荐系统和信息检索等领域的核心任务，通过在高维空间中近似地找出与查询向量最相似的 k 个邻居，以实现高效的检索与推荐。传统方法如倒排索引、局部敏感哈希（LSH）等，受限于高维“维度灾难”和海量数据规模，在精度与效率之间难以兼顾。近年来，图结构索引（如 HNSW、Vamana、HCNNG 等）通过稀疏化邻接图与多级跳跃结构，实现了显著的吞吐提升与可控的搜索时延。

然而，现有图索引算法大多假设数据分布相对均匀，忽略了嵌入向量分布的偏斜性。我们在电商场景中观察到，GNN 生成的用户-商品嵌入中，热门商品（dense cluster）与小众商品（sparse cluster）聚簇程度差异巨大；GPT 生成的文本嵌入则呈现语义相似词聚簇、语义远离词分散的分布。

【图1：GNN 与GPT嵌入向量聚簇示例】

图中左侧展示了 GNN 在电商用户-商品交互图上的嵌入结果，其中热门商品形成若干高密度簇，而小众商品分布稀疏；右侧展示了 GPT 在文本语义空间的嵌入结果，语义相似词语（如“repayment”，“refund”）聚集成簇，语义不同词语则离散分布。由此可见，生成模型所引入的多源、多模态特征导致向量分布的高度不均衡。

2. 数据集可视化与不均衡度量

为了量化分布不均衡对 ANNS 性能的影响，我们选择 SIFT（1M×128）、DEEP（1M×96）、GloVe（1.2M×100）和 ByteECom1（1M×128）四个典型数据集，分别通过 t-SNE 降维可视化样本。

【图2：四个ANNS数据集（SIFT, DEEP, GloVe, ByteECom1）的 t-SNE 可视化】

SIFT 数据集呈现相对均匀的散点分布；DEEP 数据集部分区域出现高密度簇；GloVe 数据集在语义维度上形成多个大小不一的簇；ByteECom1 则展示了极端不均衡，部分簇内点密集，而大部分点分散。基于上述可视化，我们引入 k-NN 连接度（Connectivity）作为衡量分布不均衡的指标：向量 v 在 k-NN 图中被其他向量选为邻居的次数，即其入度。在高维空间中，某些点的 k-NN 连接度极低（入度

【图3：三个数据集 k-NN 连接度分布直方图】

我们选取四个数据集中三个million-scale的数据集进行分析。以 k=50 为例，三幅 k-NN 入度直方图均呈明显的长尾分布：左侧的峰值区域表明大多数向量集中在中等连通度（20–40 条入边）附近，而右侧长长的尾部则揭示了少数节点拥有极高入度。具体来看，SIFT 中约 8% 向量入度低于 10，62% 入度低于 50；DEEP 中极低入度节点比例略高，63% 向量入度低于 50；ByteECom1 中高达 72% 向量入度低于 50。

3. 低连接度点的检索成本

低连接度点在图索引中的检索成本显著高于高连接度点。我们以 Vamana 索引为例，统计不同连接度下的平均距离计算次数。

Connectivity

(×10^2)

10

8.17

1.68

3.73

50

6.82

0.72

1.48

100

6.39

0.61

0.59

200

6.16

0.58

0.33

【表I：Vamana 索引中，不同 k-NN 连接度的向量检索成本】

【图4：连接度与距离计算次数关系曲线】

随着连接度从 10 提升至 200，SIFT 的平均距离计算次数减少约 25%；DEEP、ByteECom1 的降幅更为显著，分别超过 60% 和 90%。这表明，固定的搜索策略对低连接度点惩罚严重，严重影响整体 QPS。

4. 最小计算次数需求

在高召回场景下（Recall@10 ≥ 0.95），为保证覆盖稀疏点，索引需要为每个查询分配足够的候选列表长度。我们分析了 Recall10@10 不同配置下的向量检索成本变化，同时我们记录每个数据点达到目标召回所需的最小距离计算次数

【图5：数据点达到目标召回所需的最小计算次数分布以及ByteECom1 数据集中不同 Recall10@10 下的连接度分布与平均成本对比】

随着 Recall 从 0.80 提升至 0.95，检索的低连接度（

5. 核心动机

上述分析揭示：

现代嵌入模型生成的向量在高维空间中形成极不均衡的连接度分布，低连接度点占比不容忽视。

低连接度点的距离计算成本远高于高连接度点，且在高召回需求下进一步放大。

因此，本研究关注如何在 ANNS 图索引的构建与检索过程中，引入分布感知机制：对稀疏区域动态增补边，对连接度高的节点执行边交换剪枝，并在检索时根据查询向量的连接度自适应分配搜索资源，以期在保证高召回的同时，实现大规模并行高效检索。

Vista 构建阶段围绕“局部自适应”与“全局平衡”原则展开，主要包含以下三大流程：

1. 随机投影树分区与初始近邻估计

1.随机投影树（RPT）分区

构建 R 棵随机投影树，将样本递归投影并划分，直至叶节点中包含不超过 L 个向量（典型 L 取 100–200）。该分区有效保留了局部空间结构，并将全局近邻搜索问题拆解为多个小规模叶内搜索。

【图6：两棵 RPT 在二维空间中的切分示例 】

不同颜色代表不同叶子，展示了投影线如何将数据均匀切割，确保每个子空间内点的连通性。

2.叶内近邻图初始化

在每个叶节点内，采用精确或近似 k-NN 方法，为节点保留前 K 条最近邻向量，分别插入 InEdges 和 OutEdges 列表，构建初始 k-NN 图。通过将近邻搜索限制在小规模叶内子空间，不仅节省了全局搜索开销，还能较好地捕获局部聚簇结构。

完成上述步骤后，每个节点具备初始入度和出度信息，为后续动态补偿和边交换提供基础度量。

2. 分布感知的候选边扩充

入度分布观测

汇总初始图中所有节点的入度统计，观察到大量节点入度显著低于平均水平，尤其在数据高度偏斜的场景中，低连接度节点（入度

局部候选扩充

针对入度较低的节点，动态扩充其候选边的搜索范围：在原有 K 条基础上，为稀疏节点分配额外的搜索预算，以便在更广阔的空间中寻找可能的近邻。预算的大小根据节点的相对稀疏程度灵活调整。此举等同于为稀疏节点“开通更多窗口”，以便在初始图无法覆盖的区域获取新的邻居。

Beam Search 候选重采样

在随机投影树的某一子空间内，以 Beam Search 方式展开，对被扩充节点执行多路径搜索，直至收集到足够数量的候选边。

候选合并与剪枝

将新采集的候选边与初始边合并，按照距离升序保留最紧邻的 K 条边，并同步在对应节点的反向边列表中插入对等连接，确保图的对称性。通过这一筛选机制，我们在最大程度提高连通性的同时，将冗余长边有效剔除。

3. 全局动态边交换

枢纽节点剪枝

对拥有过多出边的“枢纽”节点，统一保留距离最小的 K 条边，其余边汇入全局“边池”，以防止部分节点边数过剩导致整体图密集化。

稀疏需求计算

针对入度不足的稀疏节点，根据与期望出度 K 的差值，统计所需额外边数，形成需求列表。

边池贪心分配

按照边的距离优先级，从边池中依次分配最短边给最稀疏节点，并在原始节点和目标节点中插入新边，保持无向图的一致性。

图6分析：通过两轮边交换后入度分布对比，稀疏长尾显著收缩，大部分节点的入度集中在合理区间，图结构更均衡。

迭代重平衡

重复剪枝和分配过程 2–3 轮，直至边池资源耗尽或节点需求基本满足，确保全局连接度分布达到相对稳定的状态。

为验证Vista在大规模不均衡向量数据集上的构建与检索性能，我们在多维度上展开系统化实验，涵盖数据规模、基线对比、分布偏斜、低连接度向量优化和构建开销几大方面。

实验环境与基线方法

硬件平台：单机 Intel Xeon Platinum 8336C，128核，2TB内存，OpenMP 并行。

评价指标：构建时间（Construction Time）、查询吞吐（QPS）、Recall10@10、低连接度向量的最小距离计算次数。

基线方法：Vamana、HNSW、HCNNG、LSHAPG（仅限 24h 可构建）。

在 1M–1B 向量规模的 DEEP、ByteECom1、ByteECom2 以及 Synthetic Uniform、Synthetic A（多簇）五种数据集上，保持 Recall10@10为特定阈值，比较各方法 QPS 性能和加速比，结果见 表II：

Vista 在所有数据集上均实现了远超基线的吞吐提升，其中相对 Vamana 的加速比在 2–5× 区间，且在高达 1B 规模的 DEEP-1B 和 ByteECom1-700M 上依然保持 4–6× 的加速优势。与 HNSW 和 HCNNG 的对比也体现出平均 3× 以上提升。

2. 可扩展性分析

在ByteECom1数据集上随着数据规模从 1M → 10M → 100M → 700M，Vista相对于表现第二好的方法始终保持约 2× 加速比，充分体现了 Vista 构建与索引对超大规模场景的优良可扩展性。随着规模增长，基线方法受内存访问和图结构稀疏性的影响，性能下降更为剧烈。

3. 分布偏斜（Skewness）适应性

针对 Synthetic A 数据（簇数 1、10、50、100），以及 Synthetic Uniform（无簇），保持 1M 规模，测试 QPS 与 Recall10@10，随着簇数从 1→100，数据分布由均匀转向高度偏斜，Vamana QPS 逐步下降超过 60%，展现出其对于不同分布的不稳定性，而 Vista性能始终保持稳定。说明 Vista 的候选扩充与边交换策略能有效缓解极端偏斜对检索性能的冲击。

4. 低连接度向量优化效果

重点考察低连接度向量的搜索成本，在 DEEP-1M 与 ByteECom1-1M 两组数据上统计最小距离计算次数，结果见 图10：

【图7：低连接度向量最小距离计算次数】

在两个数据集中，Vista相对基线方法对于低连通度向量的检索展现出明显的计算次数下降，减少超 55%。这一显著下降不仅降低了稀疏点的检索瓶颈，也间接提升了整体 QPS。

字节跳动基础架构数据库团队，致力于构建认知型数据基础设施，持续定义数据技术的未来边界。团队基于全栈自研技术，打造了涵盖关系型数据库、NoSQL 数据库、大规模图平台、多模态搜索、云原生中间件等十余项产品的数据库矩阵，用独创的技术架构实现事务处理、混合查询、智能检索等全场景覆盖。我们不仅支撑集团核心业务，更通过火山引擎为客户提供具备企业级稳定性的数据库产品，助力客户以数据驱动实现业务增长。团队在大规模分布式架构、极致性能计算/存储引擎、软硬协同优化等领域具备顶尖技术积淀。

图技术团队隶属于字节跳动基础架构数据库团队，专注于图数据库、图计算、图神经网络（GNN）、GraphRAG 等图相关技术方向，支撑抖音、今日头条、番茄小说等公司核心业务场景的落地。团队在相关技术领域已累计在 SIGMOD、VLDB、ICDE 等国际顶级会议上发表论文 8 篇，并积极参与业界标准的制定工作，是 LDBC 理事会、大数据技术标准推进委员会、图智能计算分会等组织的成员单位。

来源：字节跳动技术团队