Similarity Search with Data Missing

Similarity search is a fundamental research problem with broad applications in various research fields, including data mining, information retrieval, and machine learning. The core idea of similarity search is to find the most similar data sample of given query items, based on a specific similarity metric with the highest similarity score with all the search candidates in a large-scale database. It may suffer from a prohibitive computation cost and storage cost, which motivates us to design effective and fast similarity search algorithms in various scenarios. However, data missing is unavoidable in real-world scenarios, which results in a less accurate similarity score and further leads to an inaccurate similarity matrix. Therefore, obtaining an accurate similarity matrix is non-trivial when there are incomplete observations. To solve this problem, we propose a similarity matrix calibration method to estimate a high-quality similarity matrix and further provide a better similarity search performance. Firstly, we propose an objective function to minimize the difference between the initial inaccurate similarity matrix and the optimal estimated similarity matrix, where the inherent symmetric and Positive Semi-Definiteness (PSD) properties are utilized as the constraint to guide the calibration process. Then, we design an effective algorithm with high efficiency to provide a high-quality similarity matrix that approximates the ground-truth similarity matrix. Theoretical analysis demonstrates the efficiency guarantee of our proposed method, and extensive experimental results on real-world datasets verify the effectiveness and efficiency of the proposed method on the similarity matrix calibration task and the downstream similarity search task.