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.

The inherent connectivity and dependency of graph-structured data, combined with its unique topology-driven access patterns, pose fundamental challenges to conventional data replication and request routing strategies in geo-distributed cloud storage systems. In this paper, we propose GeoLayer, a geo-distributed graph storage framework that jointly optimizes graph replica placement and pattern request routing. We first construct a latency-aware layered graph architecture that decomposes the graph topology into multiple layers, aiming to reduce the decision space and computational complexity of the optimization problem, while mitigating the impact of network heterogeneity in geo-distributed environments. Building on the layered graph, we introduce an overlap-centric replica placement scheme to accommodate the diversity of graph pattern accesses, along with a directed heat diffusion model that captures heat conduction and superposition effects to guide data allocation. For request routing, we develop a stepwise layered routing strategy that performs progressive expansion over the layered graph to efficiently retrieve the required data. Experimental results show that, compared to state-of-the-art replica placement and routing schemes, GeoLayer achieves a 1.34x - 3.67x improvement in response times for online graph pattern requests and a 1.28x - 3.56x speedup in offline graph analysis performance.

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.

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.

Various graph models have emerged to meet diverse application needs, each with unique characteristics and specialties. Managing and analyzing graph data inevitably requires interactions across different models to serve upstream business requirements. Therefore, an Extract-Transform-Load (ETL) tool designed to bridge different graph models is desired. In this paper, we propose GETL, a generalized graph ETL framework capable of automatically identifying graph model schemas and performing seamless data conversion among RDF, RDF-star, labeled property graph, and the relational model. This is attributed to GETL's unified graph representation model, constructed as nested label, entity pairs, offering powerful capabilities in graph representation and model compatibility. Additionally, we develop a unified programming interface to support complex graph transformation tasks. It is built upon the Gremlin syntax and provides strong expressive capabilities. Finally, our evaluation demonstrates that GETL outperforms state-of-the-art solutions in terms of model conversion efficiency and data manipulation language (DML) intelligibility.

A great number of graph analysis algorithms involve iterative computations, which dominate the runtime. Accelerating iterative graph computations has become the key to improving the performance of graph algorithms. While numerous studies have focused on reducing the runtime of each iteration to improve efficiency, the optimization of the number of iterations is often overlooked. In this work, we first establish a correlation between vertex processing order and the number of iterations, providing an opportunity to reduce the number of iterations. We propose a metric function to evaluate the effectiveness of vertex processing order in accelerating iterative computations. Leveraging this metric, we propose a novel graph reordering method, GoGraph, which constructs an efficient vertex processing order. Additionally, for evolving graphs, we further propose a metric function designed to evaluate the effectiveness of vertex processing orders in response to graph changes and provide three optional methods for dynamically adjusting the vertex processing order. Our experimental results illustrate that GoGraph sur passes current state-of-the-art reordering algorithms, improving runtime by an average of 1.83× (up to 3.34×). Compared to traditional synchronous computation methods, our approach enhances the speed of iterative computations by up to 6.30×. In dynamic scenarios, incremental GoGraph can reduce end-to-end time by 43% on average (up to 48%).

Explainable recommendation has attracted great attention due to its capability of enhancing user trust and satisfaction. Users’ curiosities highly affect the recommendation accuracy and the effectiveness of explanations. Different target users have different levels of curiosities, while the curiosity of the same user changes dynamically. However, existing techniques cannot capture users’ dynamic curiosities from the historical user-item interactions for effective explainable recommendation. In this article, we propose a novel explainable recommendation approach for effective D ynamic C uriosity-aware E xplainable R ecommendation (DCER). Specifically, we first propose a novel multi-view representation learning to model the temporal user-item interactions. Then, we propose a new curiosity-enhanced recommendation to dynamically capture users’ curiosities, which improves the recommendation quality in a mutual promotion manner. Finally, we propose an adaptive rule-guided hybrid explanation generation strategy that enables more personalized explanations and well reflects the users’ dynamic psychological states behind the transactions. The experimental results demonstrate the high effectiveness of our proposed model.

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.

With the rapid growth of multi-source and heterogeneous health data, achieving efficient and trustworthy crosschain sharing while ensuring privacy and security has become a critical challenge in blockchain-based healthcare applications. To address this, this paper proposes a secure health data sharing method based on a cross-chain blockchain architecture. A fourlayer system framework is constructed, and two original core modules, D-FBAC and HAEPP, are designed. The D-FBAC module introduces a reputation-weighted attribute mechanism to achieve resilient and fine-grained access control. The HAEPP module combines hybrid encryption strategies with a key lifecycle management mechanism to enhance privacy protection during both on-chain and cross-chain data flows. To improve system interpretability and user trust, an off-chain explainable access rejection module is also integrated, enabling rule-level traceability and feedback for access denials. The experimental evaluation is conducted on real-world healthcare datasets using a comprehensive set of metrics, results show that the proposed system significantly outperforms existing approaches across multiple performance dimensions, offering valuable insights for the interoperability and trusted governance of healthcare information systems.

Fairness-aware recommendation has emerged as a pivotal research area in recent years. Current fairness studies primarily examine two independent dimensions: user-side fairness and item-side fairness. However, most approaches address each side's fairness in isolation while neglecting their complex interdependencies. In this paper, we propose an LLM-Enhanced DiscriminAtive Counterfactual Debiasing Model for Two-sided Fairness in Recommendation (LeadFairRec). Specifically, we first design a two-sided causal graph that jointly models provider-customer fairness interactions through their causal relationships. Then we propose a discriminative counterfactual debiasing method, which effectively removes spurious correlations while maintaining true user-item interactions. Finally, we propose an LLM-enhanced counterfactual inference method to derive noise-resistant user/item representations from interaction data, enhancing the robustness of causal debiasing. The experimental results demonstrate the high effectiveness of our proposed model. We provide our code at https://github.com/houyimin660/LeadFairRec.

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.

Geo-distributed consensus protocols provide high availability and resilience for distributed database services. These protocols group nodes by their data centers to leverage the network topology that spans across multiple data centers, thereby reducing costly cross-datacenter communication. However, they still face performance and scalability challenges due to inefficient log replication mechanisms. 1) These protocols rely on the leader node in each group to perform cross-datacenter log replication, creating a single-node performance bottleneck. 2) Byzantine receivers can behave arbitrarily, forcing the group leader to send multiple log copies during replication to prevent loss, thus causing redundant transmissions. 3) Since all groups must execute these logs in the same order, synchronizations across groups are necessary to maintain consistency when multiple groups are proposing concurrently, which also slow down log replication. This paper presents MassBFT, a Byzantine fault-tolerant geo-consensus protocol that achieves high performance and scalability. We design an encoded bijective log replication to eliminate the leader bottleneck and reduce the cross-datacenter network consumption. We also propose asynchronous log ordering to eliminate synchronization across groups. Experimental results show that MassBFT is scalable, fault-tolerant, and outperforms state-of-the-art protocols with 5.49-29.96 times higher throughput under YCSB, SmallBank, and TPC-C workloads.

Retrieval-Augmented Generation (RAG) has proven its effectiveness in mitigating hallucinations in Large Language Models (LLMs) by retrieving knowledge from external resources. To adapt LLMs for the RAG systems, current approaches use instruction tuning to optimize LLMs, improving their ability to utilize retrieved knowledge. This supervised fine-tuning (SFT) approach focuses on equipping LLMs to handle diverse RAG tasks using different instructions. However, it trains RAG modules to overfit training signals and overlooks the varying data preferences among agents within the RAG system. In this paper, we propose a Differentiable Data Rewards (DDR) method, which end-to-end trains RAG systems by aligning data preferences between different RAG modules. DDR works by collecting the rewards to optimize each agent in the RAG system with the rollout method, which prompts agents to sample some potential responses as perturbations, evaluates the impact of these perturbations on the whole RAG system, and subsequently optimizes the agent to produce outputs that improve the performance of the RAG system. Our experiments on various knowledge-intensive tasks demonstrate that DDR significantly outperforms the SFT method, particularly for LLMs with smaller-scale parameters that depend more on the retrieved knowledge. Additionally, DDR exhibits a stronger capability to align the data preference between RAG modules. The DDR method makes the generation module more effective in extracting key information from documents and mitigating conflicts between parametric memory and external knowledge. All codes are available at https://github.com/OpenMatch/RAG-DDR.

Knowledge tracing plays a pivotal role in enabling personalized learning on online platforms. While deep learning-based approaches have achieved impressive predictive performance, their limited interpretability poses a significant barrier to practical adoption. Existing explanation methods primarily focus on specific model architectures and fall short in 1) explicitly prioritizing critical interactions to generate fine-grained explanations, and 2) maintaining similarity consistency across interaction importance. These limitations hinder actionable insights for improving student outcomes. To bridge the gap, we propose a model-agnostic approach that provides enhanced explanations applicable to diverse knowledge tracing methods. Specifically, we propose a novel ranking loss designed to explicitly optimize the importance ranking of past interactions by comparing their corresponding perturbed outputs. Furthermore, we introduce a similarity loss to capture temporal dependencies, ensuring consistency in the assigned importance scores for conceptually similar interactions. Extensive experiments conducted on various knowledge tracing models and benchmark datasets demonstrate substantial enhancements in explanation quality.

With the rapid advancement of Multi-modal Large Language Models (MLLMs), their capability in understanding both images and text has greatly improved. However, their potential for leveraging multi-modal contextual information in Retrieval-Augmented Generation (RAG) remains largely underexplored. To address this gap, this paper introduces Multi-Modal Retrieval-Augmented Generation (M2RAG), a benchmark designed to evaluate the effectiveness of Multi-modal Large Language Models in leveraging knowledge from multi-modal retrieval documents. The benchmark comprises four tasks: image captioning, multi-modal question answering, multi-modal fact verification, and image reranking. All tasks are set in an open-domain setting, requiring RAG models to retrieve query-relevant information from a multi-modal document collection and use it as contextual input for RAG modeling. To enhance the context utilization capabilities of MLLMs, we also introduce Multi-Modal Retrieval-Augmented Instruction Tuning (MM-RAIT), an instruction tuning method that optimizes MLLMs within multi-modal contexts. Our experiments demonstrate the effectiveness of MM-RAIT by significantly improving the quality of responses generated by different RAG models, outperforming MiniCPM-V 2.6 and Qwen2-VL with 34% and 33% gains, respectively. All data and code are available at https://github.com/NEUIR/M2RAG.

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.

Large language models (LLMs) integrated with retrieval-augmented generation (RAG) have improved factuality by grounding outputs in external evidence. However, they remain susceptible to unfaithful generation, where outputs contradict retrieved context despite its relevance and accuracy. Existing approaches aiming to improve faithfulness primarily focus on enhancing the utilization of external context, but often overlook the persistent influence of internal parametric knowledge during generation. In this work, we investigate the internal mechanisms behind unfaithful generation and identify a subset of mid-to-deep feed-forward networks (FFNs) that are disproportionately activated in such cases. Building on this insight, we propose Parametric Knowledge Muting through FFN Suppression (ParamMute), a framework that improves contextual faithfulness by suppressing the activation of unfaithfulness-associated FFNs and calibrating the model toward retrieved knowledge. To evaluate our approach, we introduce CoFaithfulQA, a benchmark specifically designed to evaluate faithfulness in scenarios where internal knowledge conflicts with accurate external evidence. Experimental results show that ParamMute significantly enhances faithfulness across both CoFaithfulQA and the established ConFiQA benchmark, achieving substantial reductions in reliance on parametric memory. These findings underscore the importance of mitigating internal knowledge dominance and provide a new direction for improving LLM trustworthiness in RAG. All codes are available at https://github.com/OpenBMB/ParamMute.

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.

Existing federated learning frameworks are primarily designed for single-modal data. However, real-world scenarios require processing multi-modal data on heterogeneous devices. The gap between existing methods and real-world scenarios presents challenges in processing multimodal data on heterogeneous devices, significantly impacting model training efficiency. To address these issues, we propose a multimodal federated learning framework, which integrates multimodal algorithms with a semi-synchronous training method. The multimodal algorithm trains local autoencoders on different data modalities. By leveraging the similarity of encodings across different modalities with the same data labels, we further train and aggregate these local autoencoders into a global autoencoder, which is then deployed on the blockchain to perform downstream classification tasks. In the semi-synchronous training method, each device updates its parameters independently during a round. At the end of each round, a global aggregation combines the updates from devices. We conduct an empirical evaluation of our framework on various multimodal datasets, including Opportunity (Opp) Challenge, mHealth, and UR Fall Detection datasets. Experimental results demonstrate that our federated learning framework, outperforms the state-of-the-art multimodal frameworks on three multimodal datasets, achieving an average accuracy improvement of 9.07%. Furthermore, in terms of training speed, MMFed is obviously superior to synchronization strategies when it is extended to a large number of clients.

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-based Retrieval-Augmented Generation (GraphRAG) has emerged as a promising paradigm for enhancing LLM reliability by enabling multi-hop reasoning over graph-structured knowledge. However, existing LLMs struggle to efficiently process graph-structured inputs, as traditional attention mechanisms are sequence-based and introduce significant redundancy when serializing graphs into prompt sequences, leading to excessive computation and memory overhead. To address this, we introduce dependency attention, a novel graph-aware attention mechanism that restricts attention computation to token pairs with structural dependencies in the retrieved subgraph. Unlike standard self-attention that computes fully connected interactions, dependency attention prunes irrelevant token pairs and reuses computations along shared relational paths, substantially reducing inference overhead. Building on this idea, we develop DepCache, a KV cache management framework tailored for dependency attention. DepCache enables efficient KV cache reuse through (i) a graph-based KV cache reuse strategy that aligns KV caches across varying prompt contexts, enabling efficient cross-request reuse in GraphRAG, and (ii) a locality-aware replacement policy that leverages spatial and temporal access patterns to improve KV cache hit rate. Evaluations across diverse models and datasets show that DepCache improves LLM inference throughput by 1.5×-5.0× and reduces time-to-first-token latency by up to 3.2×, without compromising generation accuracy.

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.

Leveraging GPUs' high parallelism can significantly improve the real-time computation efficiency of streaming graph processing. However, when a large-scale graph exceeds GPU memory capacity, CPU-GPU cooperative processing often results in substantial and irregular CPU-to-GPU data transfer overhead. This stems from the extensive redundant graph accesses during continuous computation, which can hardly be addressed by existing solutions. In this work, we present Grapin, an out-of-memory GPU streaming graph processing system designed to minimize graph data transfer via two effective techniques for eliminating redundant accesses: (1) Extending advanced incremental processing algorithms to GPUs by converting their heavyweight data dependency processing into GPU-friendly forms, eliminating redundant graph accesses from the computation side; and (2) providing a lightweight yet efficient GPU hot subgraph management framework that finely caches the frequently accessed dynamic subgraphs in a vertex-centric manner. Experimental results demonstrate that Grapin can efficiently process large-scale streaming graphs with billions of edges on a single NVIDIA A5000 GPU. Enabling incremental computation reduces data transfer by 61%, and the integration of GPU hot subgraph reuse further reduces the remaining transfer by 72%, resulting in a total reduction of 89%. Compared with CPU-based solutions, Grapin achieves speedups ranging from 1.8x to 96.9x (17.9x on average).

Existing disaggregated databases separate execution and storage layers, enabling independent and elastic scaling of resources. In most cases, this design makes transaction concurrency control (CC) a critical bottleneck, which demands significant computing resources for concurrent conflict management and struggles to scale due to the coordination overhead for concurrent conflict resolution. Coupling CC with execution or storage limits performance and elasticity, as CC's resource needs do not align with the free scaling of the transaction execution layer or the storage-bound data layer. This paper proposes Concurrency Control as a Service (CCaaS), which decouples CC from databases, building an execution-CC-storage three-layer decoupled database, allowing independent scaling and upgrades for improved elasticity, resource utilization, and development agility. However, adding a new layer increases latency due to the shift in communication from hardware to network. To address this, we propose a Sharded Multi-Write OCC (SM-OCC) algorithm with an asynchronous log push-down mechanism to minimize network communications overhead and transaction latency. Additionally, we implement a multi-write architecture with a deterministic conflict resolution method to reduce coordination overhead in the CC layer, thereby improving scalability. CCaaS is designed to be connected by a variety of execution and storage engines. Existing disaggregated databases can be revolutionized with CCaaS to achieve high elasticity, scalability, and high performance. Results show that CCaaS achieves 1.02–3.11X higher throughput and 1.11–2.75X lower latency than SoTA disaggregated databases.

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.

Few-shot classification is increasingly relevant in emerging applications, such as university course classification in intelligent education systems. University course classification helps students acquire specific skills, comprehend course purposes, and assists departments in defining training goals. However, classifying frontier courses presents challenges due to the absence of labels and descriptions. Few-shot learning addresses this by acquiring meta-knowledge. Heterogeneous graphs (HGs), rich in semantic information, introduce complexities that make few-shot particularly challenging. Addressing this problem, we propose a subgraph-aware convolutional few-shot classification method on HGs (HG-SCC). We first formalize the subgraph sampling strategy for HGs and different views under meta-paths. Then, the layer number adaptive spectral-based graph convolution is designed for personalized node embedding. Furthermore, a high-order convolution operation with classes as nodes is designed to increase the class representation coverage. Modeling subgraph centrality, combined with node features, captures structural information, improving awareness of each sampled subgraph, thus alleviating sparsity in new class labels and enhancing classification accuracy. Euclidean distance-based and task-affected cosine similarity-based classifiers under different meta-paths are proposed, with stacking introduced to blend multiple classifiers based on subgraph features. Experimental results show that our method has high performance in course classification and also outperforms state-of-the-art methods on benchmark datasets.

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.

The key performance bottleneck of large-scale graph processing on memory-limited GPUs is the host-GPU graph data transfer. Existing GPU-accelerated graph processing frameworks address this issue by managing the active subgraph transfer at runtime. Some frameworks adopt explicit transfer management approaches based on explicit memory copy with filter or compaction. In contrast, others adopt implicit transfer management approaches based on on-demand accesses with the zero-copy mechanism or unified virtual memory. Having made intensive analysis, we find that as the active vertices evolve, the performance of the two approaches varies in different workloads. Due to heavy redundant data transfers, high CPU compaction overhead, or low bandwidth utilization, adopting a single approach often results in suboptimal performance. Moreover, these methods lack effective cache management methods to address the irregular and sparse memory access pattern of graph processing. In this work, we propose a hybrid transfer management approach that takes the merits of both two transfer approaches at runtime. Moreover, we present an efficient vertex-centric graph caching framework that minimizes CPU-GPU communication by caching frequently accessed graph data at runtime. Based on these techniques, we present HytGraph, a GPU-accelerated graph processing framework, which is empowered by a set of effective task-scheduling optimizations to improve performance. Experiments on real-world and synthetic graphs show that HytGraph achieves average speedups of 2.5 ×, 5.0 ×, and 2.0 × compared to the state-of-the-art GPU-accelerated graph processing systems, Grus, Subway, and EMOGI, respectively.

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.

Deep entity resolution (ER) identifies matching entities across data sources using techniques based on deep learning. It involves two steps: a blocker for identifying the potential matches to generate the candidate pairs, and a matcher for accurately distinguishing the matches and non-matches among these candidate pairs. Recent deep ER approaches utilize pretrained language models (PLMs) to extract similarity features for blocking and matching, achieving state-of-the-art performance. However, they often fail to balance the consensus and discrepancy between the blocker and matcher, emphasizing the consensus while neglecting the discrepancy. This paper proposes MutualER, a deep entity resolution framework that integrates and jointly trains the blocker and matcher, balancing both the consensus and discrepancy between them. Specifically, we firstly introduce a lightweight PLM in siamese structure for the blocker and a heavier PLM in cross structure or an autoregressive large language model (LLM) for the matcher. Two optimization techniques named Mutual Sample Selection (MSS) and Similarity Knowledge Transferring (SKT) are designed to jointly train the blocker and matcher. MSS enables the blocker and matcher to mutually select the customized training samples for each other to maintain the discrepancy, while SKT allows them to share the similarity knowledge for improving their blocking and matching capabilities respectively to maintain the consensus. Extensive experiments on five datasets demonstrate that MutualER significantly outperforms existing PLM-based and LLM-based approaches, achieving leading performance in both effectiveness and efficiency.

With the rising proliferation of blockchain systems and applications, choosing the appropriate blockchains to deploy applications is critical to achieving optimal performance. Evaluation frameworks provide a systematic approach to assessing and comparing different blockchain systems, guiding application developers to choose the most suitable one. However, existing evaluation frameworks still have limitations that affect their accuracy. First, most frameworks utilize workloads initially de-signed for traditional databases, which fail to capture the unique characteristics and requirements of blockchain systems. Second, these frameworks fail to generate correct results under heavy workloads due to their imbalanced task processing algorithms. Third, existing frameworks are tailored only for non-sharding blockchain architectures, limiting their ability to evaluate diverse blockchains. This paper introduces Hammer, a general blockchain evaluation framework that addresses the above limitations. It consists of two key components: workload prediction and asynchronous task processing. Workload prediction accurately predicts real-world workload trends by expanding the scope of temporal control sequences, providing a more realistic evaluation of blockchain performance. Asynchronous task processing handles heavy-load situations, enabling accurate evaluation of blockchain performance. Extensive experiments on various blockchains under Smallbank workload empower application developers to make informed decisions about blockchain selection and optimization.

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.

Enhancing the efficiency of iterative computation on graphs has garnered considerable attention in both industry and academia. Nonetheless, the majority of efforts focus on expediting iterative computation by minimizing the running time per iteration step, ignoring the optimization of the number of iteration rounds, which is a crucial aspect of iterative compu-tation. We experimentally verified the correlation between the vertex processing order and the number of iterative rounds, thus making it possible to reduce the number of execution rounds for iterative computation. In this paper, we propose a graph reordering method, GoGraph, which can construct a well-formed vertex processing order effectively reducing the number of iteration rounds and, consequently, accelerating iterative computation. Before delving into GoGraph, a metric function is introduced to quantify the efficiency of vertex processing order in accelerating iterative computation. This metric reflects the quality of the processing order by counting the number of edges whose source precedes the destination. GoGraph employs a divide-and-conquer mindset to establish the vertex processing order by maximizing the value of the metric function. Our experimental results show that GoGraph outperforms current state-of-the-art reordering algorithms by 1.83 x on average (up to 3.34 x) in runtime. Compared with traditional synchronous computation, our method improves the iterative computations up to 6.30 x in runtime.

The growing volume of graph data may exhaust the main memory. It is crucial to design a disk-based graph storage system to ingest updates and analyze graphs efficiently. However, existing dynamic graph storage systems suffer from read or write amplification and face the challenge of optimizing both read and write performance simultaneously. To address this challenge, we propose LSMGraph, a novel dynamic graph storage system that combines the write-friendly LSM-tree and the read-friendly CSR. It leverages the multi-level structure of LSM-trees to optimize write performance while utilizing the compact CSR structures embedded in the LSM-trees to boost read performance. LSMGraph uses a new memory structure, MemGraph, to efficiently cache graph updates and uses a multi-level index to speed up reads within the multi-level structure. Furthermore, LSMGraph incorporates a vertex-grained version control mechanism to mitigate the impact of LSM-tree compaction on read performance and ensure the correctness of concurrent read and write operations. Our evaluation shows that LSMGraph significantly outperforms state-of-the-art (graph) storage systems on both graph update and graph analytical workloads.

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.

An efficient data structure is fundamental to meeting the growing demands in dynamic graph processing. However, the dual requirements for graph computation efficiency (with contiguous structures) and graph update efficiency (with linked list-like structures) present a conflict in the design principles of graph structures. After experimental studies of state-of-the-art dynamic graph structures, we observe that the overhead of cache misses accounts for a major portion of the graph computation time. This paper presents GastCoCo, a system with graph storage and coroutine-based prefetch co-design. By employing software prefetching via stackless coroutines and designing a prefetch-friendly data structure CBList, GastCoCo significantly alleviates the performance degradation caused by cache misses. Our results show that GastCoCo outperforms state-of-the-art graph storage systems by 1.3× - 180× in graph updates and 1.4× - 41.1× in graph computation.

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.

Nowadays, studies on energy-efficient datacenters, especially the DataCenters powered by Renewable Energy mix (DCRE), have gained great attention. DCREs are large-scale, geo-distributed, and equipped with on-site renewable energy generators. For these features, it is expensive to perform empirical evaluations of proposed algorithms and solutions on the real-world DCREs, while the state-of-the-art datacenter simulators are not applicable for DCREs. In this paper, we present CloudSimPer (CLOUD SIMulator hybrid-Powered by rEnewable eneRgy), a general-purpose simulator that comprehensively supports the simulation of DCREs. Besides the functions such as renewable energy, geo-distribution, and long-term simulation, we also design evaluation metrics and an integrated simulation case for experimental studies in the future. The main challenge of CloudSimPer lies in designing a new model and software layer upon CloudSim, to solve the complexity of traceable and comparable simulations which connect renewable energies, datacenters, workloads, regions, and schedulers. We use the term schedulers broadly, encompassing any optimization approaches on DCREs for energy saving. We prove CloudSimPer and integrated case to be valid, so that simulation results are scientifically sound, by examining the expectation and the simulation results, and comparing the simulation results with selected competitors. CloudSimPer offers simulation services to datacenter designers, datacenter administrators, and academics.

Iterative graph processing is widely used as a significant paradigm for large-scale data analysis. In many global businesses of multinational enterprises, graph-structure data is usually geographically distributed in different regions to support low-latency services. Geo-distributed graph processing suffers from the Wide Area Networks (WANs) with scarce and heterogeneous bandwidth, thus essentially differs from traditional distributed graph processing. In this paper, we propose RAGraph, aRegion-Aware framework for geo-distributedgraphprocessing. At the core of RAGraph, we design a region-aware graph processing framework that allows advancing inefficient global updates locally and enables sensible coordination-free message interactions and flexible replaceable communication module. In terms of graph data preprocessing, RAGraph introduces a contribution-driven edge migration algorithm to effectively utilize network resources. RAGraph also contains an adaptive hierarchical message interaction engine to switch interaction modes adaptively based on network heterogeneity and fluctuation, and a discrepancy-aware message filtering strategy to filter important messages. Experimental results show that RAGraph can achieve an average speedup of 9.7× (up to 98×) and an average WAN cost reduction of 78.5$\%$(up to 97.3$\%$) compared with state-of-the-art systems.

Deep Entity Matching (EM) is one of the core research topics in data integration. Typical existing works construct EM models by training deep neural networks (DNNs) based on the training samples with onehot labels. However, these sharp supervision signals of onehot labels harm the generalization of EM models, causing them to overfit the training samples and perform badly in unseen datasets. To solve this problem, we first propose that the challenge of training a well-generalized EM model lies in achieving the compromise between fitting the training samples and imposing regularization, i.e., the bias-variance tradeoff. Then, we propose a novel Soft Target-EnhAnced Matching (Steam) framework, which exploits the automatically generated soft targets as label-wise regularizers to constrain the model training. Specifically, Steam regards the EM model trained in previous iteration as a virtual teacher and takes its softened output as the extra regularizer to train the EM model in the current iteration. As such, Steam effectively calibrates the obtained EM model, achieving the bias-variance tradeoff without any additional computational cost. We conduct extensive experiments over open datasets and the results show that our proposed Steam outperforms the state-of-the-art EM approaches in terms of effectiveness and label efficiency.

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.

Processing large graphs with memory-limited GPU needs to resolve issues of host-GPU data transfer, which is a key performance bottleneck. Existing GPU-accelerated graph processing frameworks reduce the data transfers by managing the active subgraph transfer at runtime. Some frameworks adopt explicit transfer management approaches based on explicit memory copy with filter or compaction. In contrast, others adopt implicit transfer management approaches based on on-demand access with zero-copy or unified-memory. Having made intensive analysis, we find that as the active vertices evolve, the performance of the two approaches varies in different workloads. Due to heavy redundant data transfers, high CPU compaction overhead, or low bandwidth utilization, adopting a single approach often results in suboptimal performance.In this work, we propose a hybrid transfer management approach to take the merits of both the two approaches at runtime, with an objective to achieve the shortest execution time in each iteration. Based on the hybrid approach, we present HyTGraph, a GPU-accelerated graph processing framework, which is empowered by a set of effective task scheduling optimizations to improve the performance. Our experimental results on real-world and synthesized graphs demonstrate that HyTGraph achieves up to 10.27X speedup over existing GPU-accelerated graph processing systems including Grus, Subway, and EMOGI.

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.

Real-world graphs are constantly evolving, which demands updates of the previous analysis results to accommodate graph changes. By using the memoized previous computation state, incremental graph computation can reduce unnecessary recomputation. However, a small change may propagate over the whole graph and lead to large-scale iterative computations. To address this problem, we propose Layph, a two-layered graph framework. The upper layer is a skeleton of the graph which is much smaller than the original graph, and the lower layer has some disjoint subgraphs. Layph limits costly global iterative computations on the original graph to the small graph skeleton and a few subgraphs updated with the input graph changes. In this way, many vertices and edges are not involved in iterative computations, which significantly reduces the computation overhead and improves the performance of incremental graph processing. Our experimental results show that Layph outperforms current state-of-the-art incremental graph systems by 9.08× on average (up to 36.66×) in response time.

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.

Multinational enterprises conduct global business that has a demand for geo-distributed transactional databases. Existing state-of-the-art databases adopt a sharded master-follower replication architecture. However, the single-master serving mode incurs massive cross-region writes from clients, and the sharded architecture requires multiple round-trip acknowledgments (e.g., 2PC) to ensure atomicity for cross-shard transactions. These limitations drive us to seek yet another design choice. In this paper, we propose a strongly consistent OLTP database GeoGauss with full replica multi-master architecture. To efficiently merge the updates from different master nodes, we propose a multi-master OCC that unifies data replication and concurrent transaction processing. By leveraging an epoch-based delta state merge rule and the optimistic asynchronous execution, GeoGauss ensures strong consistency with light-coordinated protocol and allows more concurrency with weak isolation, which are sufficient to meet our needs. Our geo-distributed experimental results show that GeoGauss achieves 7.06X higher throughput and 17.41X lower latency than the state-of-the-art geo-distributed database CockroachDB on the TPC-C benchmark.

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%.

In many global businesses of multinational enterprises, graph-structure data is usually geographically distributed in different regions to support low-latency services. Geo-distributed graph processing suffers from the Wide Area Networks (WANs) with scarce and heterogeneous bandwidth, thus essentially differs from traditional distributed graph processing. In this paper, we propose RAGraph, a Region-Aware framework for geo-distributed graph processing. At the core of RAGraph, we design a region-aware graph processing framework that allows advancing inefficient global updates locally and enables sensible coordination-free message interactions. RAGraph also contains an adaptive hierarchical message interaction engine to switch interaction modes adaptively based on network heterogeneity and fluctuation, and a discrepancy-aware message filtering strategy to filter important messages. Finally, the experiments show that RAGraph can achieve 1.69X - 40.53X speedup and 20.9% - 97% WAN cost reduction compared with state-of-the-art systems.

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.

The sparseness and incompleteness of knowledge graphs (KGs) trigger considerable interest in enhancing the representation learning with external corpora. However, the difficulty of aligning entities and relations with external corpora leads to inferior performance improvement. Open knowledge graphs (OKGs) consist of entity-mentions and relation-mentions that are represented by noncanonicalized freeform phrases, which generally do not rely on the specification of ontology schema. The roughness of the nonontological construction method leads to a specific characteristic of OKGs: diversity, where multiple entity-mentions (or relation-mentions) have the same meaning but different expressions. The diversity of OKGs can provide potential textual and structural features for the representation learning of KGs. We speculate that leveraging OKGs to enhance the representation learning of KGs can be more effective than using pure text or pure structure corpora. In this paper, we propose a newOERL,Open knowledge graphEnhancedRepresentationLearning of KGs. OERL automatically extracts textual and structural connections between KGs and OKGs, models and transfers refined profitable features to enhance the representation learning of KGs. The strong performance improvement and exhaustive experimental analysis prove the superiority of OERL over state-of-the-art baselines.

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.

Learning rate is one of the most important hyper-parameters that has significant influence for neural network training. Learning rate schedules are widely used in real practice to adjust the learning rate according to pre-defined schedules for the fast convergence and good generalization. However, existing learning rate schedules are all heuristic algorithms and lack theoretical support. Therefore, people usually choose the learning rate schedules through multiple ad-hoc trial, and the obtained learning rate schedules are sub-optimal. To boost the performance of the obtained sub-optimal learning rate schedule, we propose a generic learning rate schedule plugin, called LEArning Rate Perturbation (LEAP), which can be applied to various learning rate schedules to improve the model training by introducing a certain perturbation to the learning rate. We found that, with such simple yet effective strategy, training processing exponentially favors flat minima rather than sharp minima with guaranteed convergence, which leads to better generalization ability. In addition, we conduct extensive experiments which show that training with LEAP can improve the performance of various deep learning models on diverse datasets using various learning rate schedules (including constant learning rate).

Mobility data collected from location-based social networks are imperative for user movement behaviour analysis and marketing strategy customization. However, due to personal privacy and temporary failure of GPS devices, mobility data suffer from missing data issues. The missing mobility data hide beneficial information that can lead to distorted data analysis. To this end, we propose a multi-task generative adversarial network, termed as MDI-MG, to mitigate the negative impact of missing mobility data by imputing possible missing records. Specifically, in MDI-MG, we first introduce region-awareness modelling to fully capture sequential dependencies. Then, the generator is designed as a multi-task network, which unifies two highly pertinent tasks, including the primary task and the auxiliary missing POI region imputation task. The joint training on the two tasks enhances presentation capabilities and brings additional benefits. Besides, we adopt a discriminator to evaluate the generated sequences. The generator and the discriminator are optimized with a minimax two-player game. Experiments on two real-world datasets show that, MDI-MG achieves better performance in terms of both imputation accuracy and effectiveness, compared with state-of-the-art methods.

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.

Compared to other language tasks, applying pre-trained language models (PLMs) for search ranking often requires more nuances and training signals. In this paper, we identify and study the two mismatches between pre-training and ranking fine-tuning: the training schema gap regarding the differences in training objectives and model architectures, and the task knowledge gap considering the discrepancy between the knowledge needed in ranking and that learned during pre-training. To mitigate these gaps, we propose Pre-trained, Prompt-learned and Pre-finetuned Neural Ranker (P3 Ranker). P3 Ranker leverages prompt-based learning to convert the ranking task into a pre-training like schema and uses pre-finetuning to initialize the model on intermediate supervised tasks. Experiments on MS MARCO and Robust04 show the superior performances of P3 Ranker in few-shot ranking. Analyses reveal that P3 Ranker is able to better accustom to the ranking task through prompt-based learning and retrieve necessary ranking-oriented knowledge gleaned in pre-finetuning, resulting in data-efficient PLM adaptation. Our code is available at https://github.com/NEUIR/P3Ranker.

GNN's training needs to resolve issues of vertex dependencies, i.e., each vertex representation's update depends on its neighbors. Existing distributed GNN systems adopt either a dependencies-cached approach or a dependencies-communicated approach. Having made intensive experiments and analysis, we find that a decision to choose one or the other approach for the best performance is determined by a set of factors, including graph inputs, model configurations, and an underlying computing cluster environment. If various GNN trainings are supported solely by one approach, the performance results are often suboptimal. We study related factors for each GNN training before its execution to choose the best-fit approach accordingly. We propose a hybrid dependency-handling approach that adaptively takes the merits of the two approaches at runtime. Based on the hybrid approach, we further develop a distributed GNN training system called NeutronStar, which makes high performance GNN trainings in an automatic way. NeutronStar is also empowered by effective optimizations in CPU-GPU computation and data processing. Our experimental results on 16-node Aliyun cluster demonstrate that NeutronStar achieves 1.81X-14.25X speedup over existing GNN systems including DistDGL and ROC.

Abstract Similarity searches on heterogeneous information networks (HINs) have attracted wide attention from both industrial and academic areas in recent years; for example, they have been used for friend detection in social networks and collaborator recommendation in coauthor networks. The structural information on the HIN can be captured by multiple metapaths, and people usually utilize metapaths to design methods for similarity search. The rich semantics in HINs are not only structural information but also content stored in nodes. However, the content similarity of nodes was usually not valued in the existing methods. Although some researchers have recently considered both types of information in machine learning-based methods for similarity search, they have used structure and content information separately. To address this issue by balancing the influence of structure and content information flexibly in the process of searching, we propose a double channel convolutional neural network model for top-k similarity search, which uses path instances as model inputs and generates structure and content embeddings for nodes based on different metapaths. We design an attention mechanism to enhance the differences in metapaths for each node. Another attention mechanism is used to combine the content and structure information of nodes. Finally, an importance evaluation function is designed to improve the accuracy and make the model more explainable. The experimental results show that our search algorithm can effectively support top-k similarity search in HINs and achieve higher performance than existing approaches.

We study the problem of self-supervised and interpretable data cleaning, which automatically extracts interpretable data repair rules from dirty data. In this paper, we propose a novel framework, namely Garf, based on sequence generative adversarial networks (SeqGAN). One key information Garf tries to capture is data repair rules (for example, if the city is "Dothan", then the county should be "Houston"). Garf employs a SeqGAN consisting of a generator G and a discriminator D that trains G to learn the dependency relationships ( e.g. , given a city value "Dothan" as input, the county can be determined as "Houston"). After training, the generator G can be used to generate data repair rules, but may contain both trusted and untrusted rules, especially when learning from dirty data. To mitigate this problem, Garf further updates the learned relationships with another discriminator D' to iteratively improve the quality of both rules and data. Garf takes advantages of both logical and learning-based methods, which allow cleaning dirty data with high interpretability and have no requirements for prior knowledge and training data. Extensive experiments on real-world and synthetic datasets demonstrate the effectiveness of Garf. Garf achieves new state-of-the-art data cleaning result with high accuracy, through learning from dirty datasets without human supervision.

Blockchain serves as a replicated transactional processing system in a trustless distributed environment. Existing blockchain systems all rely on an explicit ordering step to determine the global order of transactions that are collected from multiple peers. The ordering consensus can be the bottleneck since it must be Byzantine-fault tolerant and can scarcely benefit from parallel execution. In this paper, we propose an ordering-free architecture that makes ordering implicit through deterministic execution. Based on this novel architecture, we develop a permissioned blockchain system NeuChain. A number of key optimizations such as asynchronous block generation and pipelining are leveraged for high throughput and low latency. Several security mechanisms are also designed to make our system robust to malicious attacks. Our geo-distributed experimental results show that NeuChain can achieve 47.2--64.1X throughput improvement over HyperLedger Fabric and 1.6--12.2X throughput improvement over the state-of-the-art high performance blockchains.

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.

Currently, in addition to the performance, the energy consumption (hereinafter EC) of jobs running in a big data processing system is also of interest to academia and industry because it grows rapidly as an increasing amount of data is processed. Many studies focus on the EC optimization of jobs from the perspective of computation, which is specific to the algorithms in each job. However, the part of EC involved in I/O operations, which is general and universal, is mostly ignored in optimization. In this paper, we concentrate on the EC optimization of jobs from the perspective of I/O operations. To save energy, we argue that data compression could be exploited. On one hand, energy is saved by processing compressed data with less I/O cost. On the other hand, extra EC is incurred from the necessary data compression/decompression process, which may offset the saved energy. Therefore, there are tradeoffs to consider when determining whether to compress data for these jobs. In this paper, such tradeoffs and boundary conditions are studied. We first abstract a paradigm for the runtime environment of big data processing jobs. Then, we establish the power, jobs, compression, and I/O models in detail. Based on these models, we discuss the compression tradeoffs and derive the boundary conditions for EC optimization. Finally, we design and conduct experiments to validate our proposition. The experimental results confirm that the tradeoffs and boundary conditions exist for typical jobs in MapReduce and Spark. As explained, first, the EC of a job is reduced using data compression. Second, whether or not such optimization occurs is related to the specification of both the compression algorithm and the job and is determined by corresponding boundary conditions. Third, for a compression algorithm, the larger its compression/decompression speed and the better its compression ratio, the more likely it is to achieve EC optimization.

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.

The ever-growing amount of dynamic graph data demands efficient techniques of incremental graph processing. However, incremental graph algorithms are challenging to develop. Existing approaches usually require users to manually design nontrivial incremental operators, or choose different memoization strategies for certain specific types of computation, limiting the usability and generality. In light of these challenges, we propose Ingress, an automated system for incremental graph processing. Ingress is able to incrementalize batch vertex-centric algorithms into their incremental counterparts as a whole, without the need of redesigned logic or data structures from users. Underlying Ingress is an automated incrementalization framework equipped with four different memoization policies, to support all kinds of vertex-centric computations with optimized memory utilization. We identify sufficient conditions for the applicability of these policies. Ingress chooses the best-fit policy for a given algorithm automatically by verifying these conditions. In addition to the ease-of-use and generalization, Ingress outperforms state-of-the-art incremental graph systems by 15.93X on average (up to 147.14X) in efficiency.

Informative representation of road networks is essential to a wide variety of applications on intelligent transportation systems. In this article, we design a new learning framework, called Representation Learning for Road Networks (RLRN), which explores various intrinsic properties of road networks to learn embeddings of intersections and road segments in road networks. To implement the RLRN framework, we propose a new neural network model, namely Road Network to Vector (RN2Vec), to learn embeddings of intersections and road segments jointly by exploring geo-locality and homogeneity of them, topological structure of the road networks, and moving behaviors of road users. In addition to model design, issues involving data preparation for model training are examined. We evaluate the learned embeddings via extensive experiments on several real-world datasets using different downstream test cases, including node/edge classification and travel time estimation. Experimental results show that the proposed RN2Vec robustly outperforms existing methods, including (i) Feature-based methods : raw features and principal components analysis (PCA); (ii) Network embedding methods : DeepWalk, LINE, and Node2vec; and (iii) Features + Network structure-based methods : network embeddings and PCA, graph convolutional networks, and graph attention networks. RN2Vec significantly outperforms all of them in terms of F1-score in classifying traffic signals (11.96% to 16.86%) and crossings (11.36% to 16.67%) on intersections and in classifying avenue (10.56% to 15.43%) and street (11.54% to 16.07%) on road segments, as well as in terms of Mean Absolute Error in travel time estimation (17.01% to 23.58%).

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.

Prioritized computation is shown promising performance for a large class of graph algorithms. It prioritizes the execution of some vertices that play important roles in determining convergence. For large-scale distributed graph processing, graph partitioning is an important preprocessing step that aims to balance workload and to reduce communication costs between workers. However, existing graph partitioning methods are designed for round-robin synchronous distributed frameworks. They balance workload without distinction of vertex importance and fail to consider the characteristics of priority-based scheduling, which may limit the benefit of prioritized graph computation. In this article, to accelerate prioritized iterative graph computations, we propose Hotness Balanced Partition (HBP). In prioritized graph computation, high priority vertices are likely to be executed more frequently and are likely to pass more messages, which result in hot vertices. Based on this observation, we partition graph by distributing vertices with distinction according to their hotness rather than blindly distributing vertices with equal weights, aiming to evenly distribute the hot vertices among workers. We further provide two HBP algorithms: a streaming-based algorithm for efficient one-pass processing and a distributed algorithm for distributed processing. Our results show that our proposed partitioning methods outperform the state-of-the-art partitioning methods, Fennel, HotGraph, and SNE.

Existing graph partition methods are designed for round-robin synchronous distributed frameworks. They balance workload without discrimination of vertex importance and fail to consider the characteristics of priority-based scheduling, which may limit the benefit of prioritized graph computation. To accelerate prioritized iterative graph computations, we propose Hotness Balanced Partition (HBP) and a stream-based partition algorithm Pb-HBP. Pb-HBP partitions graph by distributing vertices with discrimination according to their hotness rather than blindly distributing vertices with equal weights, which aims to evenly distribute the hot vertices among workers. Our results show that our proposed partition method outperforms the state-of-the-art partition methods, Fennel and HotGraph. Specifically, Pb-HBP can reduce 40-90% runtime of that by hash partition, 5-75% runtime of that by Fennel, and 22-50% runtime of that by HotGraph.

Finding a team that is both competent in performing the task and compatible in working together has been extensively studied. However, most methods for team formation tend to rely on a set of skills only. In order to solve this problem, we present an efficient team formation method based on Constrained Pattern Graph (called CPG). Unlike traditional methods, our method takes into account both structure constraints and communication constraints on team members, which can better meet the requirements of users. First, a CPG preprocessing method is proposed to normalize a CPG and represent it as a CoreCPG in order to establish the basis for efficient matching. Second, a Communication Cost Index (called CCI) is constructed to speed up the matching between a CPG and its corresponding social network. Third, a CCI-based node matching algorithm is proposed to minimize the total number of intermediate results. Moreover, a set of incremental maintenance strategies for the changes of social networks are proposed. We conduct experimental studies based on two real-world social networks. The experiments demonstrate the effectiveness and the efficiency of our proposed method in comparison with traditional methods.

In database and large-scale data analytics, recursive aggregate processing plays an important role, which is generally implemented under a framework of incremental computing and executed synchronously and/or asynchronously. We identify three barriers in existing recursive aggregate data processing. First, the processing scope is largely limited to monotonic programs. Second, checking on conditions for monotonicity and correctness for async processing is sophisticated and manually done. Third, execution engines may be suboptimal due to separation of sync and async execution. In this paper, we lay an analytical foundation for conditions to check if a recursive aggregate program that is monotonic or even non-monotonic can be executed incrementally and asynchronously with its correct result. We design and implement a condition verification tool that can automatically check if a given program satisfies the conditions. We further propose a unified sync-async engine to execute these programs for high performance. To integrate all these effective methods together, we have developed a distributed Datalog system, called PowerLog. Our evaluation shows that PowerLog can outperform three representative Datalog systems on both monotonic and non-monotonic recursive programs.

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.

Column-oriented stores, known for their scalability and flexibility, are a common NoSQL database implementation and are increasingly used in big data management. In column-oriented stores, a “full-scan” query strategy is inefficient and the search space can be reduced if data is well partitioned or indexed; however, there is no pre-defined schema for building and maintaining partitions and indexes at lower cost. We leverage an accumulative and high-dimensional data model, a sophisticated linearization algorithm, and an efficient query algorithm, to solve the challenge of how a pre-defined and well-partitioned data model can be applied to flexible and time-varied key-value data. We adapt a high-dimensional array as the data model to partition the key-value data without additional storage and massive calculation; improve the Z-order linearization algorithm, which map multidimensional data to one dimension while preserving locality of the data points, for flexibility; efficiently build an expansion mechanism for the data model to support time-varied data. The result is Haery, a column-oriented store, based on a distributed file system and computing framework. In experiments, Haery is compared with Hive, HBase, Cassandra, MongoDB, PostgresXL, and HyperDex in terms of query performance. With results indicating Haery on average performs 4.57x, 4.23x, 3.55x, 1.79x, 1.82x, and 120.6x faster, respectively.

Road network is a basic component of intelligent transportation systems (ITS) in smart city. Informative representation of road networks is important as it is essential to a wide variety of ITS applications. In this paper, we propose a neural network representation learning model, namely Intersection of Road Network to Vector (IRN2Vec), to learn embeddings of road intersections that encode rich information in a road network by exploring geo-locality and intrinsic properties of intersections and moving behaviors of road users. In addition to model design, several issues unique to IRN2Vec, including data preparation for model training and various relationships among intersections, are examined. We evaluate the learned embeddings via extensive experiments on three real-world datasets using three downstream test cases, including prediction of traffic signals and crossings on intersections and travel time estimation. Experimental results show that the proposed IRN2Vec outperforms three existing methods, DeepWalk, LINE and Node2vec, in terms of F1-score in predicting traffic signals (22.21% to 23.84%) and crossings (8.65% to 11.65%), and mean absolute error (MAE) in travel time estimation (9.87% to 19.28%).

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.

Local differential privacy (LDP) is a recently proposed privacy standard for collecting and analyzing data, which has been used, e.g., in the Chrome browser, iOS and macOS. In LDP, each user perturbs her information locally, and only sends the randomized version to an aggregator who performs analyses, which protects both the users and the aggregator against private information leaks. Although LDP has attracted much research attention in recent years, the majority of existing work focuses on applying LDP to complex data and/or analysis tasks. In this paper, we point out that the fundamental problem of collecting multidimensional data under LDP has not been addressed sufficiently, and there remains much room for improvement even for basic tasks such as computing the mean value over a single numeric attribute under LDP. Motivated by this, we first propose novel LDP mechanisms for collecting a numeric attribute, whose accuracy is at least no worse (and usually better) than existing solutions in terms of worst-case noise variance. Then, we extend these mechanisms to multidimensional data that can contain both numeric and categorical attributes, where our mechanisms always outperform existing solutions regarding worst-case noise variance. As a case study, we apply our solutions to build an LDP-compliant stochastic gradient descent algorithm (SGD), which powers many important machine learning tasks. Experiments using real datasets confirm the effectiveness of our methods, and their advantages over existing solutions.

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.

A mobile operating system often needs to collect frequent new terms from users in order to build and maintain a comprehensive dictionary. Collecting keyboard usage data, however, raises privacy concerns. Local differential privacy (LDP) has been established as a strong privacy standard for collecting sensitive information from users. Currently, the best known solution for LDP-compliant frequent term discovery transforms the problem into collecting n-grams under LDP, and subsequently reconstructs terms from the collected n-grams by modelling the latter into a graph, and identifying cliques on this graph. Because the transformed problem (i.e., collecting n-grams) is very different from the original one (discovering frequent terms), the end result has poor utility. Further, this method is also rather expensive due to clique computation on a large graph. In this paper we tackle the problem head on: our proposal, PrivTrie, directly collects frequent terms from users by iteratively constructing a trie under LDP. While the methodology of building a trie is an obvious choice, obtaining an accurate trie under LDP is highly challenging. PrivTrie achieves this with a novel adaptive approach that conserves privacy budget by building internal nodes of the trie with the lowest level of accuracy necessary. Experiments using real datasets confirm that PrivTrie achieves high accuracy on common privacy levels, and consistently outperforms all previous methods.

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.

Nowadays, people prefer to take part in multiple social networks to enjoy different kinds of services. Consequently, a significant task is to identify users across networks. Most state-of-the-art works on this issue exploit user local structure features (e.g., friend, follow and followed). In this paper, we first proposes the notion of user global view features, which represent the location of users in the network. Then, we present an iterative two-stage algorithm (GAUI) using Global view features with user Attribute features to solve User Identification. In GAUI, we iteratively update pairwise similarity and predict new matching users. Certainly, we present a community based core anchor link filter strategy to reduce the computation cost, and present a stable matching based mapping strategy to improve the accuracy. At last, the experiments conducted on two real-world aligned networks demonstrate that our method has better performance on precision and recall.

With the volume of data grows rapidly, the cost of detecting duplication entities has increased significantly in data cleaning. However, some real-time applications only need to identify as many duplicate entities as possible in a limited time, rather than all of them. The existing works adopt the sorting method to divide similar records into blocks, and arrange the processing order of blocks to detect duplicate entity progressively. However, this method only works well when the attributes of records are suitable for sorting. Therefore, this paper proposes a novel progressive de-duplicate method for records that can't be sorted by their attributes. The method distributes records into different blocks based on their features and generates a modified bloom filter index for each block. Then it uses the bloom filter to predict the probability of duplicate entities in this block, which determines the processing order of blocks to detect the duplicate entities more quickly. The comprehensive experiment shows that the number of duplicate detection by this algorithm in the finite time is far more efficient than other algorithms involved in the related works.

The influence of spatial position means how deep it affects the spatial objects and can be measured by the number of affected spatial objects. The evaluation of spatial position influence which widely used in architectural planning and facility location is a typical study in the spatial database. In previous studies, a spatial object was supposed to affect only one spatial position, the influence of the object calculated by the number of the space objects in the area. However, the spatial object can affect many spatial positions and the effects are multiple. In this study, we provide a new evaluation model based on RkNN. A new measurement method was proposed by calculating the weight of the contribution based on the distance between the space object and the space position. The new measurement method makes the model more suitable for the practical application. In addition, a location algorithm was proposed based on the RkNN influence evaluation model. The algorithm can solve the problem such as making the facilities to provide the best service to the customers and using each facility effectively. The influence of each facility is calculated in this algorithm and the rationality of the location scheme is evaluated by equilibrium coefficient, the smaller the equilibrium coefficient, the more reasonable the scheme. The location algorithm based on the new model shows a better performance in the practical application, it contributes to the more reasonable and effective facility location.

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.

Density Peaks (DP) is a recently proposed clustering algorithm that has distinctive advantages over existing clustering algorithms. It has already been used in a wide range of applications. However, DP requires computing the distance between every pair of input points, therefore incurring quadratic computation overhead, which is prohibitive for large data sets. In this paper, we propose an efficient distributed algorithm LSHDDP, which is an approximate algorithm that exploits Locality Sensitive Hashing. We present formal analysis of LSH-DDP, and show that the approximation quality and the runtime can be controlled by tuning the parameters of LSH-DDP. Experimental results on both a local cluster and EC2 show that LSH-DDP achieves a factor of 1.7-70x speedup over the näıve distributed DP implementation and 2x speedup over the state-of-the-art EDDPC approach, while returning comparable cluster results.

The process of matching and integrating records that relate to the same entity from one or more datasets is known as record linkage, and it has become an increasingly important subject in many application areas, including business, government and health system. The data from these areas often contain sensitive information. To prevent privacy breaches, ideally records should be linked in a private way such that no information other than the matching result is leaked in the process, and this technique is called privacy-preserving record linkage (PPRL). With the increasing data, scalability becomes the main challenge of PPRL, and many private blocking techniques have been developed for PPRL. They are aimed at reducing the number of record pairs to be compared in the matching process by removing obvious non-matching pairs without compromising privacy. However, most of them are designed for two databases and they vary widely in their ability to balance competing goals of accuracy, efficiency and security. In this paper, we propose a novel private blocking approach for PPRL based on dynamic k -anonymous blocking and Paillier cryptosystem which can be applied on two or multiple databases. In dynamic k -anonymous blocking, our approach dynamically generates blocks satisfying k -anonymity and more accurate values to represent the blocks with varying k . We also propose a novel similarity measure method which performs on the numerical attributes and combines with Paillier cryptosystem to measure the similarity of two or more blocks in security, which provides strong privacy guarantees that none information reveals even collusion. Experiments conducted on a public dataset of voter registration records validate that our approach is scalable to large databases and keeps a high quality of blocking. We compare our method with other techniques and demonstrate the increases in security and accuracy.

Stream clustering is a fundamental problem in many streaming data analysis applications. Comparing to classical batch-mode clustering, there are two key challenges in stream clustering: (i) Given that input data are changing continuously, how to incrementally update their clustering results efficiently? (ii) Given that clusters continuously evolve with the evolution of data, how to capture the cluster evolution activities? Unfortunately, most of existing stream clustering algorithms can neither update the cluster result in real-time nor track the evolution of clusters. In this paper, we propose a stream clustering algorithm EDMStream by exploring the Evolution of Density Mountain. The density mountain is used to abstract the data distribution, the changes of which indicate data distribution evolution. We track the evolution of clusters by monitoring the changes of density mountains. We further provide efficient data structures and filtering schemes to ensure that the update of density mountains is in real-time, which makes online clustering possible. The experimental results on synthetic and real datasets show that, comparing to the state-of-the-art stream clustering algorithms, e.g., D-Stream, DenStream, DBSTREAM and MR-Stream, our algorithm is able to response to a cluster update much faster (say 7-15x faster than the best of the competitors) and at the same time achieve comparable cluster quality. Furthermore, EDMStream successfully captures the cluster evolution activities.

Along with the proliferation of online digital map and location-based service, very large POI (point of interest) databases have been constructed where a record corresponds to a POI with information including name, category, address, geographical location and other features. A basic spatial query in POI database is POI retrieval. In many scenarios, a user cannot provide enough information to pinpoint the POI except some clue. For example, a user wants to identify a caf é in a city visited many years ago. SHe cannot remember the name and address but she still recalls that "the caf é is about 200 meters away from a restaurant; and turning left at the restaurant there is a bakery 500 meters away, etc.". Intuitively, the clue, even partial and approximate, describes the spatio-textual context around the targeted POI. Motivated by this observation, this work investigates clue-based spatio-textual query which allows user providing clue, i.e., some nearby POIs and the spatial relationships between them, in POI retrieval. The objective is to retrieve k POIs from a POI database with the highest spatio-textual context similarities against the clue. This work has deliberately designed data-quality-tolerant spatio-textual context similarity metric to cope with various data quality problems in both the clue and the POI database. Through crossing valuation, the query accuracy is further enhanced by ensemble method. Also, this work has developed an index called roll-out-star R-tree (RSR-tree) to dramatically improve the query processing efficiency. The extensive tests on data sets from the real world have verified the superiority of our methods in all aspects.

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].

As new data and updates are constantly arriving, the results of data mining applications become stale and obsolete over time. Incremental processing is a promising approach to refresh mining results. It utilizes previously saved states to avoid the expense of re-computation from scratch. In this paper, we propose i2MapReduce, a novel incremental processing extension to MapReduce. Compared with the state-of-the-art work on Incoop, i2MapReduce (i) performs key-value pair level incremental processing rather than task level re-computation, (ii) supports not only one-step computation but also more sophisticated iterative computation, and (iii) incorporates a set of novel techniques to reduce I/O overhead for accessing preserved fine-grain computation states. Experimental results on Amazon EC2 show significant performance improvements of i2MapReduce compared to both plain and iterative MapReduce performing re-computation.

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.

Density Peaks (DP) is a recently proposed clustering algorithm that has distinctive advantages over existing clustering algorithms. It has already been used in a wide range of applications. However, DP requires computing the distance between every pair of input points, therefore incurring quadratic computation overhead, which is prohibitive for large data sets. In this paper, we study efficient distributed algorithms for DP. We first show that a naive MapReduce solution (Basic-DDP) has high communication and computation overhead. Then, we propose LSH-DDP, an approximate algorithm that exploits Locality Sensitive Hashing for partitioning data, performs local computation, and aggregates local results to approximate the final results. We address several challenges in employing LSH for DP. We leverage the characteristics of DP to deal with the fact that some of the result values cannot be directly approximated in local partitions. We present formal analysis of LSH-DDP, and show that the approximation quality and the runtime can be controlled by tuning the parameters of LSH-DDP. Experimental results on both a local cluster and EC2 show that LSH-DDP achieves a factor of 1.7-70x speedup over the naive Basic-DDP and 2x speedup over the state-of-the-art EDDPC approach, while returning comparable cluster results. Compared to the popular K-means clustering, LSH-DDP also has comparable or better performance. Furthermore, LSH-DDP could achieve even higher efficiency with a lower accuracy requirement.

Roles, their emotion, and interactions between them are three key elements for semantic content understanding of movies. In this paper, we proposed a novel movie summarization method to capture the semantic content in movies based on a string of IE-RoleNets. An IE-RoleNet (interaction and emotion rolenet) models the emotion and interactions of roles in a shot of the movie. The whole movie is represented as a string of IE-RoleNets. Summarization of a movie is transformed into finding an optimal substring with user-specified summarization ratio. Hierarchical substring mining is conducted to find an optimal substring of the whole movie. We have conducted objective and subjective experiments on our method. Experimental results show the ability of our method to capture the semantic content of movies.

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.

As new data and updates are constantly arriving, the results of data mining applications become stale and obsolete over time. Incremental processing is a promising approach to refreshing mining results. It utilizes previously saved states to avoid the expense of re-computation from scratch. In this paper, we propose i2MapReduce, a novel incremental processing extension to MapReduce, the most widely used frameworkfor mining big data. Compared with the state-of-the-art work on Incoop, i2MapReduce (i) performs key-value pair level incremental processing rather than task level re-computation, (ii) supports not only one-step computation but also more sophisticated iterative computation, which is widely used in data mining applications, and (iii) incorporates a set of novel techniques to reduce I/O overhead for accessing preserved fine-grain computation states. We evaluate i2MapReduce using a one-step algorithm and four iterative algorithms with diverse computation characteristics. Experimental results on Amazon EC2 show significant performance improvements of i2MapReduce compared to both plain and iterative MapReduce performing re-computation.

NoSQL database (NoSQL DB) covers the shortage of traditional database and has been widely used in recent years. Currently, researches on NoSQL DB mainly focus on performance issues, few of them are about energy consumption (EC) evaluation and optimization. Waiting Energy Consumption (WEC) is another critical reason causing energy waste besides computer idleness. Study the WEC regularities of NoSQL DB facilitates achieving real "green computing". This paper first analyzes the model and measurement approaches of EC, then designs test cases to study the WEC regularities, finally proposes approaches of "reducing WEC" for EC optimization. Plenty of experiments show that, despite that NoSQL DB is an application of "green cloud computing", the ECs of selected NoSQL DBs are widely divergent, and some of them remain to be further optimized.

Many challenging problems could be better solved by exploiting crowdsourcing platforms than traditional machine-based methods. However, data quality in crowdsourcing applications has become a crucial aspect since crowdsourcing workers may have different capabilities. In this paper, we propose a novel weighted aggregation rule (WAR) to improve the result accuracy in crowdsourcing systems. According to the agreement of answers given by the workers, we classify all the tasks into the high-agreement tasks and low-agreement tasks. For the high-agreement tasks, we use simple majority voting to select the correct answer while ensuring the result accuracy. For the low-agreement tasks, we adopt weighted majority voting strategy, which assigns a weight for each worker according to his performance on the high-agreement tasks. We evaluate the effectiveness of our proposed method using three real-world datasets on AMT. The experimental results show that our method achieves excellent result accuracy.

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.

Most previous work on cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very unpredictable. However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, while still maintaining almost as good average-case performance as LRU. In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics do not match MRU well. As our main technical contribution, we propose a new cache hit/miss classification, k -Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide k -Miss memory accesses. A remarkable feature of our analysis is that the k -Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits the advantages in efficiency and precision of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with instruction caches show that our proposed MRU analysis has both good precision and high efficiency, and the obtained estimated WCET is rather close to (typically 1%∼8% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for cache replacement policies in real-time systems.

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.

Extensive experiments have validated the effectiveness of the corpus-based method for classifying the word's sentiment polarity.However, no work is done for comparing different corpora in the polarity classification task.Nowadays, Twitter has aggregated huge amount of data that are full of people's sentiments.In this paper, we empirically evaluate the performance of different corpora in sentiment similarity measurement, which is the fundamental task for word polarity classification.Experiment results show that the Twitter data can achieve a much better performance than the Google, Web1T and Wikipedia based methods.

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.

This paper examines the importance of non-topological node attributes for link prediction in social networks. Rank method and supervised learning method were introduced to show the role of the node attributes in link prediction respectively. A rule for choosing the appropriate node attributes was discussed and a method for aggregating two node attributes was proposed. The result of the experiments on a blog dataset showed that using non-topological node attributes make a better performance in link prediction.

Determing matching schemas enables queries on heterogeneous data space to be formulated and facilitates data integration. Current schema matching techniques most focus on mining mappings using elements' own information. This paper proposes to introduce semantic and functional dependencies into matching process to achieve multilayer schema matching results. It calculates semantic similarity with the help of Word Net and generates candidate mapping sets. By introducing functional dependency to formulize structural information, it can get structural similarities between element pairs. A probabilistic factor is considered to select mapping pairs. Through experimental evaluation on real data, the superiority of our method is verified.

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.

Differential privacy (DP) is a promising scheme for releasing the results of statistical queries on sensitive data, with strong privacy guarantees against adversaries with arbitrary background knowledge. Existing studies on DP mostly focus on simple aggregations such as counts. This paper investigates the publication of DP-compliant histograms, which is an important analytical tool for showing the distribution of a random variable, e.g., hospital bill size for certain patients. Compared to simple aggregations whose results are purely numerical, a histogram query is inherently more complex, since it must also determine its structure, i.e., the ranges of the bins. As we demonstrate in the paper, a DP-compliant histogram with finer bins may actually lead to significantly lower accuracy than a coarser one, since the former requires stronger perturbations in order to satisfy DP. Moreover, the histogram structure itself may reveal sensitive information, which further complicates the problem. Motivated by this, we propose two novel algorithms, namely Noise First and Structure First, for computing DP-compliant histograms. Their main difference lies in the relative order of the noise injection and the histogram structure computation steps. Noise First has the additional benefit that it can improve the accuracy of an already published DP-complaint histogram computed using a naiive method. Going one step further, we extend both solutions to answer arbitrary range queries. Extensive experiments, using several real data sets, confirm that the proposed methods output highly accurate query answers, and consistently outperform existing competitors.

Future embedded real-time systems will be deployed on multi-core processors to meet the dramatically increasing high-performance and low-power requirements. This trend appeals to generalize established results on uniprocessor scheduling, particularly the various utilization bounds for schedulability test used in system design, to the multiprocessor setting. Recently, this has been achieved for the famous Liu and Lay land utilization bound by applying novel task splitting techniques. However, parametric utilization bounds that can guarantee higher utilizations (up to 100%) for common classes of systems are not yet known to be generalizable to multiprocessors as well. In this paper, we solve this problem for most parametric utilization bounds by proposing new task partitioning algorithms based on exact response time analysis. In addition to the worst-case guarantees, as the exact response time analysis is used for task partitioning, our algorithms significantly improve average-case utilization over previous work.

Most previous work in cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very "unpredictable". However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, but still maintaining almost as good average-case performance as LRU. In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics, originally designed for LRU, do not match MRU well. As our main technical contribution, we propose a new cache hit/miss classification, k-Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide the k-Miss memory accesses. A remarkable feature of our analysis is that the k-Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits all the advantages in efficiency, precision and composability of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with benchmarks show that the estimated WCET by our proposed MRU analysis is rather close to (5% # 20% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for the cache replacement policy in real-time systems.

The graph structure is a very important means to model schemaless data with complicated structures, such as protein-protein interaction networks, chemical compounds, knowledge query inferring systems, and road networks. This paper focuses on the index structure for similarity search on a set of large sparse graphs and proposes an efficient indexing mechanism by introducing the Q-Gram idea. By decomposing graphs to small grams (organized by κ-Adjacent Tree patterns) and pairing-up on those κ-Adjacent Tree patterns, the lower bound estimation of their edit distance can be calculated for candidate filtering. Furthermore, we have developed a series of techniques for inverted index construction and online query processing. By building the candidate set for the query graph before the exact edit distance calculation, the number of graphs need to proceed into exact matching can be greatly reduced. Extensive experiments on real and synthetic data sets have been conducted to show the effectiveness and efficiency of the proposed indexing mechanism.

This paper proposes a relation extraction model based on semantic pattern matching in Web environment. It consists of frequent pattern extraction, pattern clustering based on density, and pattern matching based on semantic similarity. First, based on the entities with known relations in a limited training set, we extract relation patterns containing these named entities from the web page. Then the relations between entities from the web page in specific areas can be extracted based on these relation patterns extracted. Experiments show the affectivity and the self-adaptive of our method on extracting relations between entities from dynamic web environment.

Keyword search is a wildly popular way for querying XML document. However, the increasing volume of XML data poses new challenges to keyword search processing. Parallel database is an efficient solution for this problem. In this paper, we study the problem of effective keyword search for SLCA (Smallest lower common ancestor) in parallel XML databases. We propose two efficient algorithm SONB (Scan once with no buffer) and MSOP (Merge strategy based on ordered partition) to compute the SLCA efficiently in the parallel environment. We have performed an extensive experimental study and the results show that our proposed approach achieves high efficiency for the keyword search.

This paper proposes and solves a novel type of spatial queries named Subject-oriented Top-k hot Region (STR) queries. Given a subject S defined by a feature set R and features importance denoted by weights, an STR query retrieves k non-overlapping regions that have the highest scores computed by the number of feature objects and their weights. As an example, the culture subject is defined by exhibition halls, libraries and museums. On the subject, an STR query finds cultural centers intensively distributed feature objects. In this paper, we propose two efficient algorithms, single-partition (SP) algorithm and dual-partition (DP) algorithm, to process STR queries. Extensive experiments evaluate the proposed solutions under a wide range of parameter settings.

As Deep Web contains tremendous well-structured data sources, how to integrate data sources in Deep Web has become a hotspot in current research. Accurately discovering and identifying Deep Web data sources related to a specific domain become key issues. We propose a Domain-Oriented Deep Web data source Discovery method (DO-DWD) and a novel Domain Identification strategy of Deep Web data sources (DIDW). In the discovery stage, we use machine learning algorithms and some heuristic rules to find query interfaces of the data sources; In the identification stage, we identify Deep Web data sources associated with the domain by calculating the relevance between a query interface and the domain based on semantic similarity. Finally, we have extensive experiments on a real data set showing that DO-DWD and DIDW are of high correctness and accuracy.

Because the amount of information contained on the Deep Web is much larger than the surface web, how to use it well has become a popular problem to research. When a query is sent to a deep web resource and the data sources return few results or even no result, a proper query relaxation solution should be adopted to get more satisfactory results to users. In this paper, such a query relaxation solution is presented. First, it solves the problem of relaxing attributes which contain multiple key words by value. That is, such attributes are not simply removed in the relaxation, but the query values of the attributes are modified. Second, when a data source returns many result pages, instead of getting all the pages, it evaluates the quality of the results in the current page to decide whether to send another query to fetch the next page. Thus, the number of query times is reduced. Finally, the experimental results demonstrate that both the result quality and the query efficiency are improved.

Liu and Layland discovered the famous utilization bound for fixed-priority scheduling on single processor systems in the 1970's. Since then, it has been a long standing open problem to find fixed-priority scheduling algorithms with the same bound for multiprocessor systems. In this paper, we present a partitioning-based fixed-priority multiprocessor scheduling algorithm with Liu and Layland's utilization bound.

It is predicted that multicores will be increasingly used in future embedded real-time systems for high performance and low energy consumption. The major obstacle is that we may not predict and provide any guarantee on real-time properties of software on such platforms. The shared memory bus is among the most critical resources, which severely degrade the timing predictability of multicore software due to the access contention between cores. In this paper, we study a multicore architecture where each core has a local L1 cache and all cores use a shared bus to access the off-chip memory. We use Abstract Interpretation (AI) to analyze the local cache behavior of a program running on a dedicated core. Based on the cache analysis, we construct a Timed Automaton (TA) to model when the programs access the memory bus. Then we model the shared bus also using timed automata. The TA models for the bus and programs will be explored using the UPPAAL model checker to find the WECTs for the respective programs. Based on the presented techniques, we have developed a tool for multicore timing analysis, which allows automatic generation of the TA models from binary code and WCET estimation for any given TA model of the shared bus. Extensive experiments have been conducted, showing that the combined approach can significantly tighten the estimations. As examples, we have studied the TDMA and FCFS buses, of which the WCET bounds can be tightened by up to 240% and 82% respectively, compared with the worst-case bounds estimated based on worst-case bus access delay.

Probabilistic data is coming as a new deluge along with the technical advances on geographical tracking, multimedia processing, sensor network and RFID. While similarity search is an important functionality supporting the manipulation of probabilistic data, it raises new challenges to traditional relational database. The problem stems from the limited effectiveness of the distance metric supported by the existing database system. On the other hand, some complicated distance operators have proven their values for better distinguishing ability in the probabilistic domain. In this paper, we discuss the similarity search problem with the Earth Mover's Distance , which is the most successful distance metric on probabilistic histograms and an expensive operator with cubic complexity. We present a new database approach to answer range queries and k-nearest neighbor queries on probabilistic data, on the basis of Earth Mover's Distance. Our solution utilizes the primal-dual theory in linear programming and deploys B + tree index structures for effective candidate pruning. Extensive experiments show that our proposal dramatically improves the scalability of probabilistic databases.

Synchronous dataflow (SDF) is a well-known model of computation for dataflow-oriented applications such as embedded systems for signal processing and multimedia. It is important to minimize the buffer size requirements of applications generated from SDF graphs, since memory space is often a scarce resource in these systems due to cost or power consumption constraints. Some authors have proposed to use model-checking for finding the minimum buffer size requirements, but the scalability of model-checking is limited by state space explosion. In this paper, we present several techniques for reducing state space size and improving scalability of model-checking by exploiting problem-specific properties of SDF graphs.

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 major obstacle to use multicores for real-time applications is that we may not predict and provide any guarantee on real-time properties of embedded software on such platforms; the way of handling the on-chip shared resources such as L2 cache may have a significant impact on the timing predictability. In this paper, we propose to use cache space isolation techniques to avoid cache contention for hard real-time tasks running on multicores with shared caches. We present a scheduling strategy for real-time tasks with both timing and cache space constraints, which allows each task to use a fixed number of cache partitions, and makes sure that at any time a cache partition is occupied by at most one running task. In this way, the cache spaces of tasks are isolated at run-time.

Recently, there have been several promising techniques developed for schedulability analysis and response time analysis for multiprocessor systems based on over-approximation. This paper contains two contributions. First, to improve the analysis precision, we apply Baruah's window analysis framework to response time analysis for poradic tasks on multiprocessor systems where the deadlines of tasks are within their periods. The crucial observation is that for global fixed priority scheduling, a response time bound of each task can be efficiently estimated by fixed-point computation without enumerating all the busy window sizes as in for schedulability analysis. The technique is proven to dominate theoretically state-of-the-art techniques for response time analysis for multiprocessor systems. Our experiments also show that the technique results in significant performance improvement compared with several existing techniques for multiprocessor schedulability analysis. As the second main contribution of this paper, we extend the proposed technique to task systems with arbitrary deadlines, allowing tasks to have deadlines beyond the end of their periods. This is a non-trivial extension even for single-processor systems. To our best knowledge, this is the first work of response time analysis for multiprocessor systems in this setting, which involves sophisticated techniques for the characterization and computation of response time bounds.

Static path analysis is a key process of Worst Case Execution Time (WCET) estimation, the objective of which is to find the execution path that has the largest execution time. Currently, there is an argument in the research community whether model checking is another good solution for WCET analysis, besides ILP. To our knowledge, no paper so far has addressed this argument with real performance data. In this paper, we implement both ILP and model checking for static path analysis of WCET, and the experiment results show that ILP yields very good performance, while model checking only works well for simple programs, and it is inclined to scalability problems when dealing with programs that have complex structures and large loop counts.

Data Grids primarily deal with providing services and infrastructure for distributed data-intensive applications, in which schema matching is a key technology for supporting dynamic data integration. Against the limitations of existed schema matching methods and with the aim of reducing the amount of user effort as much as possible, a novel approach to schema matching called SMM is proposed based on schema structure information and known matching knowledge, in which neural network influence procedure is imitated to realize semantic matching and reasoning, known matching knowledge is reused to supplement the matching and reasoning. At last, the experiment results show that SMM is feasible.

As Moore's law comes to an end, multi-processor (MP) systems are becoming increasingly important in embedded systems design, hence real-time schedulability analysis for MP systems has become an important research topic. In this paper, we present an exact method for schedulability analysis of global multiprocessor scheduling with either fixed-priority (FP) or earliest-deadline-first (EDF) algorithms using the model-checker NuSMV. Compared to safe but pessimistic schedulability tests based on processor utilization bounds, model-checking can provide an exact answer to the schedulability of a taskset, as well as quantitative information on each task's best-case and worst- case response times.

We study the schedulability analysis problem for nonpreemptive scheduling algorithms on multiprocessors. To our best knowledge, the only known work on this problem is the test condition proposed by Baruah for non-preemptive EDF scheduling, which will reject a task set with arbitrarily low utilization if it contains a task whose execution time is equal or greater than the minimal relative deadline among all tasks. In this paper, we firstly derive a linear-time test condition which avoids the problem mentioned above, by building upon previous work for preemptive multiprocessor scheduling. This test condition works on not only non-preemptive EDF, but also any other work-conserving non-preemptive scheduling algorithms. Then we improve the analysis and present test conditions of pseudo-polynomial time-complexity for Non-preemptive Earliest Deadline First scheduling and Non-preemptive Fixed Priority scheduling respectively. Experiments with randomly generated task sets show that our proposed test conditions, especially the improved test conditions, have significant performance improvements compared with [BAR-EDFnp].

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.

With the rapid growth of Web databases, it's necessary to extract and integrate large-scale data available in deep Web automatically. But current Web search engines conduct page-level ranking, which are becoming inadequate for entity-oriented vertical search. In this paper, we present an entity-level ranking mechanism called LG-ERM for deep Web query based on local scoring and global aggregation. Unlike traditional approaches, LG-ERM considers more rank influencing factors including the uncertainty of entity extraction, the style information of entities and the importance of Web sources, as well as the entity relationship. By combining local scoring and global aggregation in ranking, the query result can be more accurate and effective to meet users' needs. The experiments demonstrate the feasibility and effectiveness of the key techniques of LG-ERM.

To access the large-scale data sources efficiently and automatically, it is necessary to classify these data sources into different domains and categories. In this paper, we propose a novel classification approach to classify data sources into detail domain subjects by query probing. In our approach, we train sample instances for each subject category and use them to probe the data scale of each source and category. And then we build a matrix to classify a data source into one or more subject categories and develop a decision algorithm based on probing iteration to rectify the classification result. Our experiments over real deep web sources show that our approach can achieve higher accuracy across a variety of data sources.

On the analysis of current state of aeroengine remote diagnosis, collaborative mechanism based on multi-agent was introduced to overcome the obstacles of conventional remote fault diagnosis. The model of aeroengine remote collaborative diagnosis based on multi-agent was put forward on analysis of the positional relationship of all agents in the collaborative environment and the relationship between collaborative agents and roles in the course of collaboration. Some key technologies such as coordination mechanism, task assignment mechanism, agent interaction mechanism, case-based reasoning (CBR) in treatment agent, and the analytic hierarchy process (AHP) in decision analysis were discussed and specific methods of realization were given concretely. Based on these, a Web-based prototype system for aeroengine fault diagnosis was developed on the JADE (Java Agent DEvelopment Framework) platform. The process of system implementation and a case example of fault diagnosis were presented to illustrate and prove the proposed system's applicability. Running results show the feasibility and reliability of the framework, which will be helpful to integrate the aeroengine diagnosis knowledge, improve the diagnosis efficiency effectively and decrease the aeroengine diagnosis cost remarkably.

Clustering is a popular technique for analyzing microarray data sets, with n genes and m experimental conditions. As explored by biologists, there is a real need to identify coregulated gene clusters, which include both positive and negative regulated gene clusters. The existing pattern-based and tendency-based clustering approaches cannot directly be applied to find such coregulated gene clusters, because they are designed for finding positive regulated gene clusters. In this paper, in order to cluster coregulated genes, we propose a coding scheme that allows us to cluster two genes into the same cluster if they have the same code, where two genes that have the same code can be either positive or negative regulated. Based on the coding scheme, we propose a new algorithm for finding maximal subspace coregulated gene clusters with new pruning techniques. A maximal subspace coregulated gene cluster clusters a set of genes on a condition sequence such that the cluster is not included in any other subspace coregulated gene clusters. We conduct extensive experimental studies. Our approach can effectively and efficiently find maximal subspace coregulated gene clusters. In addition, our approach outperforms the existing approaches for finding positive regulated gene clusters.

Field Programmable Gate Arrays (FPGAs) are very popular in today's embedded systems design, and Partial Runtime-Reconfigurable (PRTR) FPGAs allow HW tasks to be placed and removed dynamically at runtime. Hardware task scheduling on PRTR FPGAs brings many challenging issues to traditional real-time scheduling theory, which have not been adequately addressed by the research community compared to software task scheduling on CPUs. In this article, we consider the schedulability analysis problem of HW task scheduling on PRPR FPGAs. We derive utilization bounds for several variants of global preemptive/nonpreemptive EDF scheduling, and compare the performance of different utilization bound tests.

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.

A database grid can provide a robust distributed environment for accessing and manipulating different database resources. While current challenges focus on managing database resources and ensuring the quality of data integration. This paper describes a service level agreement (SLA) based data integration model, which includes SLA-based resource description model, SLA-based query model, SLA-based matching algorithm and SLA-based evaluation model. The SLAs of a database resource is defined by SLA-based resource description model. The SLA-based query model is defined to normalize the various types of queries. The SLA-based matching algorithm has been proposed to match schemas of resources for each sub-query, and then the quality of database resources is evaluated by SLA-based evaluation model to obtain the final query solutions. Experimental results have shown that SLA-based data integration model can provide more stable database resources and save time cost in data integration applications as well.

Similarity-based time series retrieval has been a subject of long term study due to its wide usage in many applications, such as financial data analysis, weather data forecasting, and multimedia data retrieval. Its original task was to find those time series similar to a pattern (query) time series data, where both the pattern and data time series are static. Recently, with an increasing demand on stream data management, similarity-based stream time series retrieval has raised new research issues due to its unique requirements during the stream processing, such as one-pass search and fast response. In this paper, we address the problem of matching patterns over high-speed stream time series data. We will develop a novel representation, called multi-scaled segment mean (MSM), for stream time series data, which can be incrementally computed and thus perfectly adapted to the stream characteristics. Most importantly, we propose a novel multi-step filtering mechanism over the multi-scaled representation. Analysis indicates that the mechanism can greatly prune the search space and thus offer fast response. Extensive experiments show the multi-scaled representation together with the multi-step filtering scheme can efficiently filter out false candidates and detect patterns, compared to the multiscaled wavelet.

Reconfigurable devices, such as field programmable gate arrays (FPGAs), are very popular in today's embedded systems design due to their low-cost, high-performance and flexibility. Partially runtime-reconfigurable (PRTR) FPGAs allow hardware tasks to be placed and removed dynamically at runtime. Hardware task scheduling on PRTR FPGAs brings many challenging issues to traditional real-time scheduling theory, which have not been adequately addressed by the research community compared to software task scheduling on CPUs. In this paper, we consider the schedulability analysis problem of HW task scheduling on PRPR FPGAs. We derive utilization bound tests for two variants of global EDF scheduling, and use synthetic tasksets to compare performance of the tests to existing work and simulation results.

In this paper, we address the problem of static scheduling and software synthesis for dataflow graphs with the symbolic model-checker NuSMV using a two-step process: first use model-checking to obtain a static schedule with the objective of minimizing the data buffer size, then synthesize efficient code from the static schedule with the objective of minimizing code size and performance overheads due to runtime dynamic decisions. We show the effectiveness of these techniques using a number of digital signal processing examples.

Searching for approximate repetitions in a DNA sequence has been an important topic in gene analysis. One of the problems in the study is that because of the varying lengths of patterns, the similarity between patterns cannot be judged accurately if we use only the concept of ED (edit distance). In this paper we shall use the function similar to compute similarity, which considers both the difference and sameness between patterns at the same time. Seeing the computational complexity, we shall also propose a new distance PFD (partition frequency distance) and design a new filter based on PFD, with which we can sort out candidate set of approximate repetitions efficiently. We use SUA instead of sliding window to get the fragments in a DNA sequence, so that the patterns of an approximate repetition have no limitation on length. The results show that with this technique we are able to find a bigger number of approximate repetitions than that of those found with tandem repeat finder

Currently, pattern-based and tendency-based models are very popular for clustering co-regulated genes. In this paper, we propose another novel model, namely g-Cluster. The proposed model has the following advantages: (1) find positive and negative co-regulated genes in a shot, (2) get away from the restriction of magnitude transformation relationship among genes, and (3) guarantee quality of clusters and significance of regulations using a novel similarity measurement gCode and two user-specified thresholds, called wave constraint threshold and regulation threshold respectively. We also design a novel tree-based clustering algorithm, FBTD, combined with efficient pruning rules to identify all maximal g-Clusters. The extensive experiments on real and synthetic datasets show that (1) our algorithm can effectively and efficiently find an amount of co-regulated gene clusters missed by previous models, which are potentially of high biological significance, and (2) our algorithm is superior to the existing approaches

The Web services composition plays a more and more important role in SOA environment nowadays. Composing Web services on user's demand proves to be essential for both B2B and B2C applications. However, existing composition approaches and services composition description languages, such as BPEL4WS, are insufficient for satisfying user requirements. In this paper, we present an approach for Web services composition on demand. Our approach defines a description language for describing user's demand and supporting dynamic services binding for flexible service composition, and applies SLA to service discovery that can automatically adapt the change of QoS constraints. The description language can be applied to any process-oriented composition language that supports executable business processes. Finally, our approach is applied to a service grid system where it provides a fully automatic, stable service composition on user's demand

In data publishing, if the data is published carelessly, public users could use common knowledge to infer more information from the published data, causing leakage of sensitive information. To address related research challenges, we develop a system called XGuard, which can help data owners publish a partial XML document without leaking sensitive information, even if public users can do inference. Specifically, the system has the following functionalities. i) It allows the data owner to define sensitive information and specify common knowledge as XML constraints. ii) Given a partial document, the system can validate if the document can cause information leakage due to common knowledge and how much data can be leaked. iii) The system can help the data owner interactively analyze the data inference and produce a secure valid partial document using the algorithms.

XML is emerging as a major standard for representing data on the World Wide Web. Recently, many XML storage models have been proposed to manage XML data. In order to assess an XML database's abilities to deal with XML queries, several benchmarks have also been proposed, including XMark and XMach. However, no reported studies using those benchmarks were found that can provide users with insights on the impacts of a variety of storage models on XML query performance. In this article, we report our first set of results on benchmarking a set of XML database implementations using two XML benchmarks. The selected implementations represent a wide range of approaches, including RDBMS-based systems with document-independent and document-dependent XML-relational schema mapping approaches, and XML native engines based on an Object-Oriented Model and the Document Object Model. Comprehensive experiments were conducted to study relative performance of different approaches and the important issues that affect XML query performance, such as path expression query processing, effectiveness of various partitioning, label-path, and indexing structures.