Shaohua Duan, Pengcheng Huang, Xinze Li, Zhenghao Liu, Xiaoyuan Yi, Yukun Yan, Shuo Wang, Yu Gu, Ge Yu, Maosong Sun. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Yifan Ji, Zhipeng Xu, Zhenghao Liu, Zulong Chen, Qian Zhang, Zhibo Yang, Junyang Lin, Yu Gu, Ge Yu, Maosong Sun. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Diffusion language models (DLMs) have emerged as a powerful non-autoregressive alternative to GPT-style sequential generation, but suffer from substantial computational overhead due to their iterative parallel denoising.Existing acceleration works cannot accurately detect semantically stabilized tokens and then skip computation, leading to sub-optimal speedup in practice.This paper presents the first systematic study of convergence dynamics in DLMs.Innovative observations include the misalignment between traditionally used scalar detection criterion and the semantic convergence, and the post-peak confidence score, that wastes denoising computation and degrades inference quality.To address these limitations, we propose Ada-DLM, a semantic-aware adaptive denoising framework that encodes the trajectory of scalar confidence scores into an evolutionaware feature vector and then clusters vectors proactively to adaptively identify semantically converged tokens.Furthermore, we incorporate system-level optimizations to maximize runtime efficiency.Experiments show that Ada-DLM consistently outperforms the SOTA competitor, achieving up to 2× speedup and 19% quality improvement.That offers a practical path toward efficient high-quality DLM deployment.

Zhenghao Liu, Zhuoyang Wu, Xinze Li, Yukun Yan, Shuo Wang, Zulong Chen, Yu Gu, Ge Yu, Maosong Sun. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

User-item interaction histories are pivotal for sequential recommendation systems but often include noise, such as unintended clicks or actions that fail to reflect genuine user preferences. To address this, we propose Learned Item Shortcuts for Sequential Recommendation (LISRec), a novel framework that explicitly captures stable preferences by extracting personalized semantic shortcuts from historical interactions. LISRec first learns task-agnostic semantic representations to assess item similarities, then constructs a personalized semantic graph over all user-interacted items. By identifying the maximal semantic connectivity subset within this graph, LISRec selects the most representative items as semantic shortcuts to guide user preference modeling. This focused representation filters out irrelevant actions while preserving the diversity of genuine interests. Experimental results on the Yelp and Amazon Product datasets illustrate that LISRec achieves a 13% improvement over baseline recommendation models, showing its effectiveness in capturing stable user interests. Further analysis indicates that shortcut-based histories better capture user preferences, making more accurate and relevant recommendations. All codes and datasets are available at https://github.com/NEUIR/LISRec.

Multimodal Retrieval-Augmented Generation (MRAG) has shown promise in mitigating hallucinations in Multimodal Large Language Models (MLLMs) by incorporating external knowledge. However, existing methods typically adhere to rigid retrieval paradigms by mimicking fixed retrieval trajectories and thus fail to fully exploit the knowledge of different retrieval experts through dynamic interaction based on the model's knowledge needs or evolving reasoning states. To overcome this limitation, we introduce Mixture-of-Retrieval Experts (MoRE), a novel framework that enables MLLMs to collaboratively interact with diverse retrieval experts for more effective knowledge exploitation. Specifically, MoRE learns to dynamically determine which expert to engage with, conditioned on the evolving reasoning state. To effectively train this capability, we propose Stepwise Group Relative Policy Optimization (Step-GRPO), which goes beyond sparse outcome-based supervision by encouraging MLLMs to interact with multiple retrieval experts and synthesize fine-grained rewards, thereby teaching the MLLM to fully coordinate all experts when answering a given query. Experimental results on diverse open-domain QA benchmarks demonstrate the effectiveness of MoRE, achieving average performance gains of over 7% compared to competitive baselines. Notably, MoRE exhibits strong adaptability by dynamically coordinating heterogeneous experts to precisely locate relevant information, validating its capability for robust, reasoning-driven expert collaboration. All codes and data are released on https://github.com/OpenBMB/MoRE.

Transformer-based foundation models are becoming deeper and larger. For fast training, their billions of parameters (tensors) are split onto parallel tasks running on many modern yet expensive accelerators. To amortize the huge hardware investments, it is cost-effective to share the aggregated resources among multi-tenants. However, resource contention yields the heavy straggling problem. Existing works feature contributions for the traditional data parallelism. They cannot work well for the new tensor parallelism, due to the dependency among split tensors. This paper is the first attempt on accelerating heterogeneous tensor parallelism. We summarize specific challenges, including the very frequent synchronizations and the heavy tensor computation workloads. Our solution is to resize dimensions of parameters on demand, to quickly and dynamically balance workloads. The accuracy loss is reduced through priority resizing. We also migrate workloads between tasks, without any loss of accuracy. The most efficient communication primitives are selected and then scheduled in a non-redundant manner, to reduce the runtime latency. Our final hybrid solution is built on top of resizing and migration. By studying the tradeoff between accuracy and efficiency, it can smartly hit the “sweet spot”. Extensive experiments validate the effectiveness of our proposals.

Due to the anonymity and decentralization inherent in blockchains, they have gradually become a new breeding ground for money laundering. Anti-money laundering (AML) in blockchains is urgently needed. A conventional AML method involves analyzing transaction features derived from blockchain records that define money transfers within a transaction network. However, this method often fails to identify all illicit transactions, as some are obscured within the network due to their indistinguishable features compared to both known licit and illicit transactions. Fortunately, all transactions involve at least two addresses (accounts), and the account features of illicit transactions are distinguishable because they reflect the social information of the parties involved. This insight provides a pathway to uncover hidden illicit transactions. In this article, we propose the account enhanced transactions classification ($\mathsf{ATC}$) model to enhance the performance of illicit transaction detection. The$\mathsf{ATC}$expands the dimensionality of transaction feature vectors by concatenating the corresponding accounts, represented as a variable number of high-dimensional feature vectors. In addition,$\mathsf{ATC}$employs clustering, pooling, and persistent homology techniques to address the challenges associated with learning from these dimension-expanded features. Experimental results on the Elliptic++ dataset demonstrate the advantages of$\mathsf{ATC}$with an accuracy of 98.28%, precision of 99.64%, recall of 91.85%, and an F1 score of 95.59%, significantly outperforming other comparative methods.

Biological oscillations are periodic changes in various signaling processes crucial for the proper functioning of living organisms. These oscillations are modeled by ordinary differential equations, with coefficient variations leading to diverse periodic behaviors, typically measured by oscillatory frequencies. This paper explores sampling techniques for neural networks to model the relationship between system coefficients and oscillatory frequency. However, the scarcity of oscillations in the vast coefficient space results in many samples exhibiting non-periodic behaviors, and small coefficient changes near oscillation boundaries can significantly alter oscillatory properties. This leads to non-oscillatory bias and boundary sensitivity, making accurate predictions difficult. While existing importance and uncertainty sampling approaches partially mitigate these challenges, they either fail to resolve the sensitivity problem or result in redundant sampling. To address these limitations, we propose the Hierarchical Gradient-based Genetic Sampling (HGGS) framework, which improves the accuracy of neural network predictions for biological oscillations. The first layer, Gradient-based Filtering, extracts sensitive oscillation boundaries and removes redundant non-oscillatory samples, creating a balanced coarse dataset. The second layer, Multi-grid Genetic Sampling, utilizes residual information to refine these boundaries and explore new high-residual regions, increasing data diversity for model training. Experimental results demonstrate that HGGS outperforms seven comparative sampling methods across four biological systems, highlighting its effectiveness in enhancing sampling and prediction accuracy.

Retrieval-Augmented Generation (RAG) enhances the performance of Large Language Models (LLMs) by incorporating external knowledge.However, LLMs still encounter challenges in effectively utilizing the knowledge from retrieved documents, often being misled by irrelevant or noisy information.To address this issue, we introduce RankCoT, a knowledge refinement method that incorporates reranking signals in generating CoT-based summarization for knowledge refinement based on given query and all retrieval documents.During training, RankCoT prompts the LLM to generate Chain-of-Thought (CoT) candidates based on the query and individual documents.It then fine-tunes the LLM to directly reproduce the best CoT from these candidate outputs based on all retrieved documents, which requires LLM to filter out irrelevant documents during generating CoT-style summarization.Additionally, RankCoT incorporates a self-reflection mechanism that further refines the CoT outputs, resulting in higher-quality training data.Our experiments demonstrate the effectiveness of RankCoT, showing its superior performance over other knowledge refinement models.Further analysis reveals that RankCoT can provide shorter but effective refinement results, enabling the generator to produce more accurate answers.All code and data are available at https://github.com/NEUIR/RankCoT.

Hypergraph Neural Networks (HGNNs) build on Graph Neural Networks (GNNs) by using hyperedges to capture complex, high-order relationships in data. However, training HGNNs on large hypergraphs is limited by computational and memory bottlenecks on a single machine. To overcome this, we propose LCHGNN, a distributed training method based on a new data structure called the communication graph, which simplifies hypergraph communication by representing cut hyperedges as vertices for structured message passing. LCHGNN employs a vertex-centric, hyperedge-replication-based storage scheme and introduces specialized forward and backward propagation mechanisms tailored for distributed execution. To mitigate communication overhead, We propose a lightweight optimization strategy that employs full synchronization in the initial round, followed by lightweight synchronization in subsequent rounds. Additionally, we present a learnable semi-supervised synchronization (LSS) aggregation mechanism for adaptive hyperedge selection. Extensive experiments on benchmark datasets demonstrate that LCHGNN preserves training accuracy while substantially reducing communication costs and enhancing scalability. This work addresses a critical gap in distributed HGNN research by delivering a communication-efficient and scalable training method, thereby facilitating the application of hypergraph learning to large-scale problems.

Large language models (LLMs) have demonstrated significant potential in enhancing dense retrieval through query augmentation.However, most existing methods treat the LLM and the retriever as separate modules, overlooking the alignment between generation and ranking objectives.In this work, we propose Ex-pandR, a unified LLM-augmented dense retrieval framework that jointly optimizes both the LLM and the retriever.ExpandR employs the LLM to generate semantically rich query expansions, which are leveraged to enhance the retriever's training.Simultaneously, the LLM is trained using Direct Preference Optimization (DPO), guided by a carefully designed reward function that balances retrieval effectiveness and generation consistency.This joint optimization paradigm enables mutual adaptation between the LLM and the retriever, resulting in query expansions that are both informative and well-suited for retrieval.Experimental results on multiple benchmarks show that Ex-pandR consistently outperforms strong baselines, achieving more than a 5% improvement in retrieval performance.

Multi-modal Knowledge Graph Completion (MMKGC) aims to predict missing entities, relations, or attributes in knowledge graphs by collaboratively modeling the triple structure and multimodal information (e.g., text, images, videos) associated with entities. This approach facilitates the automatic discovery of previously unobserved factual knowledge. However, existing MMKGC methods encounter several critical challenges: (i) the imbalance of inter-entity information across different modalities; (ii) the heterogeneity of intra-entity multimodal information; and (iii) for a given entity, the informational contributions of different modalities are inconsistent across contexts. In this paper, we propose a novel **L**arge model-driven **B**alanced **M**ultimodal **K**nowledge **G**raph **C**ompletion framework, termed LBMKGC. Subsequently, to bridge the semantic gap between heterogeneous modalities, LBMKGC aligns the multimodal embeddings of entities semantically by using the CLIP (Contrastive Language-Image Pre-Training) model. Furthermore, LBMKGC adaptively fuses multimodal embeddings with relational guidance by distinguishing between the perceptual and conceptual attributes of triples. Finally, extensive experiments conducted against 21 state-of-the-art baselines demonstrate that LBMKGC achieves superior performance across diverse datasets and scenarios while maintaining efficiency and generalizability. Our code and data are publicly available at: https://github.com/guoynow/LBMKGC.

Intellectual Property (IP) management involves strategically protecting and utilizing intellectual assets to enhance organizational innovation, competitiveness, and value creation. Patent matching is a crucial task in intellectual property management, which facilitates the organization and utilization of patents. Existing models often rely on the emergent capabilities of Large Language Models (LLMs) and leverage them to identify related patents directly. However, these methods usually depend on matching keywords and overlook the hierarchical classification and categorical relationships of patents. In this paper, we propose MemGraph, a method that augments the patent matching capabilities of LLMs by incorporating a memory graph derived from their parametric memory. Specifically, MemGraph prompts LLMs to traverse their memory to identify relevant entities within patents, followed by attributing these entities to corresponding ontologies. After traversing the memory graph, we utilize extracted entities and ontologies to improve the capability of LLM in comprehending the semantics of patents. Experimental results on the PatentMatch dataset demonstrate the effectiveness of MemGraph, achieving a 17.68% performance improvement over baseline LLMs. The further analysis highlights the generalization ability of MemGraph across various LLMs, both in-domain and out-of-domain, and its capacity to enhance the internal reasoning processes of LLMs during patent matching. All data and codes are available at https://github.com/NEUIR/MemGraph.

Dynamic Graph Neural Networks (DGNNs) are effective at capturing multidimensional data and enable many important applications. As model training is computationally intensive, distributed DGNN training is employed to accommodate large data. Also, when training DGNNs, so-called sliding window training is used predominantly, as it enhances both accuracy and efficiency. However, current distributed frameworks-such as snapshot partitioning, chunk-based partitioning, and L -hop cache-based communication-free vertex partitioning-are inherently incompatible with sliding window training. While communication-based vertex partitioning supports sliding window training, its design for static graphs limits the effectiveness in distributed DGNN training. Specifically, existing partitioning strategies fail to optimize communication across snapshots, while existing cache reuse and communication scheduling strategies ignore opportunities for optimization between sliding windows. To support distributed sliding window training, we present SWASH, a scalable and flexible communication framework that utilizes a S liding W indow-based c A che SH aring technique. Specifically, we propose a flexible communication framework that supports ratio adjustment and timing selection, as well as hyperparameter settings and adaptive scheduling. We also propose a lightweight partitioning strategy tailored to sliding window-based DGNN training to reduce both partitioning and communication overheads. Finally, to alleviate decreases in accuracy due to reduced communication, we propose a cache-sharing technique based on sliding windows for sharing boundary vertex embeddings. Comprehensive experiments show that SWASH is capable of training speedups of an average of 9.44× over state-of-the-art frameworks while maintaining the accuracy of fully communicating, non-caching training frameworks.

Graph neural networks (GNNs) have emerged as a promising method for learning from graph data, but large-scale GNN training requires extensive memory and computation resources. To address this, researchers have proposed using multi-GPU processing, which partitions graph data across GPUs for parallel training. However, vertex dependencies in multi-GPU GNN training lead to significant neighbor replications across GPUs, increasing memory consumption. The substantial intermediate data generated during training further exacerbates this issue. Neighbor replication and intermediate data constitute the primary memory consumption in GNN training (i.e., typically accounting for over 80%). In this work, we propose GNN task parallelism for multi-GPU GNN training, which reduces neighbor replication by partitioning training tasks in each layer across different GPUs rather than partitioning the graph structure. This approach only partitions the graph data within individual GPUs, reducing the memory requirements of single tasks while overlapping subgraph computation across different GPUs. Shared neighbor embeddings among different subgraphs can be efficiently reused within a single GPU. Additionally, we employ a task-decoupled GNN training framework, which decouples different training tasks to manage their associated intermediate data independently and release it as early as possible to reduce memory usage. By integrating these techniques, we propose a multi-GPU GNN training system, NeutronTask. Experimental results on a 4×A5000 GPU server show that NeutronTask effectively supports billion-scale full-graph GNN training. For small graphs where the training data fits into the GPUs, NeutronTask achieves 1.27× - 5.47× speedup compared to state-of-the-art GNN systems including NeutronStar and Sancus.

Multiplex Graph Contrastive Learning (MGCL) has attracted significant attention. However, existing MGCL methods often struggle with suboptimal graph structures and fail to fully capture intricate interdependencies across multiplex views. To address these issues, we propose a novel self-supervised framework, Multiplex Graph Refinement with progressive fusion (MGRefine), for multiplex graph contrastive representation learning. Specifically, MGRefine introduces a multi-view learning module to extract a structural guidance matrix by exploring the underlying relationships between nodes. Then, a progressive fusion module is employed to progressively enhance and fuse representations from different views, capturing and leveraging nuanced interdependencies and comprehensive information across the multiplex graphs. The fused representation is then used to construct a consensus guidance matrix. A self-enhanced refinement module continuously refines the multiplex graphs using these guidance matrices while providing effective supervision signals. MGRefine achieves mutual reinforcement between graph structures and representations, ensuring continuous optimization of the model throughout the learning process in a self-enhanced manner. Extensive experiments demonstrate that MGRefine outperforms state-of-the-art methods and also verify the effectiveness of MGRefine across various downstream tasks on several benchmark datasets.

Fact verification tasks aim to identify the integrity of textual contents according to the truthful corpus. Existing fact verification models usually build a fully connected reasoning graph, which regards claim-evidence pairs as nodes and connects them with edges. They employ the graph to propagate the semantics of the nodes. Nevertheless, the noisy nodes usually propagate their semantics via the edges of the reasoning graph, which misleads the semantic representations of other nodes and amplifies the noise signals. To mitigate the propagation of noisy semantic information, we introduce a Confidential Graph Attention Network (CO-GAT), which proposes a node masking mechanism for modeling the nodes. Specifically, CO-GAT calculates the node confidence score by estimating the relevance between the claim and evidence pieces. Then, the node masking mechanism uses the node confidence scores to control the noise information flow from the vanilla node to the other graph nodes. CO-GAT achieves a 73.59% FEVER score on the FEVER dataset and shows the generalization ability by broadening the effectiveness to the science-specific domain.

The range search in Hamming space is to explore the binary vectors whose Hamming distances with a query vector are within a given searching threshold. It arises as the core component of many applications, such as image retrieval, pattern recognition, and machine learning. Existing searching methods in Hamming space require much pre-processing overhead, which are not suitable for processing multiple batches of incoming data in a short time. Moreover, significant pre-processing overhead can be a burden when the number of queries is relatively small. In this paper, we propose a query-aware method for the approximate range search in Hamming space with no pre-process. Specifically, to eliminate the impact of data skewness, we introduce JS-divergence to measure the divergence between data's distribution and query's distribution, and specially design a Query-Aware Dimension Partitioning (QADP) strategy to partition the dimensions into several subspaces according to the scales of given searching thresholds. In the subspaces, the candidates can be efficiently obtained by the basic Pigeonhole Principle and our proposed Anti-Pigeonhole Principle. Furthermore, a sampling strategy is designed to estimate the Hamming distance between the query vector and arbitrary binary vector to obtain the final approximate searching results among the candidates. Experimental results on four real-world datasets illustrate that, in comparison with benchmark methods, our method possesses the superior advantages on searching accuracy and efficiency. The proposed method can increase the searching efficiency up to nearly 16 times with high searching accuracy.

Graph partitioning as a classic NP-complete problem, is the most fundamental procedure that needs to be performed before parallel computations. Partitioners can be divided into vertex- and edge-based approaches. Recently, both approaches are employing a streaming heuristic to find approximate solutions. It is lightweight in space and time complexities, but suffers from suboptimal partitioning quality, especially for directed graphs where the explicit knowledge provided for heuristic is limited. This paper thereby proposes new heuristics for not only vertex-based but also edge-based partitioning. They improve quality by additionally utilizing implicit knowledge, which is embedded in the local streaming view and the global graph view. Memory reduction techniques are presented to extract this knowledge with negligible space costs. That preserves the lightweight advantages of streaming partitioning. Besides, we study parallel acceleration and restreaming, to further boost the partitioning efficiency and quality. Extensive experiments validate that our proposals outperform the state-of-the-art competitors.

In recent years, blockchain anonymity has led to more illicit accounts participating in various money laundering transactions. Existing studies typically detect money laundering transactions, known as AML (Anti-money Laundering), through learning transaction features on transaction graphs of transactional blockchains. However, transaction graphs fail to represent the accounts’ social features within transactional organizations. Account graphs reveal such features well, and detecting illicit accounts on account graphs provides a new perspective on AML. For example, it helps uncover illegal transactions whose transaction features are not distinct in transaction graphs, with a loose assumption that illicit accounts are likely involved in illegal transactions. In this paper, we propose a Social Attention Graph Neural Network ($\textsf {SGNN}$) on account graphs converted from transaction graphs. To detect illicit accounts,$\textsf {SGNN}$learns the social features on two sub-graphs, a heterogeneous graph and a hypergraph, extracted from the account graph, and fuses these features into account attribute vectors through attention. The experimental results on the Elliptic++ dataset demonstrate$\textsf {SGNN}$’s advances. It outperforms the best baseline by 14.18% in precision, 7.37% in F1 score, 0.96% in accuracy, and 0.64% in recall when detecting illicit accounts on account graphs, as well as detects 20.3% more recall of illegal transactions through these illicit accounts than state-of-the-art methods based on transaction graphs when the mappings between illegal transactions and illicit accounts are provided. Moreover, thanks to social features,$\textsf {SGNN}$has a novel capability that works under many account scales and activity degrees. We release our code onhttps://github.com/CloudLab-NEU/SGNN.

Data privacy protection legislation around the world has increasingly enforced the “right to be forgotten” regulation, generating a surge in research interest in machine unlearning (MU), which aims to remove the impact of training data from machine learning models upon receiving revocation requests from data owners. There exist two major challenges for the performance of MU: the execution efficiency and the inference interference. The former requires minimizing the computational overhead for each execution of the MU mechanism, while the latter calls for reducing the execution frequency to minimize interference with normal inference services. Nowadays most MU studies focus on the sample-level unlearning setting, leaving the other paramount feature-level setting under-explored. Adapting these existing techniques to the latter turns out to be non-trivial. The only known feature-level work achieves anapproximateunlearning guarantee, but suffers from degraded model accuracy and still leaves the inference interference challenge unsolved. We are therefore motivated to propose FELEMN, the first FEature-Level Exact Machine uNlearning method that overcomes both of the above-mentioned hurdles. For the MU execution efficiency challenge, we explore the impact of different feature partitioning strategies on the preservation of semantic relationships for maintaining model accuracy and MU efficiency. For the inference interference challenge, we propose two batching mechanisms to combine as many individual unlearning requests to be processed together as possible, while avoiding potential privacy issues coming with falsely postponing unlearning requests, which is grounded on theoretical analysis. Experiments on five real datasets show that our FELEMN outperforms up-to-date competitors with up to$3\times$speedup for each MU execution, and 50% runtime reduction by mitigating inference interference.

Pretrained language models have shown strong effectiveness in code-related tasks, such as code retrieval, code generation, code summarization, and code completion tasks. In this article, we propose COde assistaNt viA retrieval-augmeNted language model (CONAN), which aims to build a code assistant by mimicking the knowledge-seeking behaviors of humans during coding. Specifically, it consists of a code structure-aware retriever (CONAN-R) and a dual-view code representation-based retrieval-augmented generation model (CONAN-G). CONAN-R pretrains CodeT5 using Code-Documentation Alignment and Masked Entity Prediction tasks to make language models code structure-aware and learn effective representations for code snippets and documentation. Then CONAN-G designs a dual-view code representation mechanism for implementing a retrieval-augmented code generation model. CONAN-G regards the code documentation descriptions as prompts, which help language models better understand the code semantics. Our experiments show that CONAN achieves convincing performance on different code generation tasks and significantly outperforms previous retrieval augmented code generation models. Our further analyses show that CONAN learns tailored representations for both code snippets and documentation by aligning code-documentation data pairs and capturing structural semantics by masking and predicting entities in the code data. Additionally, the retrieved code snippets and documentation provide necessary information from both program language and natural language to assist the code generation process. CONAN can also be used as an assistant for Large Language Models (LLMs), providing LLMs with external knowledge in shorter code document lengths to improve their effectiveness on various code tasks. It shows the ability of CONAN to extract necessary information and help filter out the noise from retrieved code documents.

Tianshuo Zhou, Sen Mei, Xinze Li, Zhenghao Liu, Chenyan Xiong, Zhiyuan Liu, Yu Gu, Ge Yu. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Label-constrained reachability (LCR) has been ex-tensively studied. However, these studies have neglected two aspects: the label sequence and time-dependent properties. When processing reachability queries, not only label presence but also label sequence and time-dependent properties should be considered. Various real-world scenarios, including vehicular networks, computing networks, and biological networks, require such queries. In this paper, we present a formal definition of time-dependent label-constrained reachability (TDLCR) queries based on LCR. These queries require both label sequence and time-dependent constraints to be considered, thus introducing a higher level of complexity. To address this challenge, we propose two indexing algorithms that are optimized for the label constraint: OneL and TD2H. OneL builds a single-label index for each vertex and provides a baseline for solving the TDLCR problem. TD2H is based on classical 2-hop index with excellent query efficiency, while innovative pruning rules and vertex order strategies are proposed to reduce indexing overhead. To further balance indexing overhead and query efficiency and to optimize the time-dependent constraint, we introduce a BII algorithm. It effectively improves index construction efficiency by building only a local index instead of a global one. Finally, experiments on many real datasets demonstrate that although the BII has a slightly inferior query time to TD2H, it has a significant advantage in the index construction.

Recently, learned indexes are assisting and are being adopted to replace traditional indexes for their low memory usage and high query performance. However, existing learned indexes suffer in query efficiency when dealing with locally skewed data distributions which may be caused or exacerbated by ubiquitous updates. Frequent model retraining and reconstruction is required under this circumstance. To address this issue, we present Chameleon, an adaptive learned index for locally skewed data especially in the context of frequent updates. We propose a metric for measuring local skewness, based on which we employ Multi-Agent Reinforcement Learning to assist in locating locally skewed regions and optimizing index structures. Additionally, to reduce the blocking time caused by index model retraining, we propose a lightweight lock named the Interval Lock to achieve a non-blocking retraining. Extensive experiments demonstrate that, without costing more memory, Chameleon outperforms the state-of-the-art learned indexes by up to 3.75 x and 4.37 x in lookup times for read-only and mixed workloads, respectively, and it accelerates update processing by up to 2.92 x.

GPUs are being applied widely to batch workloads that benefit from the parallel processing capabilities of GPUs. To enable the processing of concurrent batch-based transactions on GPUs, existing systems build dependency graphs during a pre-execution phase to manage read and write operations. However, as dependency-graph maintenance introduces a sub-stantial overhead, there is a need for more efficient transaction support to exploit the power of GPUs more fully for transaction processing. This paper proposes LTPG, a novel GPU-enabled database system that offers increased versatility and efficiency by eliminating the need for predefined read/write-sets. LTPG employs deterministic optimistic concurrency control to ensure correct transaction execution, thus avoiding the maintenance of dependency graphs. The proposed concurrency control simpli-fies transaction processing workflows and avoids the overhead associated with managing dependency graphs, thus resulting in improved efficiency. LTPG divides a workflow into three stages: execution, conflict detection, and write-back, leveraging the parallelism of GPUs. Moreover, several additional optimization strategies are adopted to improve system performance. Experiments with real-world workloads from two benchmarks verify LTPG can achieve effective improvement in the throughput and latency compared to the leading baselines.

Graph Neural Networks (GNNs) have shown exceptional performance across a wide range of applications. Current frameworks leverage CPU-GPU heterogeneous environments for GNN model training, incorporating mini-batch and sampling techniques to mitigate GPU memory constraints. In such settings, sample-based GNN training can be divided into three phases: sampling, gathering, and training. Existing GNN systems deploy various task orchestration methods to execute each phase on either the CPU or GPU. However, through comprehensive experimentation and analysis, we observe that these task orchestration approaches do not optimally exploit the available heterogeneous resources, hindered by either inefficient CPU processing or GPU resource bottlenecks. In this paper, we propose NeutronOrch, a system for sample-based GNN training that ensures balanced utilization of the CPU and GPU. NeutronOrch decouples the training process by layer and pushes down the training task of the bottom layer to the CPU. This significantly reduces the computational load and memory footprint of GPU training. To avoid inefficient CPU processing, NeutronOrch only offloads the training of frequently accessed vertices to the CPU and lets GPU reuse their embeddings with bounded staleness. Furthermore, NeutronOrch provides a fine-grained pipeline design for the layer-based task orchestrating method. The experimental results show that compared with the state-of-the-art GNN systems, NeutronOrch can achieve up to 11.51× performance speedup.

Graph neural networks (GNNs) have emerged as a promising direction. Training large-scale graphs that relies on distributed computing power poses new challenges. Existing distributed GNN systems leverage data parallelism by partitioning the input graph and distributing it to multiple workers. However, due to the irregular nature of the graph structure, existing distributed approaches suffer from unbalanced workloads and high overhead in managing cross-worker vertex dependencies. In this paper, we leverage tensor parallelism for distributed GNN training. GNN tensor parallelism eliminates cross-worker vertex dependencies by partitioning features instead of graph structures. Different workers are assigned training tasks on different feature slices with the same dimensional size, leading to a complete load balance. We achieve efficient GNN tensor parallelism through two critical functions. Firstly, we employ a generalized decoupled training framework to decouple NN operations from graph aggregation operations, significantly reducing the communication overhead caused by NN operations which must be computed using complete features. Secondly, we employ a memory-efficient task scheduling strategy to support the training of large graphs exceeding single GPU memory, while further improving performance by overlapping communication and computation. By integrating the above techniques, we propose a distributed GNN training system NeutronTP. Our experimental results on a 16-node Aliyun cluster demonstrate that NeutronTP achieves 1.29×-8.72× speedup over state-of-the-art GNN systems including DistDGL, NeutronStar, and Sancus.

As large volumes of trajectory data accumulate, simplifying trajectories to reduce storage and querying costs is increasingly studied. Existing proposals face three main problems. First, they require numerous iterations to decide which GPS points to delete. Second, they focus only on the relationships between neighboring points (local information) while neglecting the overall structure (global information), reducing the global similarity between the simplified and original trajectories and making it difficult to maintain consistency in query results, especially for similarity-based queries. Finally, they fail to differentiate the importance of points with similar features, leading to suboptimal selection of points to retain the original trajectory information. We propose MLSimp, a novel Mutual Learning query-driven trajectory simplification framework that integrates two distinct models: GNN-TS, based on graph neural networks, and Diff-TS, based on diffusion models. GNN-TS evaluates the importance of a point according to its globality, capturing its correlation with the entire trajectory, and its uniqueness, capturing its differences from neighboring points. It also incorporates attention mechanisms in the GNN layers, enabling simultaneous data integration from all points within the same trajectory and refining representations, thus avoiding iterative processes. Diff-TS generates amplified signals to enable the retention of the most important points at low compression rates. Experiments involving eight baselines on three databases show that MLSimp reduces the simplification time by 42%--70% and improves query accuracy over simplified trajectories by up to 34.6%.

Dynamic Graph Neural Networks (DGNNs) have demonstrated exceptional performance at dynamic-graph analysis tasks. However, the costs exceed those incurred by other learning tasks, to the point where deployment on large-scale dynamic graphs is infeasible. Existing distributed frameworks that facilitate DGNN training are in their early stages and experience challenges such as communication bottlenecks, imbalanced workloads, and GPU memory overflow. We introduce DynaHB, a distributed framework for DGNN training using so-called Hybrid Batches. DynaHB reduces communication by means of vertex caching, and it ensures even data and workload distribution by means of load-aware vertex partitioning. DyanHB also features a novel hybrid-batch training mode that combines vertex-batch and snapshot-batch techniques, thereby reducing training time and GPU memory usage. Next, to further enhance the hybrid batch based approach, DynaHB integrates a reinforcement learning-based batch adjuster and a pipelined batch generator with a batch reservoir to reduce the cost of generating hybrid batches. Extensive experiments show that DynaHB is capable of up to a 93× and an average of 8.06× speedups over the state-of-the-art training framework.

Many Graph Neural Network (GNN) training systems have emerged recently to support efficient GNN training. Since GNNs embody complex data dependencies between training samples, the training of GNNs should address distinct challenges different from DNN training in data management, such as data partitioning, batch preparation for mini-batch training, and data transferring between CPUs and GPUs. These factors, which take up a large proportion of training time, make data management in GNN training more significant. This paper reviews GNN training from a data management perspective and provides a comprehensive analysis and evaluation of the representative approaches. We conduct extensive experiments on various benchmark datasets and show many interesting and valuable results. We also provide some practical tips learned from these experiments, which are helpful for designing GNN training systems in the future.

Hypergraphs can model higher-order relationships among data objects that are found in applications such as social networks and bioinformatics. However, recent studies on hypergraph learning that extend graph convolutional networks to hypergraphs cannot learn effectively from features of unlabeled data. To such learning, we propose a contrastive hypergraph neural network, CHGNN, that exploits self-supervised contrastive learning techniques to learn from labeled and unlabeled data. First, CHGNN includes an adaptive hypergraph view generator that adopts an auto-augmentation strategy and learns a perturbed probability distribution of minimal sufficient views. Second, CHGNN encompasses an improved hypergraph encoder that considers hyperedge homogeneity to fuse information effectively. Third, CHGNN is equipped with a joint loss function that combines a similarity loss for the view generator, a node classification loss, and a hyperedge homogeneity loss to inject supervision signals. It also includes basic and cross-validation contrastive losses, associated with an enhanced contrastive loss training process. Experimental results on nine real datasets offer insight into the effectiveness of CHGNN, showing that it outperforms 19 competitors in terms of classification accuracy consistently.

This paper proposes Text mAtching based SequenTial rEcommenda-tion model (TASTE), which maps items and users in an embedding space and recommends items by matching their text representations. TASTE verbalizes items and user-item interactions using identifiers and attributes of items. To better characterize user behaviors, TASTE additionally proposes an attention sparsity method, which enables TASTE to model longer user-item interactions by reducing the self-attention computations during encoding. Our experiments show that TASTE outperforms the state-of-the-art methods on widely used sequential recommendation datasets. TASTE alleviates the cold start problem by representing long-tail items using full-text modeling and bringing the benefits of pretrained language models to recommendation systems. Our further analyses illustrate that TASTE significantly improves the recommendation accuracy by reducing the popularity bias of previous item id based recommendation models and returning more appropriate and text-relevant items to satisfy users. All codes are available at https://github.com/OpenMatch/TASTE.

Data partitioning is the most fundamental procedure before parallelizing complex analysis on very big graphs. As a classical NP-complete problem, graph partitioning usually employs offline or online/streaming heuristics to find approximately optimal solutions. However, they are either heavyweight in space and time overheads or suboptimal in quality measured by workload balance and the number of cutting edges across partitions, both of which cannot scale well with the ever-growing demands of quickly analyzing big graphs. This paper thereby proposes a new vertex partitioner for better scalability. It preserves the lightweight advantage of existing streaming heuristics, and more importantly, fully utilizes the knowledge embedded in the local view when streaming a vertex, which significantly improves the quality. We present a sliding window technique to compensate for the additional memory costs caused by knowledge utilization. Also, a parallel technique with dependency detection optimization is designed to further enhance efficiency. Experiments on a spread of real-world datasets validate that our proposals can achieve overall success in terms of partitioning quality, memory consumption, and runtime efficiency.

Bregman distances (also known as Bregman divergences) are widely used in machine learning, speech recognition and signal processing, and kNN searches with Bregman distances have become increasingly important with the rapid advances of multimedia applications. Data in multimedia applications such as images and videos are commonly transformed into space of hundreds of dimensions. Such high-dimensional space has posed significant challenges for existing kNN search algorithms with Bregman distances, which could only handle data of medium dimensionality (typically less than 100). This paper addresses the urgent problem of high-dimensional kNN search with Bregman distances. We propose a novel partition-filter-refinement framework. Specifically, we propose an optimized dimensionality partitioning scheme to solve several non-trivial issues. First, an effective bound from each partitioned subspace to obtain exact kNN results is derived. Second, we conduct an in-depth analysis of the optimized number of partitions and devise an effective strategy for partitioning. Third, we design an efficient integrated index structure for all the subspaces together to accelerate the search processing. Moreover, we extend our exact solution to an approximate version by a trade-off between the accuracy and efficiency. Experimental results on four real-world datasets and two synthetic datasets show the clear advantage of our method in comparison to state-of-the-art algorithms.

Local differential privacy (LDP) has been established as a strong privacy standard for collecting sensitive information from users. Although it has attracted much research attention in recent years, the majority of existing works focus on applying LDP to frequency distribution estimation for each individual value in a discrete domain. This paper concerns the important range queries involving multiple discrete values. Till now, only a few works target this problem. They all rely on the B-ary tree to construct a uniform and hierarchical decomposition, so as to decrease the error when answering large range queries. However, the uniform splitting manner ignores the properties of decomposed sub-domains and processes them equally without preferences, which leads to significant performance penalty.In this paper, we tackle the problem head on: our proposal, privNUD, is a novel domain hierarchical decomposition mechanism. It dynamically decomposes each domain with a tailored granularity into some sub-domains, which sensitively considers the potential chances to answer one range query. The issue of granularity is carefully analyzed for better performance. It also can smartly prune the sub-domains with small frequencies. Besides, an adaptive user allocation technique is designed to dynamically decide the scale of users that are involved in each sub-domain’s frequency estimation. Extensive experiments using real and synthetic datasets demonstrate that privNUD achieves significantly higher result accuracy compared to the up-to-date solutions.

Train transfer plan ranking has become the core business of online travel platforms (OTPs), due to the flourish development of high- speed rail technology and convenience of booking trains online. Currently, mainstream OTPs adopt rule-based or simple preference- based strategies to rank train transfer plans. However, the insuf- ficient emphasis on the costs of plans and the negligence of con- sidering reference transfer plans make these existing strategies less effective in solving the personalized ranking problem of train transfer plans. To this end, a novel personalized deep network (Plan- Ranker) is presented in this paper to better address the problem. In PlanRanker, a personalized learning component is first proposed to capture both of the query semantics and the target transfer plan- relevant personalized interests of a user over the user's behavior log data. Then, we present a cost learning component, where both of the price cost and the time cost of a target transfer plan are emphasized and learned. Finally, a reference transfer plan learning component is designed to enable the whole framework of PlanRanker to learn from reference transfer plans which are pieced together by plat- form users and thus reflect the wisdom of crowd. PlanRanker is now successfully deployed at Alibaba Fliggy, one of the largest OTPs in China, serving millions of users every day for train ticket reservation. Offline experiments on two production datasets and a country-scale online A/B test at Fliggy both demonstrate the superiority of the proposed PlanRanker over baselines.

The graph kernel of the functional brain network is an effective method in the field of neuropsychiatric disease diagnosis like Alzheimer's Disease (AD). The traditional static brain networks cannot reflect dynamic changes of brain activities, but evolving brain networks, which are a series of brain networks over time, are able to seize such dynamic changes. As far as we know, the graph kernel method is effective for calculating the differences among networks. Therefore, it has a great potential to understand the dynamic changes of evolving brain networks, which are a series of chronological differences. However, if the conventional graph kernel methods which are built for static networks are applied directly to evolving networks, the evolving information will be lost and accurate diagnostic results will be far from reach. We propose an effective method, called Global Matching based Graph Kernels (GM-GK), which captures dynamic changes of evolving brain networks and significantly improves classification accuracy. At the same time, in order to reflect the natural properties of the brain activity of the evolving brain network neglected by the GM-GK method, we also propose a Local Matching based Graph Kernel (LM-GK), which allows the order of the evolving brain network to be locally fine-tuned. Finally, the experiments are conducted on real data sets and the results show that the proposed methods can significantly improve the neuropsychiatric disease diagnostic accuracy.

Distributed computing is promising to enable large-scale graph neural network (GNN) model training. However, care is needed to avoid excessive computational and communication overheads. Sampling is promising in terms of enabling scalability, and sampling techniques have been proposed to reduce training costs. However, online sampling introduces large overheads, and while offline sampling that is done only once can eliminate such overheads, it instead introduces information loss and accuracy degradation. Thus, existing sampling techniques are unable to improve simultaneously both efficiency and accuracy, particularly at low sampling rates. We develop a distributed system, ADGNN, for full-batch based GNN training that adopts a hybrid sampling architecture to enable a trade-off between efficiency and accuracy. Specifically, ADGNN employs sampling result reuse techniques to reduce the cost associated with sampling and thus improve training efficiency. To alleviate accuracy degradation, we introduce a new metric,Aggregation Difference (AD), that quantifies the gap between sampled and full neighbor set aggregation. We present so-called AD-Sampling that aims to minimize the Aggregation Difference with an adaptive sampling frequency tuner. Finally, ADGNN employs anAD -importance-based sampling technique for remote neighbors to further reduce communication costs. Experiments on five real datasets show that ADGNN is able to outperform the state-of-the-art by up to nearly 9 times in terms of efficiency, while achieving comparable accuracy to the non-sampling methods.

Existing Graph Neural Network (GNN) training frameworks have been designed to help developers easily create performant GNN implementations. However, most existing GNN frameworks assume that the input graphs are static, but ignore that most real-world graphs are constantly evolving. Though many dynamic GNN models have emerged to learn from evolving graphs, the training process of these dynamic GNNs is dramatically different from traditional GNNs in that it captures both the spatial and temporal dependencies of graph updates. This poses new challenges for designing dynamic GNN training frameworks. First, the traditional batched training method fails to capture real-time structural evolution information. Second, the time-dependent nature makes parallel training hard to design. Third, it lacks system supports for users to efficiently implement dynamic GNNs. In this paper, we present NeutronStream, a framework for training dynamic GNN models. NeutronStream abstracts the input dynamic graph into a chronologically updated stream of events and processes the stream with an optimized sliding window to incrementally capture the spatial-temporal dependencies of events. Furthermore, NeutronStream provides a parallel execution engine to tackle the sequential event processing challenge to achieve high performance. NeutronStream also integrates a built-in graph storage structure that supports dynamic updates and provides a set of easy-to-use APIs that allow users to express their dynamic GNNs. Our experimental results demonstrate that, compared to state-of-the-art dynamic GNN implementations, NeutronStream achieves speedups ranging from 1.48X to 5.87X and an average accuracy improvement of 3.97%.

Modern data centers exist as infrastructure in the era of Big Data. Big data processing applications are the major computing workload of data centers. Electricity cost accounts for about 50% of data centers’ operational costs. Therefore, the energy consumed for running distributed data processing algorithms on a data center is starting to attract both academia and industry. Most works study the energy consumption from the hardware perspective and only a few of them from the algorithm perspective. A general and hardware-independent energy evaluation model for the algorithms is in demand. With the model, algorithm designers can evaluate the energy consumption, compare energy consumption features and facilitate energy consumption optimization of distributed data processing algorithms. Inspired by the time complexity model, we propose an energy complexity model for describing the trends that an algorithm's energy consumption grows with the algorithm's input size. We argue that a good algorithm, especially for processing Big Data, should have a ‘small’ energy complexity. We define$E(n)$to represent the functional relationship that associates an algorithm's input size$n$with its notional energy consumption$E$. Based on the well-known abstract Bulk Synchronous Parallel (BSP) computer and programming model, we present a complete$E(n)$solution, including abstraction, generalization, quantification, derivation, comparison, analysis, examples, verification, and applications. Comprehensive experimental analysis shows that the proposed energy complexity model is practical, interestingly, and not equivalent to time complexity.

Hypergraphs consist of vertices and hyperedges that can connect multiple vertices. Since hypergraphs can effectively simulate complex intergroup relationships between entities, they have a wide range of applications such as computer vision and bioinformatics. In this paper, we study the subhypergraph matching problem, which is one of the most challenging problems in the processing of the hypergraphs. We aim to extract all subhypergraph isomorphism embeddings of a query hypergraph q in a large data hypergraph D. The existing methods on subgraph matching are designed for the ordinary graphs, which typically achieve the goal by three phases, i.e., filtering candidate vertex sets, refining candidates, and then enumeration final results in some matching order. However, such a design cannot be trivially extended to efficiently handle hypergraphs due to the inherent difference between ordinary graphs and hypergraphs. This motivates us to enhance the performance by exploiting hyperedge features, such as the typical intersections and inclusion relations between hyperedges.

Myriad of machine learning (ML) algorithms refine model parameters iteratively. Existing synchronous data-parallel frameworks can accelerate training with convergence guarantees. However, the pre-assigned workload-based synchronous design still poses great challenges, since fast workers must wait for slow, straggling ones, especially in a heterogeneous computing cluster. Asynchronous alternatives can bypass this performance bottleneck, but at expense of potentially losing convergence guarantees. This article proposes a new time-based flexible synchronous parallel framework (FSP). It provides strict convergence analysis by consistently updating parameters, as well as significant cost reduction by completely unleashing the power of fast workers. It identifies the optimal synchronization frequency, by online balancing costs of parameters’ update and benefits brought by their freshness. Besides the basic goal of keeping all workers fully CPU-utilized, FSP also aims to keep data spread over the cluster fully utilized, so that they can contribute to convergence with equal opportunities. These proposals are all implemented in a prototype system Flegel, with additional engineering optimizations for further performance enhancement and programming facilitation. Experiments demonstrate that Flegel significantly outperforms recent studies.

Skyline computation is an essential database operation that has many applications in multi-criteria decision making scenarios such as recommender systems. Existing algorithms have focused on checking point domination, which lack efficiency over large datasets. We propose a grid-based structure that enables grid cell domination checks. We show that only a small constant number of cells need to be checked which is independent from the number of data points. Our structure also enables parallel processing. We thus obtain a highly efficient parallel skyline algorithm named SkyCell, taking advantage of the parallelization power of graphics processing units. Experimental results confirm the effectiveness and efficiency of SkyCell -- it outperforms state-of-the-art algorithms consistently and by up to over two orders of magnitude in the computation time.

Dense retrievers encode queries and documents and map them in an embedding space using pre-trained language models.These embeddings need to be high-dimensional to fit training signals and guarantee the retrieval effectiveness of dense retrievers.However, these highdimensional embeddings lead to larger index storage and higher retrieval latency.To reduce the embedding dimensions of dense retrieval, this paper proposes a Conditional Autoencoder (ConAE) to compress the high-dimensional embeddings to maintain the same embedding distribution and better recover the ranking features.Our experiments show that ConAE is effective in compressing embeddings by achieving comparable ranking performance with its teacher model and making the retrieval system more efficient.Our further analyses show that ConAE can alleviate the redundancy of the embeddings of dense retrieval with only one linear layer.All codes of this work are available at https://github.com/NEUIR/ConAE.

The high training costs of graph neural networks (GNNs) have limited their applicability on large graphs, e.g., graphs with hundreds of millions of vertices which have become common in the era of big data. A few recent studies propose distributed GNN systems. However, these systems may generate high communication costs due to the extensive message passing among graph vertices stored on different machines. To address such limitations, in the paper, 1) we propose a distributed GNN computation system named EC-Graph for CPU clusters, which drastically reduces the communication costs among the machines by message compression; 2) we design a requesting-end compensation method for the embeddings to mitigate the errors induced by compression in the forward propagation and a Bit-Tuner to adaptively balance the model accuracy and message size; and 3) we propose a responding-end compensation approach for the embedding gradients in the backward propagation. Extensive experiments over large real-world datasets show that EC-Graph outperforms state-of-the-art distributed GNN systems on two CPU clusters of different sizes.

The advent of online applications such as social networks has led to an unprecedented scale of data and complex relationships among data. Hypergraphs are introduced to represent complex relationships that may involve more than two entities. A hypergraph is a generalized form of a graph, where edges are generalized to hyperedges. Each hyperedge may consist of any number of vertices. The flexibility of hyperedges also brings challenges in distributed hypergraph processing. In particular, a hypergraph is more difficult to be partitioned and distributed among$k$workers with balanced partitions. In this paper, we propose to convert a hypergraph into an intersection graph before partitioning by leveraging the inherent shared relationships among hypergraphs. We explore the intersection graph construction method and the corresponding partition strategy which can achieve the goal of evenly distributing vertices and hyperedges across workers, while yielding a significant communication reduction. We also design a distributed processing framework named$Hyraph$that can directly run hypergraph analysis algorithms on our intersection graphs. Experimental results on real datasets confirm the effectiveness of our techniques and the efficiency of the$Hyraph$framework.

Bregman distances (also known as Bregman divergences) are widely used in machine learning, speech recognition and signal processing, andkNN searches with Bregman distances have become increasingly important with the rapid advances of multimedia applications. Data in multimedia applications such as images and videos are commonly transformed into space of hundreds of dimensions. Such high-dimensional space has posed significant challenges for existingkNN search algorithms with Bregman distances, which could only handle data of medium dimensionality (typically less than 100). This paper addresses the urgent problem of high-dimensionalkNN search with Bregman distances. We propose a novel partition-filter-refinement framework. Specifically, we propose an optimized dimensionality partitioning scheme to solve several non-trivial issues. First, an effective bound from each partitioned subspace to obtain exactkNN results is derived. Second, we conduct an in-depth analysis of the optimized number of partitions and devise an effective strategy for partitioning. Third, we design an efficient integrated index structure for all the subspaces together to accelerate the search processing. Moreover, we extend our exact solution to an approximate version by a trade-off between the accuracy and efficiency. Experimental results on four real-world datasets and two synthetic datasets show the clear advantage of our method in comparison to state-of-the-art algorithms.

Due to the wide applications in recommendation systems, multi-class label prediction and deep learning, the Maximum Inner Product (MIP) search problem has received extensive attention in recent years. Faced with large-scale datasets containing high-dimensional feature vectors, the state-of-the-art LSH-based methods usually require a large number of hash tables or long hash codes to ensure the searching quality, which takes up lots of index space and causes excessive disk page accesses. In this paper, we relax the guarantee of accuracy for efficiency and propose an efficient method for c-Approximate Maximum Inner Product (c-AMIP) search with a lightweight iDistance index. We project high-dimensional points to low-dimensional ones via 2-stable random projections and derive probability-guaranteed searching conditions, by which the c-AMIP results can be guaranteed in accuracy with arbitrary probabilities. To further improve the efficiency, we propose Quick-Probe for quickly determining the searching bound satisfying the derived condition in advance, avoiding the inefficient incremental searching process. Extensive experimental evaluations on four real datasets demonstrate that our method requires less pre-processing cost including index size and pre-processing time. In addition, compared to the state-of-the-art benchmark methods, it provides superior results on searching quality in terms of overall ratio and recall, and efficiency in terms of page access and running time.

Abstract Hyperspace hashing which is often applied to NoSQL data-bases builds indexes by mapping objects with multiple attributes to a multidimensional space. It can accelerate processing queries of some secondary attributes in addition to just primary keys. In recent years, the rich computing resources of GPU provide opportunities for implementing high-performance HyperSpace Hash. In this study, we construct a fully concurrent dynamic hyperspace hash table for GPU. By using atomic operations instead of locking, we make our approach highly parallel and lock-free. We propose a special concurrency control strategy that ensures wait-free read operations. Our data structure is designed considering GPU specific hardware characteristics. We also propose a warp-level pre-combinations data sharing strategy to obtain high parallel acceleration. Experiments on an Nvidia RTX2080Ti GPU suggest that GHSH performs about 20-100X faster than its counterpart on CPU. Specifically, GHSH performs updates with up to 396 M updates/s and processes search queries with up to 995 M queries/s. Compared to other GPU hashes that cannot conduct queries on non-key attributes, GHSH demonstrates comparable building and retrieval performance.

In the big data era, distributed computation is becoming a preferred solution for iterative graph analysis. However, graphs are rapidly growing in size and more importantly, there exist a lot of messages across iterations. For better scalability, many distributed systems keep graph data and message data on disk. Now these systems solely employ either pushing or pulling mode to manage data, but neither can always work well during the entire computation. This is mainly because I/O access patterns are dynamic and complex. This article proposes a hybrid solution. It achieves the optimal performance in different scenarios by dynamically and adaptively switching modes between pushing and pulling. Specifically, we first devise a new block-centric pulling technique. It pulls messages much more I/O-efficiently than the existing vertex-centric pulling mode. We then combine pushing and pulling. For general-purpose, we categorize graph algorithms and accordingly present two seamless switching frameworks. We also design performance prediction components specialized to the two frameworks, to decide how and when we can switch modes. Some optimization strategies are also given to further enhance performance, such as priority scheduling and lightweight fault-tolerance. Extensive experiments against state-of-the-art solutions confirm the effectiveness of our proposals.

Missing value (MV) imputation is a critical preprocessing means for data mining. Nevertheless, existing MV imputation methods are mostly designed for batch processing, and thus are not applicable to streaming data, especially those with poor quality. In this article, we propose a framework, called Real-time and Error-tolerant Missing vAlue ImputatioN (REMAIN), to impute MVs in poor-quality streaming data. Instead of imputing MVs based on all the observed data, REMAIN first initializes the MV imputation model based on a-RANSAC which is capable of detecting and rejecting anomalies in an efficient manner, and then incrementally updates the model parameters upon the arrival of new data to support real-time MV imputation. As the correlations among attributes of the data may change over time in unforseenable ways, we devise a deterioration detection mechanism to capture the deterioration of the imputation model to further improve the imputation accuracy. Finally, we conduct an extensive evaluation on the proposed algorithms using real-world and synthetic datasets. Experimental results demonstrate that REMAIN achieves significantly higher imputation accuracy over existing solutions. Meanwhile, REMAIN improves up to one order of magnitude in time cost compared with existing approaches.

To study the issue of missing values (MVs), we propose the Order-Sensitive Imputation for Clustered Missing values (OSICM) framework, in which missing values are imputed sequentially such that the values filled earlier in the process are also used for later imputation of other MVs. Obviously, the order of imputations is critical to the effectiveness and efficiency of OSICM framework. We formulate the searching of the optimal imputation order as an optimization problem, and show its NP-hardness. Furthermore, we devise an algorithm to find the exact optimal solution and propose two approximate/heuristic algorithms to trade off effectiveness for efficiency. Finally, we conduct extensive experiments on real and synthetic datasets to demonstrate the superiority of our OSICM framework.

The issue of missing values (MVs) has appeared widely in real-world datasets and hindered the use of many statistical or machine learning algorithms for data analytics due to their incompetence in handling incomplete datasets. To address this issue, several MV imputation algorithms have been developed. However, these approaches do not perform well when most of the incomplete tuples are clustered with each other, coined here as the Clustered Missing Values Phenomenon, which attributes to the lack of sufficient complete tuples near an MV for imputation. In this paper, we propose the Order-Sensitive Imputation for Clustered Missing values (OSICM) framework, in which missing values are imputed sequentially such that the values filled earlier in the process are also used for later imputation of other MVs. Obviously, the order of imputations is critical to the effectiveness and efficiency of OSICM framework. We formulate the searching of the optimal imputation order as an optimization problem, and show its NP-hardness. Furthermore, we devise an algorithm to find the exact optimal solution and propose two approximate/heuristic algorithms to trade off effectiveness for efficiency. Finally, we conduct extensive experiments on real and synthetic datasets to demonstrate the superiority of our OSICM framework.

The k nearest neighbor (kNN) query in road networks is a traditional query type in spatial databases. This query has found new applications in the fast-growing location-based services, e.g., finding the k nearest Uber cars of a user for ridesharing. KNN queries in these applications are non-trivial to process due to the frequent location updates of data objects (e.g., movements of the cars). This calls for novel spatial indexes with high efficiency in not only query processing but also update handling. To address this need, we propose an index structure that uses a "lazy update" strategy to reduce the costs of update handling without sacrificing query efficiency or answer accuracy. We cache the location updates of data objects and only update the corresponding entries in the index when they are queried. We further propose a kNN query algorithm based on this index. This algorithm takes advantage of the strengths of both the CPU and the GPU. It first identifies the queried region and updates the index over this region using the GPU. Then, it uses the GPU to query the index and produce a candidate result set, which is later refined by the CPU to obtain the final query answer. We conduct experiments on real data and compare the proposed algorithm with state-of-the-art kNN algorithms. The experimental results show that the proposed algorithm outperforms the baseline algorithms by orders of magnitude in query time.

The k Nearest Neighbor (k-NN) query has been gaining more importance in extensive applications involving information retrieval, data mining, and databases. Specifically, in order to trade off accuracy for efficiency, approximate solutions for the k-NN query are extensively explored. However, the precision is usually order-insensitive, which is defined on the result set instead of the result sequence. In many situations, it cannot reasonably reflect the query result quality. In this paper, we focus on the approximate k-NN query problem with the order-sensitive precision requirement and propose a novel scheme based on the projection-filter-refinement framework. Basically, we adopt PCA to project the high-dimensional data objects into the low-dimensional space. Then, a filter condition is inferred to execute efficient pruning over the projected data. In addition, an index strategy named OR-tree is proposed to reduce the I/O cost. The extensive experiments based on several real-world data sets and a synthetic data set are conducted to verify the effectiveness and efficiency of the proposed solution. Compared to the state-of-the-art methods, our method can support order-sensitive k -NN queries with higher result precision while retaining satisfactory CPU and I/O efficiency.

Most graph algorithms are iterative in nature. They can be processed by distributed systems in memory in an efficient asynchronous manner. However, it is challenging to recover from failures in such systems. This is because traditional checkpoint fault-tolerant frameworks incur expensive barrier costs that usually offset the gains brought by asynchronous computations. Worse, surviving data are rolled back, leading to costly re-computations. This paper first proposes to leverage surviving data for failure recovery in an asynchronous system. Our framework guarantees the correctness of algorithms and avoids rolling back surviving data. Additionally, a novel asynchronous checkpointing solution is introduced to accelerate recovery at the price of nearly zero overheads. Some optimization strategies like message pruning, non-blocking recovery and load balancing are also designed to further boost the performance. We have conducted extensive experiments to show the effectiveness of our proposals using real-world graphs.

Myriad of parameter estimation algorithms can be performed by an Expectation-Maximization (EM) approach. Traditional synchronous frameworks can parallelize these EM algorithms on the cloud to accelerate computation while guaranteeing the convergence. However, expensive synchronization costs pose great challenges for efficiency. Asynchronous solutions have been recently designed to bypass high-cost synchronous barriers but at expense of potentially losing convergence guarantee.

We study result diversification in continuous spatial query processing and formulate a new type of queries, the moving k diversified nearest neighbor query (MkDNN). Given a moving query object, an MkDNN query maintains continuously the k diversified nearest neighbors of the query object. Here, how diversified the nearest neighbors are is defined on the distance between the nearest neighbors. We propose an algorithm to maintain incrementally the k diversified nearest neighbors to reduce the costs of continuous query processing. We further propose two approximate algorithms to obtain even higher query efficiency with precision bounds. We verify the effectiveness and efficiency of the proposed algorithms empirically. The results confirm the superiority of the proposed algorithms.

Differential privacy, which has been applied in Google Chrome and Apple iOS, provides strong privacy assurance to users while retaining the capability to discover statistical patterns from sensitive data. We focus on top-k frequent itemset mining on sensitive data, with the goal of obtaining high result utility while satisfying differential privacy. There are two basic methodologies to design a high-utility solution: one uses generic differential privacy mechanisms as building blocks, and minimizes result error through algorithm design. Most existing work follows this approach. The other methodology is to devise a new building block customized for frequent itemset mining. This is much more challenging: to our knowledge, only one recent work, NoisyCut, attempts to do so, unfortunately, Noisycut has been found to violate differential privacy. This paper proposes a novel solution PrivSuper, which contains both a new algorithm and a new differential privacy mechanism. Unlike most existing methods that follow the Apriori framework, which starts from single items and iteratively forms larger itemsets, PrivSuper directly searches for maximal frequent itemsets, and subsequently adds their sub-itemsets to the results without additional privacy budget consumption. During the search, PrivSuper applies a customized mechanism to extend the current itemset with one more item, which we call the sequence exponential mechanism (SEM). Notably, SEM does not consume any privacy budget at all, if it turns out that the current itemset cannot be extended. Extensive experiments using several real datasets demonstrate that PrivSuper achieves significantly higher result utility compared to previous solutions.

With the proliferation of geo-positioning techniques that enable users to acquire their geographical positions, there has been increasing popularity of online location-based services. This development has generated a large volume of points of interest labeled with category features (e.g., hotel, resort, stores, stations, and tourist attractions). It gives prominence to various types of spatial-keyword queries, which are employed to provide fundamental querying functionality for location-based services.

Many graph algorithms are iterative in nature and can be supported by distributed memory-based systems in a synchronous manner. However, an asynchronous model has been recently proposed to accelerate iterative computations. Nevertheless, it is challenging to recover from failures in such a system, since a typical checkpointing based approach requires many expensive synchronization barriers that largely offset the gains of asynchronous computations.

We revisit the moving k nearest neighbor (MkNN) query, which computes one's k nearest neighbor set and maintains it while at move. Existing MkNN algorithms are mostly safe region based, which lack efficiency due to either computing small safe regions with a high recomputation frequency or computing larger safe regions but with a high cost for each computation. In this demonstration, we showcase a system named INSQ that adopts a novel algorithm called the Influential Neighbor Set (INS) algorithm to process the MkNN query in both two-dimensional Euclidean space and road networks. This algorithm uses a small set of safe guarding objects instead of safe regions. As long as the the current k nearest neighbors are closer to the query object than the safe guarding objects are, the current k nearest neighbors stay valid and no recomputation is required. Meanwhile, the region defined by the safe guarding objects is the largest possible safe region. This means that the recomputation frequency is also minimized and hence, the INS algorithm achieves high overall query processing efficiency.

Earth Mover's Distance (EMD) evaluates the similarity between probability distributions, known as a robust measure more consistent with human similarity perception than traditional similarity functions. EMD similarity join retrieves pairs of probability distributions with EMD below a specified threshold, supporting many important applications, such as duplicate image retrieval and sensor pattern recognition. This paper studies the possibility of using MapReduce to improve the scalability of EMD similarity join. Utilizing the dual-program mapping technique, we present a new general data partition framework to facilitate effective workload decomposition using MapReduce, ensuring similar distributions in terms of EMD are mapped to the same reduce task for further verification. New optimization strategies are also proposed to balance the workloads among reduce tasks and eliminate large unnecessary EMD evaluations. Our experiments verify the superiority of our proposal on system efficiency, with a huge advantage of at least one order of magnitude than the state-of-the-art solution, and on system effectiveness, with a real case study towards the abused image phenomenon on C2C website in China. Further details are reported in [4].

Billion-node graphs are rapidly growing in size in many applications such as online social networks. Most graph algorithms generate a large number of messages during iterative computations. Vertex-centric distributed systems usually store graph data and message data on disk to improve scalability. Currently, these distributed systems with disk-resident data take a push-based approach to handle messages. This works well if few messages reside on disk. Otherwise, it is I/O-inefficient due to expensive random writes. By contrast, the existing memory-resident pull-based approach individually pulls messages for each vertex on demand. Although it can be used to avoid disk operations regarding messages, expensive I/O costs are incurred by random and frequent access to vertices.

As a major type of continuous spatial queries, the moving$k$nearest neighbor ($k$NN) query has been studied extensively. However, most existing studies have focused on only the query efficiency. In this paper, we consider further the usability of the query results, in particular the diversification of the returned data points. We thereby formulate a new type of query named themoving$k$diversified nearest neighbor query (M$k$DNN). This type of query continuously reports the$k$diversified nearest neighbors while the query object is moving. Here, the degree of diversity of the$k$NN set is defined on the distance between the objects in the$k$NN set. Computing the$k$diversified nearest neighbors is an NP-hard problem. We propose an algorithm to maintain incrementally the$k$diversified nearest neighbors to reduce the query processing costs. We further propose two approximate algorithms to obtain even higher query efficiency with precision bounds. We verify the effectiveness and efficiency of the proposed algorithms both theoretically and empirically. The results confirm the superiority of the proposed algorithms over the baseline algorithm.

Earth Mover's Distance (EMD) evaluates the similarity between probability distributions, known as a robust measure more consistent with human similarity perception than traditional similarity functions. EMD-based similarity join retrieves pairs of probability distributions with EMD below a specified threshold, supporting many important applications, such as duplicate image retrieval and sensor pattern recognition. This paper studies the possibility of using MapReduce to improve the scalability of EMD similarity join. While existing MapReduce optimization techniques mainly aim to minimize the communication overhead, such methods are not applicable to our problem, due to the high computational cost of EMD. Utilizing the dual-program mapping technique, we present a new general data partition framework to facilitate effective workload decomposition using MapReduce, ensuring similar distributions in terms of EMD are mapped to the same reduce task for further verification. New optimization strategies are also proposed to balance the workloads among reduce tasks and eliminate large unnecessary EMD evaluations. Our experiments verify the superiority of our proposal on system efficiency, with a huge advantage of at least one order of magnitude than the state-of-the-art solution, and on system effectiveness, with a real case study towards the abused image phenomenon on the most popular C2C Web site in China.

The moving k nearest neighbor query, which computes one's k nearest neighbor set and maintains it while at move, is gaining importance due to the prevalent use of smart mobile devices such as smart phones. Safe region is a popular technique in processing the moving k nearest neighbor query. It is a region where the movement of the query object does not cause the current k nearest neighbor set to change. Processing a moving k nearest neighbor query is a continuing process of checking the validity of the safe region and recomputing it if invalidated. The size of the safe region largely decides the frequency of safe region recomputation and hence query processing efficiency. Existing moving k nearest neighbor algorithms lack efficiency due to either computing small safe regions and have to recompute frequently or computing large safe regions (i.e., an order- k Voronoi cell) with a high cost. In this paper, we take a third approach. Instead of safe regions, we use a small set of safe guarding objects. We prove that, as long as the the current k nearest neighbors are closer to the query object than the safe guarding objects, the current k nearest neighbors stay valid and no recomputation is required. This way, we avoid the high cost of safe region recomputation. We also prove that, the region defined by the safe guarding objects is the largest possible safe region. This means that the recomputation frequency of our method is also minimized. We conduct extensive experiments comparing our method with the state-of-the-art method on both real and synthetic data sets. The results confirm the superiority of our method.

Recently, probabilistic graphs have attracted significant interests of the data mining community. It is observed that correlations may exist among adjacent edges in various probabilistic graphs. As one of the basic mining techniques, graph clustering is widely used in exploratory data analysis, such as data compression, information retrieval, image segmentation, etc. Graph clustering aims to divide data into clusters according to their similarities, and a number of algorithms have been proposed for clustering graphs, such as the pKwikCluster algorithm, spectral clustering, k-path clustering, etc. However, little research has been performed to develop efficient clustering algorithms for probabilistic graphs. Particularly, it becomes more challenging to efficiently cluster probabilistic graphs when correlations are considered. In this paper, we define the problem of clustering correlated probabilistic graphs. To solve the challenging problem, we propose two algorithms, namely the PEEDR and the CPGS clustering algorithm. For each of the proposed algorithms, we develop several pruning techniques to further improve their efficiency. We evaluate the effectiveness and efficiency of our algorithms and pruning methods through comprehensive experiments.

Nowadays, many applications return to the user a set of results that take the query as their nearest neighbor, which are commonly expressed through reverse nearest neighbor (RNN) queries. When considering moving objects, users would like to find objects that appear in the RNN result set for a period of time in some real-world applications such as collaboration recommendation and anti-tracking. In this work, we formally define the problem of interval reverse nearest neighbor (IRNN) queries over moving objects, which return the objects that maintain nearest neighboring relations to the moving query objects for the longest time in the given interval. Location uncertainty of moving data objects and moving query objects is inherent in various domains, and we investigate objects that exhibit Markov correlations, that is, each object's location is only correlated with its own location at previous timestamp while being independent of other objects. There exists the efficiency challenge for answering IRNN queries on uncertain moving objects with Markov correlations since we have to retrieve not only all the possible locations of each object at current time but also its historically possible locations. To speed up the query processing, we present a general framework for answering IRNN queries on uncertain moving objects with Markov correlations in two phases. In the first phase, we apply space pruning and probability pruning techniques, which reduce the search space significantly. In the second phase, we verify whether each unpruned object is an IRNN of the query object. During this phase, we propose an approach termed Probability Decomposition Verification (PDV) algorithm which avoid computing the probability of any object being an RNN of the query object exactly and thus improve the efficiency of verification. The performance of the proposed algorithm is demonstrated by extensive experiments on synthetic and real datasets, and the experimental results show that our algorithm is more efficient than the Monte-Carlo based approximate algorithm.

Given a set of spatial objects, facilities can influence the objects located within their influence regions that are represented by circular disks with the same radius $(r)$. Our task is to select the minimum number of locations such that establishing a temporary facility at each selected location would ensure that all the objects are influenced. Aiming to solve this location selection problem, we propose a novel kind of location selection query, called group location selection (GLS) queries. In many real-world applications, every object is usually located within an uncertainty region instead of at an exact point. Due to the uncertainty of the data, GLS processing needs to ensure that the probability of each uncertain object being influenced by one facility is not less than a given threshold $(\tau)$. An analysis of the time cost reveals that it is infeasible to exactly answer GLS queries over uncertain objects in polynomial time. Hence, this paper proposes an approximate query framework for answering queries efficiently while guaranteeing that the results of GLS queries are correct with a bounded probability. The performance of the proposed methods of the framework is demonstrated by theoretical analysis and extensive experiments with both real and synthetic data sets.

The Earth Mover's Distance, or EMD for short, has been proven to be effective for content-based image retrieval. However, due to the cubic complexity of EMD computation, it remains difficult to use EMD in applications with stringent requirement for efficiency. In this paper, we present our new system, called EUDEMON, which utilizes new techniques to support fast Online Video Frame Copy Detection based on the EMD. Given a group of registered frames as queries and a set of targeted detection videos, EUDEMON is capable of identifying relevant frames from the video stream in real time. The significant improvement on efficiency mainly relies on the primal-dual theory in linear programming and well-designed B+tree filters for adaptive candidate pruning. Generally speaking, our system includes a variety of new features crucial to the deployment of EUDEMON in real applications. First, EUDEMON achieves high throughput even when a large number of queries are registered in the system. Second, EUDEMON contains self-optimization component to automatically enhance the effectiveness of the filters based on the recent content of the video stream. Finally, EUDEMON provides a user-friendly visualization interface, named EMD Flow Chart, to help the users to better understand the alarm with the perspective of the EMD.

In recent years, there has been a growing need for location-based services (LBS), ranging from resource tracking to personal life assistance. The Moving k Nearest Neighbor (MkNN) query is a main problem in the LBS area, which retrieves the top k nearest neighbors while the query consumer moves. Considerable attention is attracted to this query type and a large number of studies are proposed recently. Most of these studies focus on ideal Euclidean plane where any two points are visible. In this paper, we propose a method to process MkNN queries in areas with obstacles, which is more realistic. We propose the obstacle-free safe region (OSR) concept within which a query point has the same kNN. No additional processing is required when the query consumer moves inside one OSR. Several novel properties are also introduced and employed in our efficient MkNN processing algorithm. Our experimental results show that our approach handles the MkNN queries with high accuracy and works efficiently.

Moving range query over RFID data streams is one of the most important spatio-temporal queries to support valuable information analysis. However, the location uncertainty challenges the query strategy. In this paper, we propose a probability evaluation model in the RFID-enabled monitoring environments and discuss the query optimization techniques under the scenarios of continuous moving range query, which can also be applied into more situations. The extensive experimental evaluation verifies the efficiency and effectiveness of our proposed model and methods.

The tagging technique has been widely applied in existing Web 2.0 systems, where users label resources with tags for effective classification and efficient retrieval of resources. Location-aware geographical tags (geo-tags) are required if users want to mark location-sensitive resources to digital maps. Large volumes of different kinds of user-created tags pose challenges to the effective organization of community resources using tags. Issues such as guaranteeing the quality of tags and supporting various tag-based queries emerge. In this demo, we present MarcoPolo, a Web 2.0 community system that allows users to define the hierarchical textual geo-tags and mark resources to a map using geo-tags. Statistical and feedback mechanisms are applied to guarantee the quality of tags (including geo-tags). The MarcoPolo system provides two effective interfaces for users to browse and search resources: one is the keyword-based interface and the other is the map-based interface.

Radio Frequency Identification (RFID) has gained a lot of attention as a promising technology that facilitates pervasive computing and the gradual proliferation of RFID-based applications will produce a large amount of urgent and complicated event streams. The RFID middleware system is expected to offer the further complex event processing service to satisfy the high-level query semantics and performance demands, and therefore, how to evaluate the service capability will be a key problem in mission-critical monitoring scenarios. In this paper, we analyze the RFID primitive event arrival and complex event processing model in a novel perspective. Furthermore, based on our proposed models, service capability evaluation method is introduced to estimate whether and how the RFID middleware system can afford the query requirements in a deterministic or statistical manner, which is believed to be very helpful in RFID-based applications. Our experiments demonstrate the utility and feasibility of our models and methods.

Correlation analysis is a basic problem in the field of data stream mining. Typical approaches add sliding window to data streams to get the recent results, but the window length defined by users is always fixed which is not suitable for the changing stream environment. We propose a Boolean representation based data-adaptive method for correlation analysis among a large number of time series streams. The periodical trends of each stream series to are monitored to choose the most suitable window size and group the series with the same trends together. Instead of adopting complex pair-wise calculation, we can also quickly get the correlation pairs of series at the optimal window sizes. All the processing is realized by simple Boolean operations. Both the theory analysis and the experimental evaluations show that our method has good computation efficiency with high accuracy.