Vector database systems have been gaining more and more attention in recent years with the prevalence of Large Language Models. As the most important algorithmic component behind vector database systems, nearest neighbor search has been studied for decades and various approaches are proposed for efficient vector retrieval. Among these proposals, the graph-based search paradigm is able to achieve desirable accuracy-efficiency tradeoff, and thus has been widely used in many industrial vector retrieval engines. In this paper, however, we claim that its efficiency is largely handicapped by two unnoticed performance issues - accuracy saturation and long-tail queries, especially when the number of links is limited. Through both empirical and theoretical analysis, we identify that the existence of antihubs is the root cause of these performance limitations. To mitigates the negative impact of antihubs, we propose a highly efficient graph-based vector retrieval framework named Local Scaling Graph (LSG) by introducing more incident edges for them in a systematic way. We conduct comprehensive experiments using four state-of-the-art algorithms, i.e., HNSW, NSG, DiskANN and HNSWPQ, over a collection of 12 real-world datasets to validate the effectiveness and broad applicability of LSG. Empirical results show a speedup of up to two orders of magnitude over the state-of-the-art algorithms for approximate nearest neighbor search.

Recently, cross-modal hashing has attracted much attention due to its low storage cost and fast query speed. Mean Average Precision (MAP) is the most widely used performance measure for cross-modal hashing. However, we found that the MAP scores do not fully reflect the quality of the top-K results for cross-modal retrieval because it neglects multi-label information and overlooks the label semantic hierarchy. In view of this, we propose a new performance measure named Normalized Weighted Discounted Cumulative Gains (NWDCG) by extending Normalized Discounted Cumulative Gains (NDCG) using co-occurrence probability matrix. To verify the effectiveness of NWDCG, we conduct extensive experiments using three popular cross-modal hashing schemes over two publically available datasets.

In this paper, we study multimodal named entity recognition in social media posts. Existing works mainly focus on using a cross-modal attention mechanism to combine text representation with image representation. However, they still suffer from two weaknesses: (1) the current methods are based on a strong assumption that each text and its accompanying image are matched, and the image can be used to help identify named entities in the text. However, this assumption is not always true in real scenarios, and the strong assumption may reduce the recognition effect of theMNER model; (2) the current methods fail to construct a consistent representation to bridge the semantic gap between two modalities, which prevents the model from establishing a good connection between the text and image. To address these issues, we propose a general matching and alignment framework (MAF) for multimodal named entity recognition in social media posts. Specifically, to solve the first issue, we propose a novel cross-modal matching (CM) module to calculate the similarity score between text and image, and use the score to determine the proportion of visual information that should be retained. To solve the second issue, we propose a novel cross-modal alignment (CA) module to make the representations of the two modalities more consistent. We conduct extensive experiments, ablation studies, and case studies to demonstrate the effectiveness and efficiency of our method.The source code of this paper can be found in https://github.com/xubodhu/MAF.

Cross-modal hashing (CMH) maps heterogeneous multiple modality data into compact binary code to achieve fast and flexible retrieval across different modalities, especially in large-scale retrieval. As the data don't need a lot of manual annotation, unsupervised cross-modal hashing has a wider application prospect than supervised method. However, the existing unsupervised methods are difficult to achieve satisfactory performance due to the lack of credible supervisory information. To solve this problem, inspired by knowledge distillation, we propose a novel unsupervised Knowledge Distillation Cross-Modal Hashing method (KDCMH), which can use similarity information distilled from unsupervised method to guide supervised method. Specifically, firstly, the teacher model adopted an unsupervised distribution-based similarity hashing method, which can construct a modal fusion similarity matrix.Secondly, under the supervision of teacher model distillation information, student model can generate more discriminative hash codes. In two public datasets NUS-WIDE and MIRFLICKR-25K, extensive experiments have proved the significant improvement of KDCMH on several representative unsupervised cross-modal hashing methods.

Locality sensitive hashing (LSH) is a widely practiced c -approximate nearest neighbor( c -ANN) search algorithm in high dimensional spaces. The state-of-the-art LSH based algorithm searches an unbounded and irregular space to identify candidates, which jeopardizes the efficiency. To address this issue, we introduce the concept of virtual hypersphere partitioning. The core idea is to impose a virtual hypersphere, centered at the query, in the original feature space and only examine points inside the hypersphere. The search space of a hypersphere is isotropic and bounded, and thus more efficient than the existing one. In practice, we use multiple physical hyperspheres with different radii in corresponding projection subspaces to emulate the single virtual hypersphere. We also developed a principled method to compute the hypersphere radii for given success probability. Based on virtual hypersphere partitioning, we propose a novel disk-based indexing and searching scheme VHP to answer c -ANN queries. In the indexing phase, VHP stores LSH projections with independent B + -trees. To process a query, VHP keeps increasing the radii of physical hyperspheres co-ordinately, which in effect amounts to enlarging the virtual hypersphere, to accommodate more candidates until the success probability is met. Rigorous theoretical analysis shows that the proposed algorithm supports c -ANN search for arbitrarily small c ≥ 1 with probability guarantee. Extensive experiments on a variety of datasets, including the billion-scale ones, demonstrate that VHP could achieve different tradeoffs between efficiency and accuracy, and achieves up to 2x speedup in running time over the state-of-the-art methods.

With the rapid development of location-based social networks (LBSNs), point of interest (POI) recommendation has become an important way to meet users' personalized demands. The aim of POI recommendation is to provide personalized recommendation of POIs for mobile users. However, traditional POI recommendation systems cannot satisfy users' personalized demands. The reason is that the traditional POI recommendation system cannot recommend the next POI to a user based on the user's context information. Also, the traditional POI recommendation system provides no real-time guarantee on performance. In this demo, we propose a novel real-time next POI recommendation system named R2SIGTP which provides more personalized real-time recommendation compared with existing ones. Our system has the following advantages: 1) it has real-time performance; 2) it uses a unified approach to integrate geographic and preference information; 3) it considers the feedback of each single user to provide more personalized recommendation. We have implemented our system. R2SIGTP is easy to use and can be used by the mobile terminal's browser to recommend the next POI to the user in real-time based on the automatically identified user location and current time. The experimental results on real-world LBSNs show that R2SIGTP's performance is satisfactory.

Locality Sensitive Hashing (LSH) is widely recognized as one of the most promising approaches to similarity search in high-dimensional spaces. Based on LSH, a considerable number of nearest neighbor search algorithms have been proposed in the past, with some of them having been used in many real-life applications. Apart from their demonstrated superior performance in practice, the popularity of the LSH algorithms is mainly due to their provable performance bounds on query cost, space consumption and failure probability.

Real-time stream processing applications must be prepared to operate under overloaded conditions. Existing load shedding techniques are not suitable for processing real-time data streams because their tuple dropping policies may violate application deadlines in an uncontrolled way. We'd argue that a more precise load shedding model, e.g., the (m, k) deadline model adopted in this paper, is much appropriate than the commonly used random dropping policy. Based on the (m, k) load shedding model and a novel load shedding approach, we propose a concrete (m, k) scheduling algorithm called SOSA-DBP by exploiting application semantics. Experimental results show that SOSA-DBP has significant performance gain over the existing (m, k) scheduling algorithm.