Similarity Search with Data Missing

Changyi Ma

doi:10.1145/3724124

2026-02-01

PRE

Changyi Ma

宋轩 (Xuan Song) *

DOI：10.1145/3724124

原文链接

原文求助

摘要

En 中文

相似性搜索是一个具有广泛应用的基础研究问题，涵盖数据挖掘、信息检索和机器学习等多个研究领域。相似性搜索的核心思想是基于特定的相似性度量，在大型数据库中搜索所有候选项中与给定查询项具有最高相似性得分的最相似数据样本。然而，它可能面临高昂的计算成本和存储成本，这促使我们在各种场景下设计有效且快速的相似性搜索算法。但在实际场景中，数据缺失是不可避免的，这会导致相似性得分不准确，进而导致相似性矩阵不准确。因此，在不完整观测数据的情况下，获得准确的相似性矩阵并非易事。为解决此问题，我们提出了一种相似性矩阵校准方法，用于估计高质量的相似性矩阵，并进一步提升相似性搜索性能。首先，我们提出一个目标函数，以最小化初始不准确相似性矩阵与最优估计相似性矩阵之间的差异，其中利用了固有的对称性和正半定性（PSD）属性作为约束来指导校准过程。然后，我们设计了一种高效算法，提供近似真实相似性矩阵的高质量相似性矩阵。理论分析证明了我们提出方法的有效性，并在真实数据集上的大量实验结果验证了该方法在相似性矩阵校准任务和下游相似性搜索任务中的有效性和效率。

Keyword:

Similarity Search

Data Missing

Positive Semi-Definiteness