Approximate nearest neighbor (ANN) searches are commonly employed in various machine learning applications, such as recommendation systems, but traditional ANN searches typically involve only a single reference vector in a query. To broaden the capabilities of ANN search and support multi-reference-vector queries, thereby enabling a wider range of machine learning applications, we introduce all/any-k ANN search. They aim to find vectors that are similar to all or any of the multi-reference vectors in a query, respectively. To effectively and efficiently support all/any-k ANN search, we first propose distance metrics to evaluate the ranking of vectors among those in the dataset for exact all/any-k NN. Building on this, we introduce search algorithms and prove they can search according to the proposed distance metrics on graph indexes designed for traditional ANN. Additionally, we further introduce two-stage search algorithms for all/any-k ANN search to further enhance their search performance. We conduct extensive experiments on real-world datasets to validate the efficiency and effectiveness of our proposed algorithms compared to existing approaches.

Sparse matrix multiplications are essential in scientific computing and machine learning applications. Recent researches offload sparse operations, such as sparse matrix-matrix multiplication (SpMM) and sampled dense-dense matrix multiplication (SDDMM), on Tensor Cores (TCs) for improved performance. However, their performance is often limited by the matrix's inherent sparsity and irregularity. In this paper, we find row reordering can potentially improve sparse operations on TCs, but existing reordering techniques exhibit limitations that hinder their effectiveness. To address the issues, we propose Groot, a graph-centric row reordering algorithm with tree. Groot aims to minimize row differences across the matrix, which is proved to be a NP-hard problem. To approximate the optimal solution, Groot firstly captures the local structure of the sparse matrix by constructing a k-nearest neighbor graph, where rows are represented as nodes. Then, it extracts a minimum spanning tree from the constructed graph for global structure optimization. Lastly, Groot traverses the extracted tree to obtain the final ordering. We evaluate Groot using real-world datasets in comparison with state-of-the-art reordering algorithms. Our results show that Groot significantly enhances the computational intensity of SpMM and SDDMM on TCs, delivering the average speedups of 1.8× and 2.0×, respectively. Furthermore, the performance gains extend broadly to sparse computations on CUDA cores and GNN systems.

k -ANN search has been extensively studied to find k approximate nearest neighbors for a given query vector in a high-dimensional dataset, where a data item is represented as a vector. As there are many new emerging real-world applications that have categorical/numerical attributes associated with vectors, it is highly needed to support k -ANN search with additional predicates on such attributes. In this paper, we study k -ANN queries, q = (v q , c q ), where v q is a query vector and c q is a predicate on categorical/numerical attributes. Note that the conventional k -ANN search is a k -ANN query when c q = ∅. In the literature, some can support the cases when c q = ∅, some can support the cases when c q is on categorical attributes, and some can support the cases when c q is on numerical attributes. But none of them can support all cases efficiently. In this paper, we propose an all-in-one approach. Our approach supports conventional k -ANN search in the same way as the state-of-the-art approaches, and supports the predicates in a similar or even better way compared to the approaches that are tailored to support either categorical attributes or numerical attributes. We conduct extensive performance studies and confirm the accuracy and the efficiency of our approach in comparison with the state-of-the-art approaches.

Network resilience is a critical ability of a network to maintain its functionality against disturbances. A network is resilient/robust when a large portion of the nodes are to be better engaged in the network, i.e., they are less likely to leave given the changes on the network. Existing studies validate that the engagement of a node can be well captured by its coreness on network topology. Therefore, it is promising to maximize the number of nodes with increasing coreness values. In this paper, we propose and study thefollower maximization problem: maximizing the resilience gain (the number of coreness-increased vertices) via anchoring a set of vertices within a given budget. We prove that the problem is NP-hard and W[2]-hard, and it is NP-hard to approximate within an O(n^1-ε ) factor. We first propose an advanced greedy approach, followed by a time-dependent framework designed to quickly find high-quality results. The framework is initialized by the advanced greedy algorithm and incorporates novel techniques for optimizing the search space. The effectiveness and efficiency of our solution are verified with extensive experiments on 8 real-life datasets. Our source codes are available at https://github.com/Tsyxxxka/Follower-Maximization.

The rapid rise and prevalence of social platforms have created great demands on effective schemes to limit the influence of negative information, e.g., blocking key vertices for influence minimization. However, there is currently no system providing practical schemes to solve the negative influence minimization problem with a blocking budget effectively and efficiently in the literature. In this demo, we present IMinimize, the first interactive system that provides audiences with vertex-blocking schemes over different budgets and demonstrates via visualization for comparison vividly and directly, aiming to help minimize the negative influence spreading in networks. Our IMinimize system applies an advanced greedy algorithm to select blocked vertices with both high efficiency and effectiveness. Furthermore, we extend IMinimize to the application of epidemic controlling and prevention and show the usability of IMinimize through two case studies of real-life applications.