The$\eta$-threshold decomposition in uncertain graphs, which calculates the$\eta$-thresholds for each vertex, is a fundamental problem for graph analysis. While existing studies on$\eta$-threshold decomposition primarily focus on static uncertain graphs, numerous real-world scenarios involve highly dynamic uncertain graphs. It is costly to recompute all$\eta$-thresholds from scratch whenever the uncertain graphs face update operations, e.g., edge insertion and deletion, and the modifications on edge probability. Motivated by this, we introduce efficient$\eta$-threshold maintenance algorithms tailored for dynamic uncertain graphs in this paper. Firstly, we investigate the impact of edge insertion and deletion on$\eta$-thresholds. Building upon this analysis, we introduce the maintenance algorithms designed to adjust the$\eta$thresholds for edge insertions or deletions within the uncertain graphs. Our approaches involve identifying a compact subgraph encompassing all vertices necessitating$\eta$-threshold updates, followed by an iterative process of vertex deletion to complete the$\eta$-threshold updates. To improve the efficiency, we devise three optimizations to further reduce the number of candidate$\eta$-thresholds requiring adjustment. Moreover, we extend the proposed algorithms to handle the$\eta$-threshold maintenance for edge probability change. Extensive experiments on both real and synthetic datasets demonstrate the efficiency of the proposed algorithms. The results reveal that our proposed algorithms consistently outperform the baselines, exhibiting improvements ranging from at least three orders of magnitude to as high as seven orders of magnitude.

Sparse Matrix-Matrix Multiplication (SpMM) is a fundamental operation in graph computing and analytics. However, the irregularity of real-world graphs poses significant challenges to achieving efficient SpMM for graph data on GPUs. Recently, the introduction of new efficient computing cores within GPUs offers new opportunities for acceleration. In this paper, we present HC-SpMM, a pioneering algorithm that leverages Hybrid GPU Cores (Tensor cores and CUDA cores) to accelerate SpMM for graphs. To adapt to the computing characteristics ofdifferent GPU cores, we investigate the impact of sparse graph features on the performance of different cores, develop a data partitioning technique for the graph adjacency matrix, and devise a novel strategy for intelligently selecting the most efficient cores for processing each submatrix. Additionally, we optimize it by considering memory access and thread utilization. To support complex graph computing workloads, we integrate HC-SpMM into the GNN training pipeline. Furthermore, we propose a kernel fusion strategy to enhance data reuse, as well as a cost-effective graph layout reorganization method to mitigate the irregularity of real-world graphs, better fitting the computational models of hybrid GPU cores. Extensive experiments on 14 real-world datasets demonstrate that HC-SpMM achieves an average speedup of 1.33× and 1.23× over state-of-the-art SpMM kernels and GNN frameworks.

An average person usually contains more than 10 trillion human cells, and each cell's transcriptome can be profiled by a single-cell RNA sequence (scRNA-seq). The huge volume and high complexity of scRNA-seq data put challenges on fundamental tasks of scRNA-seq data analysis, i.e., cell type identification and new cell type discovery. In this paper, we demonstrate scRAG, which can efficiently remove batch effect in cell-type identification and enable reliable new cell discovery, facilitated by GPU-based scRNA-seq data management and Large Language Models (LLMs). The GPU-based scRNA-seq data management enables high throughput scRNA-seq data retrieval and update, while the LLM utilizes the retrieval results to remove the batch effect and discover novel cells. We demonstrate scRAG for its: (a) interfaces, (b) GPU-based scRNA-seq data management, and (c) applications in batch effect removal and cancer cell discovery.

Approximate nearest neighbor search (ANNS) in high-dimensional vector spaces has a wide range of real-world applications. Numerous methods have been proposed to handle ANNS efficiently, while graph-based indexes have gained prominence due to their high accuracy and efficiency. However, the indexing overhead of graph-based indexes remains substantial. With exponential growth in data volume and increasing demands for dynamic index adjustments, this overhead continues to escalate, posing a critical challenge. In this paper, we introduce Tagore, a fas T library a ccelerated by G PUs f or graph ind e xing, which has powerful capabilities of constructing refinement-based graph indexes such as NSG and Vamana. We first introduce GNN-Descent, a GPU-specific algorithm for efficient k-Nearest Neighbor (k-NN) graph initialization. GNN-Descent speeds up the similarity comparison by a two-phase descent procedure and enables highly parallelized neighbor updates. Next, aiming to support various k-NN graph pruning strategies, we formulate a universal pruning procedure termed CFS and devise two generalized GPU kernels for parallel processing complex dependencies in neighbor relationships. For large-scale datasets exceeding GPU memory capacity, we propose an asynchronous GPU-CPU-disk indexing framework with a cluster-aware caching mechanism to minimize the I/O pressure on the disk. Extensive experiments on 7 real-world datasets exhibit that Tagore achieves 1.32x to 112.79x speedup while maintaining the index quality.

In high-dimensional vector spaces, Approximate Nearest Neighbor Search (ANNS) is a key component in database and artificial intelligence infrastructures. Graph-based ANNS methods, particularly HNSW, have emerged as leading solutions, offering an impressive trade-off between search efficiency and accuracy. Many vector databases utilize graph indexes as their core algorithms, benefiting from various optimizations to enhance search performance. However, the high indexing time associated with graph algorithms poses a significant challenge, especially given the increasing volume of data, query processing complexity, and dynamic index maintenance demand. This has rendered indexing time a critical performance metric for users. In this paper, we comprehensively analyze the underlying causes of the low graph indexing efficiency on modern CPUs, identifying that distance computation dominates indexing time, primarily due to high memory access latency and suboptimal arithmetic operation efficiency. We demonstrate that distance comparisons during index construction can be effectively performed using compact vector codes at an appropriate compression error. Drawing from insights gained through integrating existing compact coding methods in the graph indexing process, we propose a novel compact coding strategy, named Flash, designed explicitly for graph indexing and optimized for modern CPU architectures. By minimizing random memory accesses and maximizing the utilization of SIMD (Single Instruction, Multiple Data) instructions, Flash significantly enhances cache hit rates and arithmetic operations. Extensive experiments conducted on eight real-world datasets, ranging from ten million to one billion vectors, exhibit that Flash achieves a speedup of 10.4× to 22.9× in index construction efficiency, while maintaining or improving search performance.

Similarity search finds objects that are similar to a given query object based on a similarity metric. As the amount and variety of data continue to grow, similarity search in metric spaces has gained significant attention. Metric spaces can accommodate any type of data and support flexible distance metrics, making similarity search in metric spaces beneficial for many real-world applications, such as multimedia retrieval, personalized recommendation, trajectory analytics, data mining, decision planning, and distributed servers. However, existing studies mostly focus on indexing metric spaces on a single machine, which faces efficiency and scalability limitations with increasing data volume and query amount. Recent advancements in similarity search turn towards distributed methods, while they face challenges including inefficient local data management, unbalanced workload, and low concurrent search efficiency. To this end, we proposeDIMS, an efficientDistributedIndex for similarity search inMetricSpaces. First, we design a novel three-stage heterogeneous partition to achieve workload balance. Then, we present an effective three-stage indexing structure to efficiently manage objects. We also develop concurrent search methods with filtering and validation techniques that support efficient distributed similarity search. Additionally, we devise a cost-based optimization model to balance communication and computation cost. Extensive experiments demonstrate that DIMS significantly outperforms existing distributed similarity search approaches.

Owing to the widespread deployment of smartphones and networked devices, massive amount of data in different types are generated every day, including numeric data, locations, text data, images, etc. Nearest neighbour search in multi-metric spaces has attracted much attention, as it can accommodate any type of data and support search on flexible combinations of multiple metrics. However, most existing methods focus on single metric queries, failing to answer multi-metric queries efficiently due to the complex metric combinations. In this paper, for the first time, we study the approximate nearest neighbour search (ANNS) in multi-metric spaces, and propose HJG, a hierarchical joint graph, to solve the multi-metric query efficiently and effectively. HJG constructs hierarchical graphs for modeling objects of various types, and applies our presented balancing techniques to improve the graph distribution. To support efficient and accurate nearest neighbour search, we join individual graphs dynamically with high efficiency, and develop filtering techniques with efficient search strategy for HJG. Extensive experiments on four datasets demonstrate the superior effectiveness and scalability of our proposed HJG.

Core models are well-known cohesive subgraph models for graph analytics that have been extensively studied. These models, including (α, β)-core, (k, l)-core, and k -core, have multiple parameters, which are referred to as multi-dimensional cores. The goal of core search is to retrieve subgraphs from a graph that satisfy the semantics of a given core model. In the literature, various indexes have been proposed to accelerate core search for different core models. However, existing indexes suffer from several limitations, such as significant redundancy, lack of scalability with respect to the number of parameters, limited generality, and inadequate consideration of index maintenance. To address these limitations, in this paper, we thoroughly investigate the problem of multi-dimensional core search. In particular, we propose a novel index called MCR-Tree, which can be applied to different core models. The MCR-Tree projects all vertices into a multi-dimensional space by leveraging the skyline corenesses, which are indexed by an R-tree. Furthermore, the MCR-Tree integrates the connectivity information of subgraphs into the nodes of the R-tree to facilitate multi-dimensional core search. Subsequently, an efficient branch-and-bound algorithm is designed to perform multi-dimensional core search by traversing the MCR-Tree. Additionally, we discuss how to maintain the MCR-Tree for graph updates. Extensive experiments demonstrate that the MCR-Tree is up to two orders of magnitude smaller than existing indexes and the MCR-Tree-based core search method is up to an order of magnitude faster than existing algorithms.

Similarity search, the task of identifying objects most similar to a given query object under a specific metric, has gathered significant attention due to its practical applications. However, the absence of coordinate information to accelerate similarity search and the high computational cost of measuring object similarity hinder the efficiency of existing CPU-based methods. Additionally, these methods struggle to meet the demand for high throughput data management. To address these challenges, we propose GTS, a GPU-based tree index designed for the parallel processing of similarity search in general metric spaces, where only the distance metric for measuring object similarity is known. The GTS index utilizes a pivot-based tree structure to efficiently prune objects and employs list tables to facilitate GPU computing. To efficiently manage concurrent similarity queries with limited GPU memory, we have developed a two-stage search method that combines batch processing and sequential strategies to optimize memory usage. The paper also introduces an effective update strategy for the proposed GPU-based index, encompassing streaming data updates and batch data updates. Additionally, we present a cost model to evaluate search performance. Extensive experiments on five real-life datasets demonstrate that GTS achieves efficiency gains of up to two orders of magnitude over existing CPU baselines and up to 20x efficiency improvements compared to state-of-the-art GPU-based methods.

Nearest neighbor search (NNS) is fundamental for high-dimensional space retrieval and impacts various fields, such as pattern recognition, information retrieval, recommendation systems, and vector database management. Among existing NNS methods, graph-based methods often excel in query accuracy and efficiency. However, these methods face significant challenges, including high construction costs and difficulties with dynamic data updates. Recent efforts have focused on combining graph methods with hashing, quantization, and tree-based approaches to address these issues, but problems with large index sizes and update performance remain unresolved. In response, this paper proposes GTI, a novel, lightweight, and dynamic graph-based tree index for high-dimensional NNS. GTI constructs a tree index built across the entire dataset and employs a lightweight graph index at the level 1 of the tree to significantly reduce graph construction costs. It also features effective data insertion and deletion algorithms that enable logarithmic real-time updates. Additionally, we have developed an effective NNS algorithm for GTI, which not only achieves approximate search performance on par with SOTA graph-based methods but also supports exact NNS. Extensive experiments on six real-world datasets demonstrate that GTI achieves an approximately 10× improvement in update efficiency compared to SOTA tree-based methods, while achieving search effectiveness comparable to SOTA approximate NNS methods. These results underscore the potential of GTI for effective application in dynamic and evolving scenarios.

Similarity search finds similar objects for a given query object based on a certain similarity metric. Similarity search in metric spaces has attracted increasing attention, as the metric space can accommodate any type of data and support flexible distance metrics. However, a metric space only models a single data type with a specific similarity metric. In contrast, a multi-metric space combines multiple metric spaces to simultaneously model a variety of data types and a collection of associated similarity metrics. Thus, a multi-metric space is capable of performing similarity search over any combination of metric spaces. Many studies focus on indexing a single metric space, while only a few aims at indexing multi-metric space to accelerate similarity search. In this paper, we propose DESIRE, an efficient dynamic cluster-based forest index for similarity search in multi-metric spaces. DESIRE first selects high-quality centers to cluster objects into compact regions, and then employs B+-trees to effectively index distances between centers and corresponding objects. To support dynamic scenarios, efficient update strategies are developed. Further, we provide filtering techniques to accelerate similarity queries in multi-metric spaces. Extensive experiments on four real datasets demonstrate the superior efficiency and scalability of our proposed DESIRE compared with the state-of-the-art multi-metric space indexes.

Attributed community search aims to find the community with strong structure and attribute cohesiveness from attributed graphs. However, existing works suffer from two major limitations: (i) it is not easy to set the conditions on query attributes; (ii) the queries support only a single type of attributes. To make up for these deficiencies, in this paper, we study a novel attributed community search called vertex-centric attributed community (VAC) search. Given an attributed graph and a query vertex set, the VAC search returns the community which is densely connected (ensured by the k-truss model) and has the best attribute score. We show that the problem is NP-hard. To answer the VAC search, we develop both exact and approximate algorithms. Specifically, we develop two exact algorithms. One searches the community in a depth-first manner and the other is in a best-first manner. We also propose a set of heuristic strategies to prune the unqualified search space by exploiting the structure and attribute properties. In addition, to further improve the search efficiency, we propose a 2-approximation algorithm. Comprehensive experimental studies on various realworld attributed graphs demonstrate the effectiveness of the proposed model and the efficiency of the developed algorithms.

Ridesharing is popular among travellers because it can reduce their travel costs, and it also holds the potential to reduce travel time, congestion, air pollution, and overall fuel consumption. Existing ridesharing systems (e.g., lyft, uberPOOL) often offer each traveler only one choice that aims to minimize system-wide vehicle travel distance or time. In this demonstration, we present a price-and-time-aware ridesharing system, termed as PTRider, which provides more options. It considers both pick-up time and price, so that travellers are able to choose the vehicle matching their preferences best. To answer the ridesharing request in real time, PTRider builds indexes on the road network and vehicles separately, and utilizes corresponding efficient matching methods. A real-life dataset that contains 432,327 trips extracted from 17,000 Shanghai taxis for one day (May 29, 2009) is used to demonstrate that PTRider can return various options for every ridesharing request in real time.