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.

In real-world information retrieval scenarios, addressing data incompleteness is crucial for providing accurate similarity scores and ensuring reliable results for downstream tasks. Previous Similarity Matrix Completion (SMC) methods aim to estimate a similarity matrix that exhibits positive semi-definiteness (PSD) from an inaccurate one. However, these methods are inadequate in cases where the initial similarity matrix$S^{0}$exhibits PSD. In this paper, we propose a novel SMC framework that simultaneously explores the symmetric, positive semi-definiteness (PSD), and low-rank properties to provide an accurate and efficient solution for similarity search tasks. Specifically, we exploit the low-rank property and introduce an efficient specialized Cholesky factorization (CF) technique into the conventional SMC framework, which is implemented via a regularizer. It improves computational efficiency by learning a smaller factorized matrix instead of the entire similarity matrix. Moreover, to enhance the optimality guarantees of SMC, we introduce a novel lower-rank matrix property and design two corresponding regularizers. Building upon these meticulous designs, our novel SMC framework, for the first time, ensures both efficiency and accuracy with theoretical guarantees. Consequently, we propose two novel algorithms, i.e., SMCFN/SMCRN, to implement the SMC framework. Theoretical analysis verifies the effectiveness and fast convergence speed of SMCFN/SMCRN. Extensive experiments on five real-world datasets validate our theoretical analysis: SMCFN/SMCRN achieves up to 42% lower RMSE (e.g., 0.34 vs. 0.59 on ImageNet) and 15% higher Recall than state-of-the-art baselines, while being the most efficient among all baseline methods.

Online Continual Learning (OCL) requires models to learn sequentially from data streams with limited memory. Rehearsal-based methods, particularly Experience Replay (ER), are commonly used in OCL scenarios. This paper revisits ER through the lens of $\epsilon$-constraint optimization, revealing that ER implicitly employs a soft constraint on past task performance, with its weighting parameter post-hoc defining a slack variable. While effective, ER's implicit and fixed slack strategy has limitations: it can inadvertently lead to updates that negatively impact generalization, and its fixed trade-off between plasticity and stability may not optimally balance current streaming with memory retention, potentially overfitting to the memory buffer. To address these shortcomings, we propose the \textbf{G}radient-Guided \textbf{E}psilon \textbf{C}onstraint (\textbf{GEC}) method for online continual learning. GEC explicitly formulates the OCL update as an $\epsilon$-constraint optimization problem, which minimize the loss on the current task data and transform the stability objective as constraints and propose a gradient-guided method to dynamically adjusts the update direction based on whether the performance on memory samples violates a predefined slack tolerance $\bar{\varepsilon}$: if forgetting exceeds this tolerance, GEC prioritizes constraint satisfaction; otherwise, it focuses on the current task while controlling the rate of increase in memory loss. Empirical evaluations on standard OCL benchmarks demonstrate GEC's ability to achieve a superior trade-off, leading to improved overall performance. Code is available at https://github.com/laisong-22004009/GEC_OCL.

The similarity matrix is at the core of similarity search problems. However, incomplete observations are ubiquitous in real scenarios leading to a less accurate similarity matrix. To alleviate this problem, in this paper, based on the key insight that the similarity matrix enjoys both the symmetric and positive semi-definiteness (PSD) properties, we propose a novel similarity matrix calibration method, which is scalable, effective, and sound. Specifically, we establish the PSD property as a constraint for the similarity matrix calibration problem and propose a novel similarity matrix calibration method to estimate the similarity matrix, which approximates the unknown complete ground-truth similarity matrix. To enable a fast optimization process, we further develop a general approximated algorithm that bypasses the computation of singular values. Theoretical analysis ensures stable calibration performance and convergence speed. Extensive experiments of similarity matrix calibration on real-world datasets demonstrate that our proposed method outperforms baseline methods in terms of both accuracy and speed.

Maximum inner product search (MIPS), combined with the hashing method, has become a standard solution to similarity search problems. It often achieves an order of magnitude speedup over nearest neighbor search (NNS) under similar settings. Motivated by the work and achievements along this line, in this paper, we developed a sparse binary hashing method for MIPS to preserve the pairwise similarities with the support of two asymmetric hash functions. We proposed a simple and efficient algorithm that learns two hash functions for the query database and the search database respectively. We conducted experiments to evaluate the proposed method, relying on image retrieval tasks on four benchmark datasets. The empirical results clearly demonstrated the algorithm's promising potential on practical applications in terms of search accuracy and scalability.

Inspired by the recent discoveries in neuroscience, the study of the sparse binary projection model started to attract people's attention, shedding new light on image retrieval. Different from the classical work that tries to reduce the dimension of the data for faster retrieval speed, the model projects dense input samples into a higher-dimensional space and outputs sparse binary data representations after winner-take-all competition. Following the work along this line, this paper designed a new algorithm which obtains a high-quality sparse binary projection matrix through unsupervised training. Simple as it is, the algorithm reported significantly improved results over the state-of-the-art methods in both search accuracy and retrieval speed in a series of empirical evaluations on large-scale image retrieval tasks, which exhibited its promising potential in industrial applications.