Multimodal recommendation combines the user historical behaviors with the modal features of items to capture the tangible user preferences, presenting superior performance compared to the conventional ID-based recommender systems. However, existing methods still encounter two key problems in the representation learning of users and items, respectively: (1) the initialization of multimodal user representations is either agnostic to historical behaviors or contaminated by irrelevant modal noise, and (2) the widely used KNN-based item-item graph contains noisy edges with low similarities and lacks audience co-occurrence relationships. To address such issues, we propose MLLMRec, a novel preference reasoning paradigm with graph refinement for multimodal recommendation. Specifically, on the one hand, the item images are first converted into high-quality semantic descriptions using a multimodal large language model (MLLM), thereby bridging the semantic gap between visual and textual modalities. Then, we construct a behavioral description list for each user and feed it into the MLLM to reason about the purified user preference profiles that contain the latent interaction intents. On the other hand, we develop the threshold-controlled denoising and topology-aware enhancement strategies to refine the suboptimal item-item graph, thereby improving the accuracy of item representation learning. Extensive experiments on three publicly available datasets demonstrate that MLLMRec achieves the state-of-the-art performance with an average improvement of 21.48% over the optimal baselines. The source code is provided at https://github.com/Yuzhuo-Dang/MLLMRec.

Scene Text Recognition (STR) is challenging in extracting effective character representations from visual data when text is unreadable. Permutation language modeling (PLM) is introduced to refine character predictions by jointly capturing contextual and visual information. However, in PLM, the use of random permutations causes training fit oscillation, and the iterative refinement (IR) operation also introduces additional overhead. To address these issues, this paper proposes the Hierarchical Attention autoregressive Model with Adaptive Permutation (HAAP) to enhance position-context-image interaction capability, improving autoregressive LM generalization. First, we propose Implicit Permutation Neurons (IPN) to generate adaptive attention masks that dynamically exploit token dependencies, enhancing the correlation between visual information and context. Adaptive correlation representation helps the model avoid training fit oscillation. Second, the Cross-modal Hierarchical Attention mechanism (CHA) is introduced to capture the dependencies among position queries, contextual semantics and visual information. CHA enables position tokens to aggregate global semantic information, avoiding the need for IR. Extensive experimental results show that the proposed HAAP achieves state-of-the-art (SOTA) performance in terms of accuracy, complexity, and latency on several datasets.

Dynamic link prediction aims to predict the future links in dynamic graphs. Existing generative dynamic link prediction studies utilize the global degree distribution for mitigating the over-estimation problem, which can model the time-invariant features while neglecting the time-varying features, resulting in capturing inaccurate evolution patterns. However, such time related features are intrinsically coupled, which makes simultaneously and independently modeling both features infeasible. Motivated by these issues, we propose a Time-wise causal debiasing framework (Tide) for generative dynamic link prediction, which does not resort to any extra trainable modules. Instead, to obtain the time-invariant features, we first utilize a time-invariant deconfounded learning mechanism for decoupling the prediction score with the degree distribution. To leverage the time-varying features, we intervene in the model during the inference stage by a predicted future degree distribution, aiming to make the accurate predictions for dynamic graphs. Experiments conducted on four public datasets under both inductive and transductive settings present that our Tide enhanced models can outperform their corresponding vanilla versions by up to 21.42% and 27.73% in terms of NDCG and Jaccard, respectively.

Video Scene Graph Generation (VidSGG) aims to capture dynamic relationships among entities by sequentially analyzing video frames and integrating visual and semantic information. However, VidSGG is challenged by significant biases that skew predictions. To mitigate these biases, we propose a VIsual and Semantic Awareness (VISA) framework for unbiased VidSGG. VISA addresses visual bias through memory-enhanced temporal integration that enhances object representations and concurrently reduces semantic bias by iteratively integrating object features with comprehensive semantic information derived from triplet relationships. This visual-semantics dual debiasing approach results in more unbiased representations of complex scene dynamics. Extensive experiments demonstrate the effectiveness of our method, where VISA outperforms existing unbiased VidSGG approaches by a substantial margin (e.g., +13.1% improvement in mR@20 and mR@50 for the SGCLS task under Semi Constraint).

Dynamic link prediction aims to predict the future links on dynamic graphs, which can be applied to wide scenarios such as recommender systems and social networks on the World Wide Web. Existing methods mainly (1) focus on the in-graph learning, which cannot generalize to graphs unobserved during training; or (2) achieve the cross-graph predictions in a many-many mechanism by training on multiple graphs across various domains, which results in a large computational cost. In this paper, we propose a cross-graph dynamic link predictor named CrossDyG, which achieves the cross-graph transferability in a one-many mechanism which trains on one single source graph and test on different target graphs. Specifically, we provide causal and empirical analysis on the structural bias caused by the graph-specific structural characteristics in cross-graph predictions. Then, we conduct deconfounded training to learn the universal network evolution pattern from one single source graph during training. Finally, we apply the causal intervention to leverage the graph-specific structural characteristics of each target graph during inference. Extensive experiments conducted on three benchmark data of dynamic graphs demonstrate that CrossDyG outperforms the state-of-the-art baselines by up to 11.01% and 17.02% in terms of AP and AUC, respectively. In addition, the improvements are especially significant when training on small source graphs.

Dynamic graph link prediction is widely utilized in the complex web of the real world, such as social networks, citation networks, recommendation systems, etc. Recent Transformer-based link prediction methods on dynamic graphs not only fail to model the fine-grained structures such as triangles with the vanilla Transformers in the graph serialization process, but also amplify the imbalanced distribution of graphs because of their over-estimation of high-degree nodes. To tackle these issues, we propose a Topology-aware Transformer on Dynamic Graph (TopDyG) for link prediction, consisting of a topology injected Transformer (Ti-Transformer) and a mutual information learning (Mi-Learning). The Ti-Transformer explores the explicit structure of serialized graphs, capturing the topological features. The Mi-Learning mines the relationship between nodes by modeling the mutual information with a prior knowledge, alleviating the over-estimation of high-degree nodes when applying the Transformer-based models for the dynamic graph link prediction task. Extensive experiments on four public datasets containing both transductive and inductive settings present the superiority of our proposal. In particular, TopDyG presents an improvement of 43.27% and 28.75% against the state-of-the-art baselines in terms of NDCG and Jaccard, respectively. The advantages are especially obvious on the high-density graphs.

Determining dense feature points on fingerprints used in constructing deep fixed-length representations for accurate matching, particularly at the pixel level, is of significant interest. To explore the interpretability of fingerprint matching, we propose a multi-stage interpretable fingerprint matching network, namely Interpretable Fixed-length Representation for Fingerprint Matching via Vision Transformer (IFViT), which consists of two primary modules. The first module, an interpretable dense registration module, establishes a Vision Transformer (ViT)-based Siamese Network to capture long-range dependencies and the global context in fingerprint pairs. It provides interpretable dense pixel-wise correspondences of feature points for fingerprint alignment and enhances the interpretability in the subsequent matching stage. The second module takes into account both local and global representations of the aligned fingerprint pair to achieve an interpretable fixed-length representation extraction and matching. It employs the ViTs trained in the first module with the additional fully connected layer and retrains them to simultaneously produce the discriminative fixed-length representation and interpretable dense pixel-wise correspondences of feature points. Extensive experimental results on diverse publicly available fingerprint databases demonstrate that the proposed framework not only exhibits superior performance on dense registration and matching but also significantly promotes the interpretability in deep fixed-length representations-based fingerprint matching.

Link prediction on temporal networks aims to predict the future edges by modeling the dynamic evolution involved in the graph data. Previous methods relying on the node/edge attributes or the distance on the graph structure are not practical due to the deficiency of the attributes and the limitation of the explicit distance estimation, respectively. Moreover, the existing graph representation learning methods mostly rely on graph neural networks (GNNs), which cannot adequately take the dynamic correlations between nodes into consideration, leading to the generating of inferior node embeddings. Thus, we propose a time-aware graph (TAG) learning method for link prediction on temporal networks. We first conduct a theoretical causal analysis proving that the correlations between nodes are required to be unchanged for the temporal graph representation learning using GNNs. Then, we model the recent dynamic node correlations by designing an edge-dropping (ED) module and adopting a recent neighbor sampling (RNS) strategy so as to approximate the above condition. Besides, we also preserve the long-term stable node correlations by introducing additional self-supervisions using the contrastive learning. Comprehensive experiments were conducted on four public temporal network datasets, i.e., MathOverflow, StackOverflow, AskUbuntu, and SuperUser, demonstrate that TAG can achieve state-of-the-art performance in terms of average precision (AP) and area under the ROC curve (AUC). In addition, TAG can ensure high computational efficiency by making the temporal graph lightweight, letting it be practical in real-world applications.

Inductive link prediction on temporal networks aims to predict the future links associated with node(s) unseen in the historical timestamps. Existing methods generate the predictions mainly by learning node representation from the node/edge attributes as well as the network dynamics or by measuring the distance between nodes on the temporal network structure. However, the attribute information is unavailable in many realistic applications and the structure-aware methods highly rely on nodes' common neighbors, which are difficult to accurately detect, especially in sparse temporal networks. Thus, we propose a distance-aware learning (DEAL) approach for inductive link prediction on temporal networks. Specifically, we first design an adaptive sampling method to extract temporal adaptive walks for nodes, increasing the probability of including the common neighbors between nodes. Then, we design a dual-channel distance measuring component, which simultaneously measures the distance between nodes in the embedding space and on the dynamic graph structure for predicting future inductive edges. Extensive experiments are conducted on three public temporal network datasets, i.e., MathOverflow, AskUbuntu, and StackOverflow. The experimental results validate the superiority of DEAL over the state-of-the-art baselines in terms of accuracy, area under the ROC curve (AUC), and average precision (AP), where the improvements are especially obvious in scenarios with only limited data.

Dynamic graph learning on temporal networks aims to understand the continuous evolution pattern of networks, with an important application on forecasting the future temporal network. Existing methods mainly focus on modeling the structural and temporal features, with recent research interest shifting toward considering the structural correlations between nodes through their neighbor co-occurrences. Though satisfactory performance has been achieved, there still remain several limitations: (1) the deviation of investigated scenarios from real-world applications, since most previous researches concentrate on special cases of multigraphs with abundant repeat edges; (2) the insufficient computational efficiency of modeling the structural features, since the existing neighbor co-occurrence scheme fails to consider explicit structural correlations between nodes and suffers from a time-consuming pairwise encoding strategy; (3) the unsatisfying prediction accuracy due to inadequate modeling of temporal features, since each neighbor’s historical temporal features and the temporal domain shifting with network evolving are both neglected. To solve these issues, we first focus on the general scenarios of temporal networks without abundant repeat edges for approaching the actual applications and propose an efficient and effective dynamic graph learning method named LightDyG. Specifically, (1) on the one hand, to increase the computational efficiency, LightDyG decouples the structural correlations between nodes and their individual substructures for fast convergence based on the analysis of existing co-occurrence mechanism, and further designs an incremental strategy for efficient structural encoding; (2) on the other hand, to improve the prediction accuracy, the temporal characteristics are considered by including both the interaction and appearance timestamps of neighbors, and a time-invariant temporal encoding strategy is designed to eliminate the temporal bias introduced by the network evolution. Extensive experiments conducted on four public temporal networks demonstrate that LightDyG outperforms the best baselines by 4.54–11.39% and 6.06–16.24% in terms of AP and AUC on the temporal link prediction tasks, respectively. In addition, LightDyG reduces the time cost for training and test up to 45.91% and 63.94%, respectively, and also achieves a fast convergence speed during training. The implementation of our approach is available in https://github.com/nudtzpan/LightDyG .

Qisen Yang, Zekun Wang, Honghui Chen, Shenzhi Wang, Yifan Pu, Xin Gao, Wenhao Huang, Shiji Song, Gao Huang. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Data augmentation is serving as a critical and fundamental technology to improve model generalization and performance in a wide spectrum of machine learning tasks. Despite the increasing interest in developing various pathways to artificially generate new data to reduce the overfitting issue during model training, enriching the diversity of training data in the field of medicine remains facing enormous challenges. By virtue of recent advancements in generative artificial intelligence, we present a novel data augmentation framework, CLIP-MedFake, to address the shortage of training data used in medical image classification. The proposed method first employs the Stable Diffusion model to generate new fake data based on a small amount of training data, and then adopts the paradigm of few-shot learning and uses the CLIP architecture as the backbone to pre-train the model with synthetic data and then fine-tune it with real medical images. Extensive experiment results on two publicly available datasets demonstrate the effectiveness of the proposed method in promoting medical image classification.

Graph self-supervised learning is a task replete with potential. Previously, mainstream approaches in graph self-supervised learning were based on contrastive or generative tasks to extract graph embeddings, achieving commendable performance in downstream tasks such as node classification. However, these two methods have their respective strengths and limitations: (i) contrastive graph learning excels at capturing discriminative features of the graph but is more prone to overlooking structural representations of the graph itself; (ii) generative methods prioritize learning reconstructive features but struggle with large graphs and are susceptible to overfitting. Consequently, several simplistic fusion methods have been proposed, integrating encoded features from both approaches through concatenation, addition, or attention mechanisms for downstream tasks. However, these methods tend to be overly coarse, neglecting some unique information present in both categories of methods.To enhance the synergy of these two methods, we propose an edge perturbation data augmentation method to prevent the generation of spurious positive samples and a feature imputation decoder to complement contrastive features. We assess the model’s performance on two downstream tasks in graph representation learning, and experimental results demonstrate that our proposed method outperforms baseline methods on ten publicly available datasets.

Event representation aims to transform individual events from a narrative event chain into a set of low-dimensional vectors to help support a series of downstream applications, e.g., similarity differentiation and missing event prediction. Traditional event representation models tend to focus on single modeling perspectives and thus are incapable of capturing physically disconnected yet semantically connected event segments. We, therefore, propose a heterogeneous event graph model (HeterEvent) to explicitly represent such event segments. Furthermore, another challenge in traditional event representation models is inherited from the datasets themselves. Data sparsity and insufficient labeled data are commonly encountered in event chains, easily leading to overfitting and undertraining. Therefore, we extend HeterEvent with a multistructure contrastive learning framework (MulCL) to alleviate the training risks from two structural perspectives. From the sequential perspective, a sequential-view contrastive learning component (SeqCL) is designed to facilitate the acquisition of sequential characteristics. From the graph perspective, a graph-view contrastive learning component (GraCL) is proposed to enhance the robustness of graph training by comparing different corrupted graphs. Experimental results confirm that our proposed MulCL$_{[W+E]}$model outperforms state-of-the-art baselines. Specifically, compared with the previously proposed supervised model HeterEvent$_{[W+E]}$[Zhenget al.(2020)], MulCL$_{[W+E]}$shows an average improvement of 5.3% in terms of accuracy for the inference-ability-based tasks. For the representation-ability-based tasks, MulCL$_{[W+E]}$achieves an average improvement of 2.7% in terms of accuracy for the hard similarity tasks and an improvement of 4.1% in terms of the Spearman’s correlation for the transitive sentence similarity task, respectively.

Abstract Arbitrary shape text detection is a challenging task in scene text recognition. Driven by deep learning and large‐scale data sets, the detection method based on connected component (CC) has increasingly gained popularity. However, there are still problems of unclear separation of text instances and incorrect component links. Thus, in this paper, the authors propose a novel component connection method, that is, Fragmented Affinity Reasoning Network of Text Instances (FARNet), for arbitrary shape text detection. The network consists of a Weighted Feature Fusion Pyramid Network (WFFPN), Text Fragments Subgraph (TFS), and Dense Graph Attention Network (DGAT), which can be trained end‐to‐end. The WFFPN is used to generate text fragments, TFS and DGAT jointly construct an affinity reasoning network. Since the neighbouring boundaries between text instances may blend them into a single instance, the core idea is to use the WFFPN to divide the text instance into a series of rectangular fragments, the affinity reasoning network infers the affinity between fragments and then links them to rebuild text instances. Extensive experiments on seven challenging datasets (ICDAR2015, MSRA‐TD500, Totaltext, CTW‐1500, ICDAR 2019MLT, ICDAR2019 ArT, and DAST‐1500) demonstrate that the proposed text detector achieves state‐of‐the‐art performance in both on polygon datasets and quadrilateral datasets. The code is available at https://github.com/giganticpower/FARNet .

Job‐resume matching (JRM) is the core of online recruitment services for predicting the matching degree between a job post and a resume. Most of the existing methods for JRM achieve a promising performance by simplifying this task as a matching between the free‐text attributes in the job post and the resume. However, they neglect the contributions of the semistructured multivariate attributes such as education and salary, which will result in an unsuccessful prediction. To address this issue, we propose a novel approach to comprehensively explore the Internal and EXternal InTeractions for semistructured multivariate attributes in JRM, i.e., InEXIT. In detail, we first encode the key and the value of each attribute as well as its source into the same semantic space. Next, to explore the complex relationships among the multivariate attributes, we propose to hierarchically model the internal interactions among the multivariate attributes inside the job post and the resume, as well as the external interactions between the job post and the resume. In particular, a stepwise fusion mechanism is designed to respectively integrate the key embeddings and the source embeddings into the value embeddings so as to clearly indicate the key and the source of the value. Finally, we employ an aggregation matching layer to predict the matching degree. We quantify the improvements of InEXIT against the competitive baselines on a real‐world dataset, showing a general improvement of 4.28%, 4.10%, and 3.56% over the state‐of‐the‐art baseline in terms of AUC, accuracy, and F1 score, respectively.

Mobile edge computing is a new paradigm in which the computing and storage resources are placed at the edge of the Internet. Data placement and retrieval are fundamental services of mobile edge computing when a network of edge clouds collaboratively provide data services. These services require short-latency and low-overhead implementation in network and computing devices and load balance on edge clouds. However existing methods such as distributed hash tables (DHTs) are not enough to achieve efficient data placement and retrieval services for cooperative edge clouds. This article presents GRED, a novel data placement and retrieval service for mobile edge computing, which is efficient in not only the load balance but also routing path lengths and forwarding table sizes. GRED utilizes the programmable switches to support a virtual-space based DHT with only one overlay hop. Data location can be easily implemented on top of the GRED by associating a virtual position with each data by hashing, and storing the data at the edge server connected to the switch whose position is the nearest to the position of the data in the virtual space. We implement GRED in a P4 prototype, which provides a simple and efficient solution. Results from theoretical analysis, simulations, and experiments show that GRED can efficiently balance the load of edge clouds, and can fast answer data queries due to its low routing stretch.

Hierarchical context modeling plays an important role in the response generation for multi-turn conversational systems. Previous methods mainly model context as multiple independent utterances and rely on attention mechanisms to obtain the context representation. They tend to ignore the explicit responds-to relationships between adjacent utterances and the special role that the user's latest utterance (the query) plays in determining the success of a conversation. To deal with this, we propose a multi-turn response generation model named KS-CQ, which contains two crucial components, the Keep and the Select modules, to produce a neighbor-aware context representation and a context-enriched query representation. The Keep module recodes each utterance of context by attentively introducing semantics from its prior and posterior neighboring utterances. The Select module treats the context as background information and selectively uses it to enrich the query representing process. Extensive experiments on two benchmark multi-turn conversation datasets demonstrate the effectiveness of our proposal compared with the state-of-the-art baselines in terms of both automatic and human evaluations.

Recent research has highlighted the importance of mixed-initiative interactions in conversational search. To enable mixed-initiative interactions, information retrieval systems should be able to ask diverse questions, such as information-seeking, clarification, and open-ended ones. question generation (QG) of open-domain conversational systems aims at enhancing the interactiveness and persistence of human-machine interactions. The task is challenging because of the sparsity of question generation (QG)-specific data in conversations. Current work is limited to single-turn interaction scenarios. We propose a context-enhanced neural question generation (CNQG) model that leverages the conversational context to predict question content and pattern, then perform question decoding. A hierarchical encoder framework is employed to obtain the discourse-level context representation. Based on this, we propose Review and Transit mechanisms to respectively select contextual keywords and predict new topic words to further construct the question content. Conversational context and the predicted question content are used to produce the question pattern, which in turn guides the question decoding process implemented by a recurrent decoder with a joint attention mechanism. To fully utilize the limited QG-specific data to train our question generator, we perform multi-task learning with three auxiliary training objectives, i.e., question pattern prediction, Review , and Transit mechanisms. The required additional labeled data is obtained in a self-supervised way. We also design a weight decaying strategy to adjust the influences of various auxiliary learning tasks. To the best of our acknowledge, we are the first to extend the application of QG to the multi-turn open-domain conversational scenario. Extensive experimental results demonstrate the effectiveness of our proposal and its main components on generating relevant and informative questions, with robust performance for contexts with various lengths.

Event representation targets to model the event-reasoning process as a machine-readable format. Previous studies on event representation mostly concentrate on a sole modeling perspective and have not well investigated the scenario-level knowledge, which can cause information loss. To cope with this dilemma, we propose a unified fine-tuning architecture-based approach ( UniFA-S ) that integrates all levels of trainings, including the scenario-level knowledge. However, another challenge for existing models is the ever-increasing computation overheads, restricting the deployment ability on limited resources devices. Hence, in this article, we aim to compress the cumbersome model UniFA-S into a lighter and easy-to-deploy one without much performance damage. To this end, we propose a sequence-aware knowledge distillation model (SaKD) that employs a dynamic self-distillation on the decouple-compress-couple framework for compressing UniFA-S , which cannot only realize the model compression, but also retain the integrity of individual components. We also design two fitting strategies to address the less-supervised issue at the distillation stage. Comprehensive experiments on representation-and-inference ability-based tasks validate the effectiveness of SaKD. Compared to UniFA-S , SaKD realizes a more portable event representation model at the cost of only 1.0% performance drop in terms of accuracy or Spearman’s correlation, which is far less than other knowledge distillation models.

Few-shot relation extraction aims to identify the relation type between entities in a given text in the low-resource scenario. Albeit much progress, existing meta-learning methods still fall into prediction confusions owing to the limited inference ability over shallow text features. To relieve these confusions, this paper proposes a discriminative rule-based knowledge (DRK) method. Specifically, DRK adopts a logic-aware inference module to ease the word-overlap confusion, which introduces a logic rule to constrain the inference process, thereby avoiding the adverse effect of shallow text features. Also, DRK employs a discrimination finding module to alleviate the entity-type confusion, which explores distinguishable text features via a hierarchical contrastive learning. We conduct extensive experiments on four types of meta tasks and the results show promising improvements from DRK (6.0% accuracy gains on average). Besides, error analyses reveal the word-overlap and entity-type errors are the main courses of mispredictions in few-shot relation extraction.

Session-based recommendation aims to generate recommendations merely based on the ongoing session, which is a challenging task. Previous methods mainly focus on modeling the sequential signals or the transition relations between items in the current session using RNNs or GNNs to identify user’s intent for recommendation. Such models generally ignore the dynamic connections between the local and global item transition patterns, although the global information is taken into consideration by exploiting the global-level pair-wise item transitions. Moreover, existing methods that mainly adopt the cross-entropy loss with softmax generally face a serious over-fitting problem, harming the recommendation accuracy. Thus, in this article, we propose a Graph Co-Attentive Recommendation Machine (GCARM) for session-based recommendation. In detail, we first design a Graph Co-Attention Network (GCAT) to consider the dynamic correlations between the local and global neighbors of each node during the information propagation. Then, the item-level dynamic connections between the output of the local and global graphs are modeled to generate the final item representations. After that, we produce the prediction scores and design a Max Cross-Entropy (MCE) loss to prevent over-fitting. Extensive experiments are conducted on three benchmark datasets, i.e., Diginetica, Gowalla, and Yoochoose. The experimental results show that GCARM can achieve the state-of-the-art performance in terms of Recall and MRR, especially on boosting the ranking of the target item.

Session-based recommendation (SBR) , which mainly relies on a user’s limited interactions with items to generate recommendations, is a widely investigated task. Existing methods often apply RNNs or GNNs to model user’s sequential behavior or transition relationship between items to capture her current preference. For training such models, the supervision signals are merely generated from the sequential interactions inside a session, neglecting the correlations of different sessions, which we argue can provide additional supervisions for learning the item representations. Moreover, previous methods mainly adopt the cross-entropy loss for training, where the user’s ground truth preference distribution towards items is regarded as a one-hot vector of the target item, easily making the network over-confident and leading to a serious overfitting problem. Thus, in this article, we propose a Collaborative Graph Learning (CGL) approach for session-based recommendation. CGL first applies the Gated Graph Neural Networks (GGNNs) to learn item embeddings and then is trained by considering both the main supervision as well as the self-supervision signals simultaneously. The main supervisions are produced by the sequential order while the self-supervisions are derived from the global graph constructed by all sessions. In addition, to prevent overfitting, we propose a Target-aware Label Confusion (TLC) learning method in the main supervised component. Extensive experiments are conducted on three publicly available datasets, i.e., Retailrocket, Diginetica, and Gowalla. The experimental results show that CGL can outperform the state-of-the-art baselines in terms of Recall and MRR.

Edge computing promises a dramatic reduction in the network latency and the traffic volume, where many edge servers are placed at the edge of the Internet. Furthermore, those edge servers cache data to provide services for edge users. The data sharing among those edge servers can effectively shorten the latency to retrieve the data and further reduce the network bandwidth consumption. The key challenge is to construct an efficient data indexing mechanism no matter how the data is cached in the edge network. Although this is essential, it is still an open problem. Moreover, existing methods such as the centralized indexing and the DHT indexing in other fields fail to meet the performance demand of edge computing. This paper presents a COordinate-based INdexing (COIN) mechanism for the data sharing in edge computing. COIN maintains a virtual space where switches and data indexes are associated with their coordinates. Then, COIN distributes data indexes to indexing edge servers based on those coordinates. The COIN is effective because any query request from an edge server can be responded when the data has been stored in the edge network. More importantly, COIN is efficient in both routing path lengths and forwarding table sizes for publishing/querying data indexes. We implement COIN in a P4 prototype. Experimental results show that COIN uses 59% shorter path length and 30% less forwarding table entries to retrieve data indexes compared to using Chord, a well-known DHT solution.

To enable fast content delivery for delay-sensitive applications, large content providers build edge servers, Points of Presence (PoPs), and datacenters around the world. They are networked together as an integrated infrastructure via a private wide-area network (WAN), named content delivery network (CDN). To deliver quality services in the CDN, there are two critical decisions that should be properly made: 1) making assignments of PoP and datacenter for user requests, and 2) selecting routing paths from PoP to datacenter. However, with both the network variability and CDN environment complexity, it is challenging to achieve satisfying decisions. In this paper, we propose DeepDelivery, an adaptive deep reinforcement learning approach to intelligently make assignments and routing decisions in real time. Essentially, DeepDelivery adopts the Markov decision process (MDP) model to capture the dynamics of network variation, and the objective is to jointly maximize the infrastructure utilization of providers and minimize the total latency of end users. We conduct extensive trace-driven evaluations spanning various environment dynamics with both real-world and synthetic trace data. The result demonstrates that DeepDelivery can outperform the state-of-the-art scheme by 21.89% higher utilization and 11.27% lower end-to-end latency on average.

Event detection classifies unlabeled sentences into event labels, which can benefit numerous applications, including information retrieval, question answering and script learning. One of the major obstacles to event detection in reality is insufficient training data. To deal with the low-resources problem, we investigate few-shot event detection in this paper and propose TaLeM, a novel taxonomy-aware learning model, consisting of two components, i.e., the taxonomy-aware self-supervised learning framework (TaSeLF) and the taxonomy-aware prototypical networks (TaPN). Specifically, TaSeLF mines the taxonomy-aware distance relations to increases the training examples, which alleviates the generalization bottleneck brought by the insufficient data. TaPN introduces the Poincaré embeddings to represent the label taxonomy, and integrates them into a task-adaptive projection networks, which tackles problems of the class centroids distribution and the taxonomy-aware embedding distribution in the vanilla prototypical networks.

This paper provides theoretical and practical implications for the application of agent-based models (ABMs) to address the issue of coevolutionary business-IS alignment. The implications stem from the following arguments: (a) the alignment issue can be modelled by an ABM to describe the features of complex adaptive systems (CAS); (b) the coevolutionary principles of business and IS alignment stipulate individual behaviours and guide organisational order; (c) ABM development and experimentation offer guidance to better explain how organisations control the alignment trajectory with coevolutionary principles. To extend the extant coevolutionary research on alignment, this paper develops an ABM for a hierarchical organisational structure and validates three coevolutionary principles.

The hierarchical mobile edge computing satisfies the stringent latency requirements of data access and processing for emerging edge applications. The data location service is a basic function to provide data storage and retrieval to enable these applications. However, it still lacks research of a scalable and low-latency data location service in the environment. The existing solutions, such as DNS and DHT, fail to meet the requirement of those latency-sensitive applications. Therefore, in this article, we present a low-latency hybrid data-sharing framework, HDS. The HDS divides the data location service into two parts: intra-region and inter-region. More precisely, we design a data sharing protocol called Cuckoo Summary to achieve fast data localization in intra-region. Furthermore, for the inter-region data sharing, we develop a geographic routing based scheme to achieve efficient data localization with only one overlay hop. The advantages of HDS include short response latency, low implementation overhead, and few false positives. We implement the HDS framework based on a P4 prototype. The experimental results show that, compared to the state-of-the-art solutions, our design achieves 50.21% shorter lookup paths and 92.75% fewer false positives.

A large number of servers are interconnected using a specific datacenter network to deliver the infrastructure as a service (IaaS). Multicast can jointly utilize the network resources and further reduce the consumption of network bandwidth more than individual unicast. The source of a multicast service, however, does not need to be in a specific location as long as certain constraints are satisfied. This means the multicast can have uncertain sources, which could reduce the network resource consumption more than a traditional multicast service and further improve the quality of service. In this paper, we propose a novel reliable multicast service with uncertain sources named ReMUS. The goal is to minimize the sum of the transfer cost and the recovery cost, although finding such a ReMUS is very challenging. Thus, we design a source-based multicast method to solve this problem by exploiting the flexibility of sources when no recovery nodes exist in the network. Furthermore, we design a general multicast method to jointly exploit the benefits of uncertain sources and recovery nodes to minimize the total cost of ReMUS. We conduct extensive evaluations under Internet2 and datacenter networks. The results indicate that our methods can efficiently realize the reliable and scalable multicast with uncertain sources, irrespective of the settings of networks and multicasts. To the best of our knowledge, we are the first to study the reliable multicast service under uncertain sources.

Session-based recommendation is a challenging task. Without access to a user's historical user-item interactions, the information available in an ongoing session may be very limited. Previous work on session-based recommendation has considered sequences of items that users have interacted with sequentially. Such item sequences may not fully capture complex transition relationship between items that go beyond inspection order. Thus graph neural network (GNN) based models have been proposed to capture the transition relationship between items. However, GNNs typically propagate information from adjacent items only, thus neglecting information from items without direct connections. Importantly, GNN-based approaches often face serious overfitting problems. We propose Star Graph Neural Networks with Highway Networks (SGNN-HN) for session-based recommendation. The proposed SGNN-HN applies a star graph neural network (SGNN) to model the complex transition relationship between items in an ongoing session. To avoid overfitting, we employ highway networks (HN) to adaptively select embeddings from item representations. Finally, we aggregate the item embeddings generated by the SGNN in an ongoing session to represent a user's final preference for item prediction. Experiments on two public benchmark datasets show that SGNN-HN can outperform state-of-the-art models in terms of [email protected] and [email protected] for session-based recommendation.

Given an incomplete event chain, script learning aims to predict the missing event, which can support a series of NLP applications.Existing work cannot well represent the heterogeneous relations and capture the discontinuous event segments that are common in the event chain.To address these issues, we introduce a heterogeneous-event (HeterEvent) graph network.In particular, we employ each unique word and individual event as nodes in the graph, and explore three kinds of edges based on realistic relations (e.g., the relations of word-and-word, word-and-event, event-and-event).We also design a message passing process to realize information interactions among homo or heterogeneous nodes.And the discontinuous event segments could be explicitly modeled by finding the specific path between corresponding nodes in the graph.The experimental results on one-step and multi-step inference tasks demonstrate that our ensemble model HeterEvent [W +E] can outperform existing baselines.

Edge computing satisfies the stringent latency requirements of data access and processing for applications running on edge devices. The data location service is a key function to provide data storage and retrieval to enable these applications. However, it still lacks research of a scalable and low-latency data location service in mobile edge computing. Meanwhile, the existing solutions, such as DNS and DHT, fail to meet the low latency requirement of mobile edge computing. This paper presents a low-latency hybrid data-sharing framework, HDS, in which the data location service is divided into two parts: intra-region and inter-region. In the intra-region part, we design a data sharing protocol called Cuckoo Summary to achieve fast data localization. In the inter-region part, we develop a geographic routing based scheme to achieve efficient data localization with only one overlay hop. The advantages of HDS include short response latency, low implementation overhead, and few false positives. We implement our HDS framework based on a P4 prototype. The experimental results show that, compared to the state-of-the-art solutions, our design achieves 50.21% shorter lookup paths and 92.75% fewer false positives.

Given an occurred event, human can easily predict the next event or reason the preceding event, yet which is difficult for machine to perform such event reasoning. Event representation bridges the connection and targets to model the process of event reasoning as a machine-readable format, which then can support a wide range of applications in information retrieval, e.g., question answering and information extraction. Existing work mainly resorts to a joint training to integrate all levels of training loss in event chains by a simple loss summation, which is easily trapped into a local optimum. In addition, the scenario knowledge in event chains is not well investigated for event representation. In this paper, we propose a unified fine-tuning architecture, incorporated with scenario knowledge for event representation, i.e., UniFA-S, which mainly consists of a unified fine-tuning architecture (UniFA) and a scenario-level variational auto-encoder (S-VAE). In detail, UniFA employs a multi-step fine-tuning to integrate all levels of training and S-VAE applies a stochastic variable to implicitly represent the scenario-level knowledge. We evaluate our proposal from two aspects, i.e., the representation and inference abilities. For the representation ability, our ensemble model UniFA-S can beat state-of-the-art baselines for two similarity tasks. For the inference ability, UniFA-S can outperform the best baseline, achieving 4.1%-8.2% improvements in terms of accuracy for various inference tasks.

Question generation in open-domain dialogue systems is a challenging but less-explored task. It aims to enhance the interactivity and persistence of human-machine interactions. Previous work mainly focuses on question generation in the setting of single-turn dialogues, or investigates it as a data augmentation method for machine comprehension. We propose a Context-augmented Neural Question Generation (CNQG) model that leverages the conversational context to generate questions for promoting interactivity and persistence of multi-turn dialogues. More specifically, we formulate the task of question generation as a two-stage process. First, we employ an encoder-decoder framework to predict a question pattern, which denotes a set of representative interrogatives, and identify the potential topics from the conversational context by employing point-wise mutual information. Then, we generate the question by decoding the concatenation of the current dialogue utterance, the pattern, and the topics with an attention mechanism. To the best of our knowledge, ours is the first work on question generation in multi-turn open-domain dialogue systems. Our experimental results on two publicly available multi-turn conversation datasets show that CNQG outperforms the state-of-the-art baselines in terms of BLEU-1, BLEU-2, Distinct-1 and Distinct-2. In addition, we find that CNQG allows one to efficiently distill useful features from long contexts, and maintain robust effectiveness even for short contexts.

Vehicular cloud computing (VCC) has been utilized to enhance traffic management and road safety. By connecting with base stations (BSes), VCC can provide the information of real-time dynamics for smart vehicles (SVs). However, the area outside the coverage of BSes will be the blind areas, where SVs cannot obtain the real-time safety guarantee, especially on the highway. In this article, we utilize unmanned aerial vehicles (UAVs) to assist the communication between SVs and BSes to solve the above problem. In particular, we study the interdependency task scheduling for the highway driving environment detection, where SVs, BSes, and UAVs collect the environmental data, schedule tasks, and feedback results cooperatively. There are two main problems in this scenario: 1) the scheduling within the coverage of BSes and 2) the rescheduling between the coverage of BSes. We model both the processes as constrained numerical optimization problems aiming to minimize the request-response time. To this end, we propose a systematical scheduling scheme named Teso, which consists of two stages: 1) designed approximation algorithm for scheduling and 2) offloading algorithm for rescheduling. Extensive experiments show that Teso can significantly reduce the response time overall and improve the system stability.

Large-scale datacenters are the key infrastructures of cloud computing. Inside a datacenter, a large number of servers are interconnected using a specific datacenter network to deliver the infrastructure as a service (IaaS) for tenants. To realize novel cloud applications like the network virtualization and network isolation among tenants, the principle of software-defined network (SDN) has been applied to datacenters. In the setting, multiple distributed controllers are deployed to offer a control plane over the entire datacenter to efficiently manage the network usage. Despite such efforts, cloud datacenters, however, still lack a scalable and resilient control plane. Consequently, this paper systematically studies the coverage problem of controllers, which means to cover all network devices using the least number of controllers. More precisely, we tackle this essential problem from three aspects, including the minimal coverage, the minimal fault-tolerant coverage, and the minimal communication overhead among controllers. After modelling and analyzing such three problems, we design efficient approaches to approximate the optimal solution, respectively. Extensive evaluation results indicate that our approaches can significantly save the number of required controllers, improve the fault-tolerant capability of the control plane and reduce the communication overhead of state synchronization among controllers. The design methodologies proposed in this paper can be applied to cloud datacenters with other networking structures after minimal modifications.

Session-based recommendation is the task of recommending the next item a user might be interested in given partially known session information, e.g., part of a session or recent historical sessions. An effective session-based recommender should be able to exploit a user's evolving preferences, which we assume to be a mixture of her short- and long-term interests. Existing session-based recommendation methods often embed a user's long-term preference into a static representation, which plays a fixed role when dealing with her current short-term interests. This is problematic because long-term preferences may be more or less important for predicting the next conversion depending on the user's short-term interests. We propose a DCN-SR. DCN-SR applies a co-attention network to capture the dynamic interactions between the user's long- and short-term interaction behavior and generates co-dependent representations of the user's long- and short-term interests. For modeling a user's short-term interaction behavior, we design a CGRU network to take actions like "click'', "collect'' and "buy'' into account. Experiments on e-commerce datasets show significant improvements of DCN-SR over state-of-the-art session-based recommendation methods, with improvements of up to 2.58% on the Tmall dataset and 3.08% on the Tianchi dataset in terms of [email protected] [email protected] improvements are 3.78% and 4.05%, respectively. We also investigate the scalability and sensitivity of DCN-SR. The improvements of DCN-SR over state-of-the-art baselines are especially noticeable for short sessions and active users with many historical interactions.

Edge computing is a new paradigm in which the computing and storage resources are placed at the edge of the Internet. Data placement and retrieval are fundamental services of edge computing when a network of edge servers collaboratively provide data storage. These services require short-latency and low-overhead implementation in network devices and load balance on edge servers. However existing methods such as distributed hash tables (DHTs) are not able to achieve efficient data placement and retrieval services in the edge computing environment. This paper presents GRED, an efficient data placement and retrieval service for edge computing, which is efficient in not only the load balance but also routing path lengths and forwarding table sizes. GRED utilizes the software-defined networking paradigm to support a virtual-space based DHT with only one overlay hop. We implement GRED in a P4 prototype. Experimental results show that GRED uses <; 30% routing path lengths and achieves better load balance among edge servers compared to using Chord, a well-known DHT solution.

Edge computing promises a dramatic reduction in the network latency and the traffic volume, where many edge servers are placed at the edge of the Internet. Furthermore, these edge servers cache data to provide services for edge users. The data sharing among edge servers can effectively shorten the latency to retrieve the data and further reduce the network bandwidth consumption. The key challenge is to construct an efficient data indexing mechanism no matter how the data is cached in the edge network. Although this is essential, it is still an open problem. Moreover, existing methods such as the centralized indexing and the DHT indexing in other fields fail to meet the performance demand of edge computing. This paper presents a COordinate-based INdexing (COIN) mechanism for the data sharing in edge computing. COIN maintains a virtual space where the switches and the data indexes are associated with the coordinates. Then, COIN distributes data indexes to indexing edge servers based on those coordinates. The COIN is effective because any query request from an edge server can be responded when the data has been stored in the edge network. More importantly, COIN is efficient in both routing path lengths and forwarding table sizes for publishing/querying the data indexes. We implement COIN in a P4 prototype. Experimental results show that COIN uses 59% shorter path length and 30% less forwarding table entries to retrieve the data index compared to using Chord, a well-known DHT solution.

Answer selection focuses on selecting the correct answer for a question. Most previous work on answer selection achieves good performance by employing an RNN, which processes all question and answer sentences with the same feature extractor regardless of the sentence length. These methods often encounter the problem of long-term dependencies. To address this issue, we propose a Length-adaptive Neural Network (LaNN) for answer selection that can auto-select a neural feature extractor according to the length of the input sentence. In particular, we propose a flexible neural structure that applies a BiLSTM-based feature extractor for short sentences and a Transformer-based feature extractor for long sentences. To the best of our knowledge, LaNN is the first neural network structure that can auto-select the feature extraction mechanism based on the input. We quantify the improvements of LaNN against several competitive baselines on the public WikiQA dataset, showing significant improvements over the state-of-the-art.

We propose a Joint Neural Collaborative Filtering (J-NCF) method for recommender systems. The J-NCF model applies a joint neural network that couples deep feature learning and deep interaction modeling with a rating matrix. Deep feature learning extracts feature representations of users and items with a deep learning architecture based on a user-item rating matrix. Deep interaction modeling captures non-linear user-item interactions with a deep neural network using the feature representations generated by the deep feature learning process as input. J-NCF enables the deep feature learning and deep interaction modeling processes to optimize each other through joint training, which leads to improved recommendation performance. In addition, we design a new loss function for optimization that takes both implicit and explicit feedback, point-wise and pair-wise loss into account. Experiments on several real-world datasets show significant improvements of J-NCF over state-of-the-art methods, with improvements of up to 8.24% on the MovieLens 100K dataset, 10.81% on the MovieLens 1M dataset, and 10.21% on the Amazon Movies dataset in terms of HR@10. NDCG@10 improvements are 12.42%, 14.24%, and 15.06%, respectively. We also conduct experiments to evaluate the scalability and sensitivity of J-NCF. Our experiments show that the J-NCF model has a competitive recommendation performance with inactive users and different degrees of data sparsity when compared to state-of-the-art baselines.

The design of distributed control plane is an essential part of SDN. While there is an urgent need for verifying the control plane, little, however, is known about how to validate that the control plane offers assurable performance, especially across various failures. Such validation is hard due to two fundamental challenges. First, the number of potential failure scenarios could be exponential or even non-enumerable. Second, it is still an open problem to model the performance change when the control plane employs different failure recovery strategies. In this paper, we first characterize the validation of the distributed control plane as a robust optimization problem and further propose a robust validation framework to verify whether a control plane provides assurable performance across various failure scenarios and multiple failure recovery strategies. Then, we prove that identifying an optimal recovery strategy is NP-hard after developing an optimization model of failure recovery. Accordingly, we design two efficient failure recovery strategies, which can well approximate the optimal strategy and further exhibit good performance against potential failures. Furthermore, we design the capacity augmentation scheme when the control plane fails to accommodate the worst failure scenario even with the optimal failure recovery strategy. We have conducted extensive evaluations based on an SDN test bed and large-scale simulations over real network topologies. The evaluation results show the efficiency and effectiveness of the proposed validation framework.

In previous work on text summarization, encoder-decoder architectures and attention mechanisms have both been widely used. Attention-based encoder-decoder approaches typically focus on taking the sentences preceding a given sentence in a document into account for document representation, failing to capture the relationships between a sentence and sentences that follow it in a document in the encoder. We propose an attentive encoder-based summarization (AES) model to generate article summaries. AES can generate a rich document representation by considering both the global information of a document and the relationships of sentences in the document. A unidirectional recurrent neural network (RNN) and a bidirectional RNN are considered to construct the encoders, giving rise to unidirectional attentive encoder-based summarization (Uni-AES) and bidirectional attentive encoder-based summarization (Bi-AES), respectively. Our experimental results show that Bi-AES outperforms Uni-AES. We obtain substantial improvements over a relevant start-of-the-art baseline.

Query suggestions help users of a search engine to refine their queries. Previous work on query suggestion has mainly focused on incorporating directly observable features such as query co-occurrence and semantic similarity. The structure of such features is often set manually, as a result of which hidden dependencies between queries and users may be ignored. We propose an AHNQS model that combines a hierarchical structure with a session-level neural network and a user-level neural network to model the short- and long-term search history of a user. An attention mechanism is used to capture user preferences. We quantify the improvements of AHNQS over state-of-the-art RNN-based query suggestion baselines on the AOL query log dataset, with improvements of up to 21.86% and 22.99% in terms of [email protected] and [email protected], respectively, over the state-of-the-art; improvements are especially large for short sessions.

In multi-tenant shared clouds, applications of different tenants compete for the shared network and thus suffer significant unpredictability of performance. The progress is an essential metric to measure the overall data transfer rate of a tenant and to indicate how fast a tenant can complete data transfer. Most previous work of network allocation or schedule focus on achieving the tradeoff among the fairness, performance, and efficiency. They, however, often do not make each tenant achieve noticeable progress. In this paper, we motivate to maximize tenant's progress by using information about the underlying network and traffic patterns of tenants' applications. To illustrate the feasibility of maximizing progress, we develop a network sharing framework for multi-tenant datacenter, by exploiting the benefits of careful placement of tenant's applications. Furthermore, the tenants' progress and network utilization would be further improved without impacting performance isolation, if the bandwidth demand of each application can be rescheduled. Our evaluation results show that our method provides higher tenant progress and better tenant-level performance than HUG.

Multicast can jointly utilize the network resources when delivering the same content to a set of destinations; hence, it can effectively reduce the consumption of network resources more than individual unicast. The source of a multicast, however, does not need to be in a specific location as long as certain constraints are satisfied. This means the multicast can have uncertain sources, which could reduce the network bandwidth consumption more than a traditional multicast. Meanwhile, a reliable multicast becomes crucial in providing reliable services for many important applications. However, a prior minimal cost forest (MCF) for such a new multicast is not designed to support reliable transmissions. In this paper, we propose a novel reliable multicast routing with uncertain sources named ReMUS. To the best of our knowledge, we are the first to study the reliable multicast under uncertain sources. The goal is to minimize the sum of the transfer cost and the recovery cost, although finding such a ReMUS is very challenging. Thus, we design a sourcebased multicast method to solve this problem by exploiting the flexibility of uncertain sources when no recovery nodes exist in the network. Furthermore, we design a general multicast method to jointly exploit the benefits of uncertain sources and recovery nodes to minimize the total cost of ReMUS. We conduct extensive evaluations based on the real topology of Internet2. The results indicate that our methods can efficiently realize the reliable and bandwidth-efficient multicast with uncertain sources, irrespective of the settings of networks and multicasts.

Query suggestions help users refine their queries after they input an initial query. We consider the task of generating query suggestions that are personalized and diversified. We propose a personalized query suggestion diversification model (PQSD), where a user's long-term search behavior is injected into a basic greedy query suggestion diversification model (G-QSD) that considers a user's search context in their current session. Query aspects are identified through clicked documents based on the Open Directory Project (ODP). We quantify the improvement of PQSD over a state-of-the-art baseline using the AOL query log and show that it beats the baseline in terms of metrics used in query suggestion ranking and diversification. The experimental results show that PQSD achieves the best performance when only queries with clicked documents are taken as search context rather than all queries.

Summary Large‐scale online services and distributed execution engines (i.e., MapReduce and Dryad) generate large volumes of traffic in data center networks. As a consequence, significant congestion can occur in the data center network. To the best of our knowledge, most existing approaches either focus on local congestion‐aware mechanisms, which have only a poor ability to handle asymmetry or use explicit congestion notification packets, which are difficult to implement directly in switch hardware. These methods are insufficient to solve the congestion problem. In this paper, we focus on a congestion‐free routing strategy, resorting to the global view of the data center network in a software‐defined networking controller. Specifically, a timeslot allocation was first conducted for the coming packets, and then the corresponding routing paths were computed for each packet. In view of the efficiency, the timeslot allocation algorithm follows a heuristic pattern, and the path selection is modeled as a bin‐packing problem. Simulation results showed that the congestion‐free routing strategy proposed here performs well in throughput, queuing, and end‐to‐end round‐trip time. Copyright © 2015 John Wiley & Sons, Ltd.

With an increasing use of services sustaining the resources which people need has become more important. In this paper, we propose an effective reservation method, called “BPSR” (Business Process Service Reservation), which aims for the process reservation which to the best of our knowledge has not been studied before. In particular we address for major jobs: service differentiation; service reservation; process reservation and QoS Control. We also describe a flexible policy-based reservation method which aims to increase the success rate of reservation and utilization of service resources. Experimental analysis shows that the BPSR reservation system achieves better results than other reservation methods.

A Bloom filter is an effective, space-efficient data structure for concisely representing a set, and supporting approximate membership queries. Traditionally, the Bloom filter and its variants just focus on how to represent a static set and decrease the false positive probability to a sufficiently low level. By investigating mainstream applications based on the Bloom filter, we reveal that dynamic data sets are more common and important than static sets. However, existing variants of the Bloom filter cannot support dynamic data sets well. To address this issue, we propose dynamic Bloom filters to represent dynamic sets, as well as static sets and design necessary item insertion, membership query, item deletion, and filter union algorithms. The dynamic Bloom filter can control the false positive probability at a low level by expanding its capacity as the set cardinality increases. Through comprehensive mathematical analysis, we show that the dynamic Bloom filter uses less expected memory than the Bloom filter when representing dynamic sets with an upper bound on set cardinality, and also that the dynamic Bloom filter is more stable than the Bloom filter due to infrequent reconstruction when addressing dynamic sets without an upper bound on set cardinality. Moreover, the analysis results hold in stand-alone applications, as well as distributed applications.

There is a growing need for enabling reprogramming in a working sensor network. We prefer to meet the requirements remotely instead of collecting all deployed sensors. Identifying the version difference of data items, having the same key, could significantly reduce the communication overhead, because only those out-of-date items should be updated at each sensor. Previous protocols need to exchange multiple messages to identify a version difference between two items with the same key. In this paper, we propose a reliable and energy efficient data dissemination protocol (BDP) with less propagation delay. BDP uses Bloom filters to identify a version difference between two items with the same key, and find the new one between two items having the same key but different versions. Through comprehensive simulations, we show that BDP outperforms previous work in terms of energy cost and propagation delay of updating new items with high reliability

The topological properties of peer-to-peer overlay networks are critical factors that dominate the performance of these systems. Several non-constant and constant degree interconnection networks have been used as topologies of many peer-to-peer networks. One of these has many desirable properties: the Kautz digraph. Unlike interconnection networks, peer-to-peer networks need a topology with an arbitrary size and degree, but the complete Kautz digraph does not possess these properties. In this paper, we propose Moore: the first effective and practical peer-to-peer network based on the incomplete Kautz digraph withO(logdN) diameter and constant degree under a dynamic environment. The diameter and average routing path length are [logd(N) - logd(1 + 1/d)] and logdN, respectively, and are shorter than that of CAN, butterfly, and cube-connected-cycle. They are close to that of complete de Bruijn and Kautz digraphs. The message cost of node joining and departing operations are at most 2.5dlogdNand (2.5d+ 1) logdN, and onlydand 2dnodes need to update their routing tables. Moore can achieve optimal diameter, high performance, good connectivity and low congestion evaluated by formal proofs and simulations.

Abstract — A bloom filter is a simple, space-efficient, randomized data structure for concisely representing a static data set, in order to support approximate membership queries. It has great potential for distributed applications where systems need to share information about what resources they have. The space efficiency is achieved at the cost of a small probability of false positive in membership queries. However, for many applications the space savings and short locating time consistently outweigh this drawback. In this paper, we introduce dynamic bloom filters (DBF) to support concise representation and approximate membership queries of dynamic sets, and study the false positive probability and union algebra operations. We prove that DBF can control the false positive probability at a low level by adjusting the number of standard bloom filters used according to the actual size of current dynamic set. The space complexity is also acceptable if the actual size of dynamic set does not deviate too much from the predefined threshold. Furthermore, we present multidimension dynamic bloom filters (MDDBF) to support concise representation and approximate membership queries of dynamic sets in multiple attribute dimensions, and study the false positive probability and union algebra operations through mathematic analysis and experimentation. We also explore the optimization approach and three network applications of bloom filters, namely bloom joins, informed search, and global index implementation. Our simulation shows that informed search based on bloom filters can obtain higher recall and success rate of query than the blind search protocol.

As the increasing development of application technology and infrastructure, many kinds of application and resources can be encapsulated as Web service and its variations, and service-oriented computing become research hot. But, we believe service-oriented computing should establish on virtualized service rather than concrete service instance directly. In this paper, we present formalized model of virtualized service and service instance, and define the concept of service virtualization. Then, we propose the implementation solution of virtualized service-oriented application from perspective of global and local instantiation process.