Fine-Grained entity typing is complicated by the fact that type labels form a hierarchical structure, and those training examples usually contain noisy type labels. This paper addresses these two issues by proposing a novel framework that simultaneously models the correlation among hierarchical types and the noise within the training data. Additionally, the framework contains an innovative training approach during which the noise in the training data is progressively removed. Experiments on standard benchmarking datasets validate the proposed framework and establish it as a new state of the art for this problem.

Scholar name disambiguation remains a hard and unsolved problem, which brings various troubles for bibliography data analytics. Most existing methods handle name disambiguation separately that tackles one name at a time, and neglect the fact that disambiguation of one name affects the others. Further, it is typically common that only limited information is available for bibliography data, e.g., only basic paper and citation information is available in DBLP. In this study, we propose a collective approach to name disambiguation, which takes the connection of different ambiguous names into consideration. We reformulate bibliography data as a heterogeneous multipartite network, which initially treats each author reference as a unique author entity, and disambiguation results of one name propagate to the others of the network. To further deal with the sparsity problem caused by limited available information, we also introduce word-word and venue-venue similarities, and we finally measure author similarities by assembling similarities from four perspectives. Using real-life data, we experimentally demonstrate that our approach is both effective and efficient.

This study investigates name disambiguation for scholarly data. We propose a collective approach, which considers the connections of different ambiguous names, such that it initially treats each author reference as a unique author entity and reformulates the bibliography data as a heterogeneous multipartite network. Disambiguation results of one author name propagate to the others in the network. To further deal with the sparsity problem caused by limited available information, we also introduce word-word and venue-venue similarities and measure author similarities by assembling similarities from multiple perspectives. Using three real-life datasets, we experimentally show that our approach is both effective and efficient.

Fine-grained entity typing (FET) aims to annotate the entity mentions in a sentence with fine-grained type labels. It brings plentiful semantic information for many natural language processing tasks. Existing FET approaches apply hard attention to learn on the noisy labels, and ignore that those noises have structured hierarchical dependency. Despite their successes, these FET models are insufficient in modeling type hierarchy dependencies and handling label noises. In this paper, we directly tackle the structured noisy labels by combining a forward tree module and a backward tree module. Specifically, the forward tree formulates the informative walk that hierarchically represents the type distributions. The backward tree models the erroneous walk that learns the noise confusion matrix. Empirical studies on several benchmark data sets confirm the effectiveness of the proposed framework.

Scholarly search systems greatly aid the deep understanding of scholarly data and facilitate the research activities of scholars for scientific studies. Though a number of such systems have been developed, most of them either support rankings of limited search of entities or provide only basic ranking metrics. These existing systems also mainly adopt RDBMSs as their storage such that the linked feature of scholarly data is not fully exploited. In this study, we design and develop a novel scholarly search system Athena. (1) It supports four types of scholarly entity searches: articles, authors, venues and affiliations, and is equipped with five ranking metrics, including three traditional metrics and two comprehensive importance ranking metrics. (2) It also provides profiling of scholarly entities. (3) It further utilizes a graph storage to directly leverage the linked feature for speeding up the processing of complex queries. We demonstrate the advantages of Athena at scholarly search, profiling, graph storage and ranking quality.

Entity linking, which maps named entity mentions in a document into the proper entities in a given knowledge graph, has been shown to be able to significantly benefit from modeling the entity relatedness through Graph Convolutional Networks (GCN). Nevertheless, existing GCN entity linking models fail to take into account the fact that the structured graph for a set of entities not only depends on the contextual information of the given document but also adaptively changes on different aggregation layers of the GCN, resulting in insufficiency in terms of capturing the structural information among entities. In this paper, we propose a dynamic GCN architecture to effectively cope with this challenge. The graph structure in our model is dynamically computed and modified during training. Through aggregating knowledge from dynamically linked nodes, our GCN model can collectively identify the entity mappings between the document and the knowledge graph, and efficiently capture the topical coherence among various entity mentions in the entire document. Empirical studies on benchmark entity linking data sets confirm the superior performance of our proposed strategy and the benefits of the dynamic graph structure.

Dense subgraph discovery has proven useful in various applications of temporal networks. We focus on a special class of temporal networks whose nodes and edges are kept fixed, but edge weights regularly vary with timestamps. However, finding dense subgraphs in temporal networks is non-trivial, and its state of the art solution uses a filter-and-verification framework that is not scalable on large temporal networks. In this study, we propose a highly efficient approach to finding dense subgraphs in large temporal networks with T timestamps. (1) We first develop a statistics-driven approach that employs hidden statistics to identifying k time intervals, instead of T(T + 1)/2 ones (k is typically much smallerthan T), which strikes a balance between quality and efficiency. (2) After proving that the problem has no constant factor approximation algorithms, we design better heuristic algorithms to attack the problem, by connecting finding dense subgraphs with a variant of the Prize Collecting Steiner Tree problem. (3) Finally, we have conducted an extensive experimental study to verify that our approach is both effective and efficient.

Shuai Ma, Gang Wang, Yansong Feng, Jinpeng Huai. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Fine-grained entity typing (FET), which annotates the entities in a sentence with a set of finely specified type labels, often serves as the first and critical step towards many natural language processing tasks. Despite great processes have been made, current FET methods have difficulty to cope with the noisy labels which naturally come with the data acquisition processes. Existing FET approaches either pre-process to clean the noise or simply focus on one of the noisy labels, sidestepping the fact that those noises are related and content dependent. In this paper, we directly model the structured, noisy labels with a novel content-sensitive weighting schema. Coupled with a newly devised cost function and a hierarchical type embedding strategy, our method leverages a random walk process to effectively weight out noisy labels during training. Experiments on several benchmark datasets validate the effectiveness of the proposed framework and establish it as a new state of the art strategy for noisy entity typing problem.

Microblog platforms have been extremely popular in the big data era due to its real-time diffusion of information. It's important to know what anomalous events are trending on the social network and be able to monitor their evolution and find related anomalies. In this paper we demonstrate RING, a real-time emerging anomaly monitoring system over microblog text streams. RING integrates our efforts on both emerging anomaly monitoring research and system research. From the anomaly monitoring perspective, RING proposes a graph analytic approach such that (1) RING is able to detect emerging anomalies at an earlier stage compared to the existing methods, (2) RING is among the first to discover emerging anomalies correlations in a streaming fashion, (3) RING is able to monitor anomaly evolutions in real-time at different time scales from minutes to months. From the system research perspective, RING (1) optimizes time-ranged keyword query performance of a full-text search engine to improve the efficiency of monitoring anomaly evolution, (2) improves the dynamic graph processing performance of Spark and implements our graph stream model on it, As a result, RING is able to process big data to the entire Weibo or Twitter text stream with linear horizontal scalability. The system clearly presents its advantages over existing systems and methods from both the event monitoring perspective and the system perspective for the emerging event monitoring task.

The area of anomaly detection has recently been expanded in the graph-based data. Anomalous vertices are often exhibited as a connected subgraph. Few works, however, have focused on connected anomalous subgraph detection because of the challenge of optimizing graph functionals under connectivity constraints. We employ Non-Parametric Graph Scan (NPGS) statistics for detecting anomalies within graph-based data. Based on the NPGS statistics, we proposed an efficient approximate approach to the connected anomalous subgraph detection problem that provides provable guarantees on performance and quality. In particular, we first decompose the problem into a sequence of subproblems, each of which can be reduced to a Budget Price-Collecting Steiner Tree (BPCST) problem, and then develop efficient exact and approximate algorithms for a special category of graphs in which the anomalous subgraphs can be reformulated in a fixed tree topology. Our method has a wide variety of applications, such as disease outbreak detection, road traffic congestion detection, and event detection in social media, because the NPGS statistics is free of distribution assumptions and can be applied to heterogeneous graph data.

Question answering over knowledge bases aims to take full advantage of the information in knowledge bases with the ultimate purpose of returning answers to questions. To access the substantial knowledge within the KB, many model architectures are hindered by the bottleneck of accurately predicting relations that connect subject entities in questions to object entities in the knowledge base. To break the bottleneck, this article presents a novel model architecture, APVA, which includes a verification mechanism to check the correctness of predicted relations. Specifically, APVA takes advantage of KB-based information to improve relation prediction but verifies the correctness of the predicted relation by means of simple negative sampling in a logistic regression framework. The APVA architecture offers a natural way to integrate an iterative training procedure, which we call turbo training. Accordingly, we introduce APVA-TURBO to perform question answering over knowledge bases. We demonstrate extensive experiments to show that APVA-TURBO outperforms existing approaches on question answering.

With the rapid development of fast and byte-addressable non-volatile memories (NVMs), hybrid NVM/DRAM storage systems become promising for computer systems. Existing NVM file systems have already been optimized around the NVM properties. However, they inherit some design choices of block-oriented storage devices that lead to scalability bottlenecks and data copy overhead for ensuring data consistency. In this paper, we present noseFS, a highly non-volatile memory scalable and efficient File System. It is designed to achieve high performance through a bundle of novel techniques: (1) a scalable lightweight naming integrating VFS with the underlying file system namespace, (2) a fine-grained byte-unit file index tree avoiding redundant copy overhead introduced by Copy-On-Write, (3) a lightweight journaling providing atomicity and scalability on many-core platforms, and (4) a lightweight atomic-mmap providing strong consistency guarantee with low overhead by tracking dirty pages. Experimental results show that noseFS performs much better than the state-of-the-art file systems with equally strong data consistency guarantees, and achieves near-linear scalability on a 40-core machine.

Ranking query independent scholarly articles is a practical and difficult task, due to the heterogeneous, evolving and dynamic nature of entities involved in scholarly articles. To do this, we first propose a scholarly article ranking model by assembling the importance of involved entities (i.e., articles, venues and authors) such that the importance is a combination of prestige and popularity to capture the evolving nature of entities. To compute the prestige of articles and venues, we propose a novel Time-Weighted PageRank that extends traditional PageRank with a time decaying factor. We then develop a batch algorithm for scholarly article ranking, in which we propose a block-wise method for Time-Weighted PageRank in terms of an analysis of the citation characteristics of scholarly articles. We further develop an incremental algorithm for dynamic scholarly article ranking, which partitions graphs into affected and unaffected areas, and employs different updating strategies for nodes in different areas. Using real-life data, we finally conduct an extensive experimental study, and show that our approach is both effective and efficient for ranking scholarly articles.

Existing efforts mainly use empirical analysis to evaluate the effectiveness of crowdsourcing methods, which is often unreliable across experimental settings. Consequently, it is of great importance to study theoretical methods. This work, for the first time, defines the cost complexity of crowdsourcing, and presents two theorems to compute the cost complexity. Our theorems provide a general theoretical method to model the trade-off between costs and quality, which can be used to evaluate and design crowdsourcing algorithms, and characterize the complexity of crowdsourcing problems. Moreover, following our theorems, we prove a set of corollaries that can obtain existing theoretical results for special cases. We have verified our work theoretically and empirically.

Road traffic speed prediction is a challenging problem in intelligent transportation system (ITS) and has gained increasing attentions. Existing works are mainly based on raw speed sensing data obtained from infrastructure sensors or probe vehicles, which, however, are limited by expensive cost of sensor deployment and maintenance. With sparse speed observations, traditional methods based only on speed sensing data are insufficient, especially when emergencies like traffic accidents occur. To address the issue, this paper aims to improve the road traffic speed prediction by fusing traditional speed sensing data with new-type “sensing” data from cross domain sources, such as tweet sensors from social media and trajectory sensors from map and traffic service platforms. Jointly modeling information from different datasets brings many challenges, including location uncertainty of low-resolution data, language ambiguity of traffic description in texts, and heterogeneity of cross-domain data. In response to these challenges, we present a unified probabilistic framework, called Topic-Enhanced Gaussian Process Aggregation Model (TEGPAM), consisting of three components, i.e., location disaggregation model, traffic topic model, and traffic speed Gaussian Process model, which integrate new-type data with traditional data. Experiments on real world data from two large cities validate the effectiveness and efficiency of our model.

In sparse data, a large fraction of the entries take on zero values. Some examples of sparse data include short text snippets (such as tweets in Twitter) or some feature representations of categorical data sets with a large number of values, in which traditional methods for outlier detection typically fail because of the difficulty of computing distances. To address this, it is important to use the latent relations between such values. Factorization machines represent a natural methodology for this, and are naturally designed for the massive-domain setting because of their emphasis on sparse data sets. In this study, we propose an outlier detection approach for sparse data with factorization machines. Factorization machines are also efficient due to their linear complexity in the number of non-zero values. In fact, because of their efficiency, they can even be extended to traditional settings for numerical data by an appropriate feature engineering effort. We show that our approach is both effective and efficient for sparse categorical, short text and numerical data by an extensive experimental study.

This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. We propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

Dense subgraph discovery has proven useful in various applications of temporal networks. We focus on a special class of temporal networks whose nodes and edges are kept fixed, but edge weights constantly and regularly vary with timestamps. However, finding dense subgraphs in temporal networks is nontrivial, and its state of the art solution uses a filter-and-verification framework, which is not scalable on large temporal networks. In this study, we propose a data-driven approach to finding dense subgraphs in large temporal networks with T timestamps. (1) We first develop a data-driven approach employing hidden statistics to identifying k time intervals, instead of T*(T + 1)/2 ones (k is typically much smaller than T), which strikes a balance between quality and efficiency. (2) After proving that the problem has no constant factor approximation algorithms, we design better heuristic algorithms to attack the problem, by building the connection of finding dense subgraphs with a variant of the Prize Collecting Steiner Tree problem. (3) Finally, we have conducted an extensive experimental study to demonstrate the effectiveness and efficiency of our approach, using real-life and synthetic data.

For a detection problem, a user often has some prior knowledge about the structure-specific subgraphs of interest, but few traditional approaches are capable of employing this knowledge. The main technical challenge is that few approaches can efficiently model the space of connected subgraphs that are isomorphic to a query graph. We present a novel, efficient approach for optimizing a generic nonlinear cost function subject to a query-specific structural constraint. Our approach enjoys strong theoretical guarantees on the convergence of a nearly optimal solution and a low time complexity. For the case study, we specialize the nonlinear function to several well-known graph scan statistics for anomalous subgraph discovery. Empirical evidence demonstrates that our method is superior to state-of-the-art methods in several real-world anomaly detection tasks.

Nowadays, various sensors are collecting, storing and transmitting tremendous trajectory data, and it is known that raw trajectory data seriously wastes the storage, network band and computing resource. Line simplification (LS) algorithms are an effective approach to attacking this issue by compressing data points in a trajectory to a set of continuous line segments, and are commonly used in practice. However, existing LS algorithms are not sufficient for the needs of sensors in mobile devices. In this study, we first develop a one-pass error bounded trajectory simplification algorithm (OPERB), which scans each data point in a trajectory once and only once. We then propose an aggressive one-pass error bounded trajectory simplification algorithm (OPERB-A), which allows interpolating new data points into a trajectory under certain conditions. Finally, we experimentally verify that our approaches (OPERB and OPERB-A) are both efficient and effective, using four real-life trajectory datasets.

A network with n nodes contains O(n2) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity on large networks. Hence, most known link prediction methods are designed for evaluating the link propensity on a specified subset of links, rather than on the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this article, we propose an ensemble enabled approach to scaling up link prediction, by decomposing traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with latent factor models, which can be effectively implemented on networks of modest size. By incorporating with the characteristics of link prediction, the ensemble approach further reduces the sizes of subproblems without sacrificing its prediction accuracy. The ensemble enabled approach has several advantages in terms of performance, and our experimental results demonstrate the effectiveness and scalability of our approach.

Temporal graphs are a class of graphs whose nodes and edges, together with the associated properties, continuously change over time. Recently, systems have been developed to support snapshot queries over temporal graphs. However, these systems barely support aggregate time range queries. Moreover, these systems cannot guarantee ACID transactions, an important feature for data management systems as long as concurrent processing is involved. To solve these issues, we design and develop TGraph, a temporal graph data management system, that assures the ACID transaction feature, and supports fast temporal graph queries.

Network anomaly detection has become very popular in recent years because of the importance of discovering key regions of structural inconsistency in the network. In addition to application-specific information carried by anomalies, the presence of such structural inconsistency is often an impediment to the effective application of data mining algorithms such as community detection and classification. In this paper, we study the problem of detecting structurally inconsistent nodes that connect to a number of diverse influential communities in large social networks. We show that the use of a network embedding approach, together with a novel dimension reduction technique, is an effective tool to discover such structural inconsistencies. We also experimentally show that the detection of such anomalous nodes has significant applications: one is the specific use of detected anomalies, and the other is the improvement of the effectiveness of community detection.

A network with $n$ nodes contains O(n2) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Furthermore, even though link prediction is closely related to missing value estimation problems, such as collaborative filtering, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity over very large networks. Due to this computational complexity, most known link prediction methods are designed for evaluating the link propensity over a specified subset of links, rather than for performing a global search over the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this paper, we propose an ensemble enabled approach to scaling up link prediction, which is able to decompose traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with the use of latent factor models, which can be effectively implemented over networks of modest size. Furthermore, the ensemble enabled approach has several advantages in terms of performance. We show the advantage of using ensemble-based latent factor models with experiments on very large networks. Experimental results demonstrate the effectiveness and scalability of our approach.

Computing shortest paths and distances is one of the fundamental problems on graphs, and it remains a challenging task today. This article investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. To do this, we propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We first show that routing proxies hold good properties for speeding-up shortest path and distance queries. Then, we design a linear-time algorithm to compute routing proxies and their corresponding DRAs. Finally, we experimentally verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

OS-level virtualization is often used for server consolidation in data centers because of its high efficiency. However, the sharing of storage stack services among the colocated containers incurs contention on shared kernel data structures and locks within I/O stack, leading to severe performance degradation on manycore platforms incorporating fast storage technologies (e.g., SSDs based on nonvolatile memories). This article presents MultiLanes, a virtualized storage system for OS-level virtualization on manycores. MultiLanes builds an isolated I/O stack on top of a virtualized storage device for each container to eliminate contention on kernel data structures and locks between them, thus scaling them to manycores. Meanwhile, we propose a set of techniques to tune the overhead induced by storage-device virtualization to be negligible, and to scale the virtualized devices to manycores on the host, which itself scales poorly. To reduce the contention within each single container, we further propose SFS, which runs multiple file-system instances through the proposed virtualized storage devices, distributes all files under each directory among the underlying file-system instances, then stacks a unified namespace on top of them. The evaluation of our prototype system built for Linux container (LXC) on a 32-core machine with both a RAM disk and a modern flash-based SSD demonstrates that MultiLanes scales much better than Linux in micro- and macro-benchmarks, bringing significant performance improvements, and that MultiLanes with SFS can further reduce the contention within each single container.

It is cost-prohibitive to find matches Q(G) of a pattern query Q in a big graph G. We approach this by fetching a small subgraph GQof G such that Q(GQ) = Q(G). We show that many practical patterns are effectively bounded under access constraints A commonly found in real life, such that GQcan be identified in time determined by Q and A only, independent of the size |G| of G. This holds no matter whether pattern queries are localized (e.g., via subgraph isomorphism) or non-localized (graph simulation). We provide algorithms to decide whether a pattern Q is effectively bounded, and if so, to generate a query plan that computes Q(G) by accessing GQ, in time independent of |G|. When Q is not effectively bounded, we give an algorithm to extend access constraints and make Q bounded in G. Using real-life data, we experimentally verify the effectiveness of the approach, e.g., about 60% of queries are effectively bounded for subgraph isomorphism, and for such queries our approach outperforms the conventional methods by 4 orders of magnitude.

Virtual machine (VM) snapshot enhances the system availability by saving the running state into stable storage during failure-free execution and rolling back to the snapshot point upon failures. Unfortunately, the snapshot state may be lost due to disk failures, so that the VM fails to be recovered. The popular distributed file systems employ replication technique to tolerate disk failures by placing redundant copies across disperse disks. However, unless user-specific personalization is provided, these systems consider the data in the file as of same importance and create identical copies of the entire file, leading to non-trivial additional storage overhead.

One of the most important crowdsourcing topics is to study the effective quality control methods so as to reduce the cost and to guarantee the quality of task processing. As an effective approach, iterative improvement workflow is known to choose the best result from multiple workflows. However, for complex crowdsourcing tasks that consists of a certain number of subtasks under some specific constraints, but cannot be split into subtasks to be crowdsourced, the approach merely considers the best workflow without integrating the contributions of all workflows, which potentially results in extra costs for more iterations. In this paper, we propose an assembly model to integrate the best output of subtasks from different workflows. Moreover, we devise an efficient iterative method based on POMDP to improve the quality of assembled output. Empirical studies confirms the superiority of our proposed model.

Mashing up Web services and RESTful APIs is a novel programming approach to develop new applications. As the number of available resources is increasing rapidly, to discover potential services or APIs is getting difficult. Therefore, it is vital to relieve mashup developers of the burden of service discovery. In this paper, we propose a probabilistic model to assist mashup creators by recommending a list of APIs that may be used to compose a required mashup given descriptions of the mashup. Specifically, a relational topic model is exploited to characterize the relationship among mashups, APIs and their links. In addition, we incorporate the popularity of APIs to the model and make predictions on the links between mashups and APIs. Moreover, the statistical analysis on a public mashup platform shows the current status of mashup development and the applicability of this study. Experiments on a large service data set confirm the effectiveness of this proposed approach.

Large-scale distributed storage systems often replicate data across servers and even geographically-distributed data centers for high availability, while existing theories like CAP and PACELC show that there is a tradeoff between availability and consistency. However, current practice is mainly experience-based and lacks quantitative analysis for identifying a good tradeoff between the two. In this work, we are concerned with providing a quantitative analysis on availability for widely-used quorum systems in data centers. First, a probabilistic model is presented to quantify availability for typical data center networks: 2-tier basic tree, 3-tier basic tree, fat tree and folded clos network. Second, we build the availability-consistency table and propose a set of rules to quantitatively make tradeoff between availability and consistency. Finally, with Monte Carlo based simulations, we validate our presented quantitative results and show that our approach to make tradeoff between availability and consistency is effective.

With the rapid proliferation of camera-equipped smart devices (e.g., smartphones, pads, tablets), visible light communication (VLC) over screen-camera links emerges as a novel form of near-field communication. Such communication via smart devices is highly competitive for its user-friendliness, security, and infrastructure-less (i.e., no dependency on WiFi or cellular infrastructure). However, existing approaches mostly focus on improving the transmission speed and ignore the transmission reliability. Considering the interplay between the transmission speed and reliability towards effective end-to-end communication, in this paper, we aim to boost the throughput over screen-camera links by enhancing the transmission reliability. To this end, we propose RDCode, a robust dynamic barcode which enables a novel packet-frame-block structure. Based on the layered structure, we design different error correction schemes at three levels: intra-blocks, inter-blocks and inter-frames, in order to verify and recover the lost blocks and frames. Finally, we implement RDCode and experimentally show that RDCode reaches a high level of transmission reliability (e.g., reducing the error rate to 10%) and yields a at least doubled transmission rate, compared with the existing state-of-the-art approach COBRA.

Visible light communication (VLC) over screen-camera links emerges as a novel form of near-field communication, and it offers a user-friendly, infrastructure-less and secure communication, which is highly competitive for one-time file transfer [1 - 4]. However, the limitations of smart devices and the uncertainty of user behaviors seriously impair the transmission reliability and hinder its applicability. Worse still, existing approaches [1, 2, 4]mostly focus on improving the transmission speed and ignore the transmission reliability. Hence, RDCode is proposed to boost the throughput over screen-camera links, by making use of a novel barcode design and several effective techniques to enhance the transmission reliability. In this demo, we show that our RDCode prototype system addresses many practical challenges.

Graph pattern matching is finding all matches in a data graph for a given pattern graph and is often defined in terms of subgraph isomorphism, an NP -complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow graph pattern matching to be conducted in cubic time. However, they fall short of capturing the topology of data graphs, that is, graphs may have a structure drastically different from pattern graphs they match, and the matches found are often too large to understand and analyze. To rectify these problems, this article proposes a notion of strong simulation , a revision of graph simulation for graph pattern matching. (1) We identify a set of criteria for preserving the topology of graphs matched. We show that strong simulation preserves the topology of data graphs and finds a bounded number of matches. (2) We show that strong simulation retains the same complexity as earlier extensions of graph simulation by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation which allows us to develop an effective distributed algorithm to conduct graph pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms using both real-life and synthetic data.

Existing theories like CAP and PACELC have claimed that there are tradeoffs between some pairs of performance measures in distributed replication systems, such as consistency and latency. However, current systems take a very vague view on how to balance those tradeoffs, e.g. eventual consistency. In this work, we are concerned with providing a quantitative analysis on consistency and latency for widely-used replicated state machines(RSMs). Based on our presented generic RSM model called RSM-d, probabilistic models are built to quantify consistency and latency. We show that both are affected by d, which is the number of ACKs received by the coordinator before committing a write request. And we further define a payoff model through combining the consistency and latency models. Finally, with Monte Carlo based simulation, we validate our presented models and show the effectiveness of our solutions in terms of how to obtain an optimal tradeoff between consistency and latency.

The increasing availability of socially shared media with tags annotated makes it vital for retrieval approaches to precisely detect web content topic semantic and better understand user interest. Most existing methodologies process the queries merely considering user posted keywords and retrieve media labeled with tags that are similar to query words, while ignoring users implicit interests and preferences. This fact stimulates us to develop preference discovering models to reveal the users' latent intents. In this paper, we study the problem of finding user preference and interest from folksonomy corpus and propose a preference-topic model that exploits probabilistic graphical model and Gibbs sampling algorithm to infer the user interested latent semantic topics. The experimental results show that, with the help of the proposed model, preference topics of the web content creators can be effectively discovered. In addition, two exemplified applications are discussed briefly.

Live virtual machine migration is a technique often used to migrate an entire OS with running applications in a non-disruptive fashion. Prior works concerned with one-to-one live migration with many techniques have been proposed such as pre-copy, post-copy and log/replay. In contrast, we propose VMScatter, a one-to-many migration method to migrate virtual machines from one to many other hosts simultaneously. First, by merging the identical pages within or across virtual machines, VMScatter multicasts only a single copy of these pages to associated target hosts for avoiding redundant transmission. This is impactful practically when the same OS and similar applications running in the virtual machines where there are plenty of identical pages. Second, we introduce a novel grouping algorithm to decide the placement of virtual machines, distinguished from the previous schedule algorithms which focus on the workload for load balance or power saving, we also focus on network traffic, which is a critical metric in data-intensive data centers. Third, we schedule the multicast sequence of packets to reduce the network overhead introduced by joining or quitting the multicast groups of target hosts. Compared to traditional live migration technique in QEMU/KVM, VMScatter reduces 74.2% of the total transferred data, 69.1% of the total migration time and achieves the network traffic reduction from 50.1% to 70.3%.

Web services are widely used to enable remote access to heterogeneous resources through standard interfaces and build complex applications by reusing existing component services. However, massive commodity computers, storage, network devices and complex management tasks running behind web services make them subject to outage and unable to provide continuously reliable services. To address this issue, we present a Paxos-based replication framework for building consistent and reliable web services. The framework mainly consists of a replication protocol and a set of failure tackling algorithms. First, in the replication protocol, besides keeping consistency of service replicas we introduce pipeline concurrency and RDG (Request Dependency Graph) to traditional Paxos so as to improve its performance. Second, we design failure recovery algorithms to recover the failed nodes, which guarantee that each web service has enough available replicas and thus can deliver expected reliability. Third, through an extensive set of experiments, we show that our method is effective in terms of keeping consistency and reliability of web services and it outperforms other replication methods.

We consider the problem of elastic-demand network equilibrium in communication networks which support both multirate multicast sessions and unicast sessions. Extending existing work for unicast sessions, we first present the elastic-demand network equilibrium models in different multicast sessions, which can be formulated as a convex programming problem. To solve the convex programming problem we use the augmented Lagrangian multiplier algorithm in which the attractive features of the exterior penalty with primal-dual methods and Lagrangian multipliers concepts are combined while curtailing the disadvantage of both. Some numerical results about unicast sessions and multirate multicast sessions are demonstrated through efficient implementations of the augmented Lagrangian multiplier algorithm.

This paper presents an global social travel system to assist tourists in their itinerary planning, tour navigation, and travel knowledge sharing. In particular, firstly, we propose an efficient and flexible itinerary planning algorithm for organizing itineraries. Secondly, we design an intelligent tour path planning and navigation system by mining patterns from trajectories and geo-photos shared by other tourists. Thirdly, we provide a framework to monitor the status and events that may affect the predefined itineraries. Finally, the social media module enhances the opportunities of experience (itinerary, trajectory, and travelogue) sharing and helps travelers make better decisions. Concrete demonstrations of our system are also provided in this paper to show the flexibility and applicability of our system.

Graph simulation has been adopted for pattern matching to reduce the complexity and capture the need of novel applications. With the rapid development of the Web and social networks, data is typically distributed over multiple machines. Hence a natural question raised is how to evaluate graph simulation on distributed data. To our knowledge, no such distributed algorithms are in place yet. This paper settles this question by providing evaluation algorithms and optimizations for graph simulation in a distributed setting. (1) We study the impacts of components and data locality on the evaluation of graph simulation. (2) We give an analysis of a large class of distributed algorithms, captured by a message-passing model, for graph simulation. We also identify three complexity measures: visit times, makespan and data shipment, for analyzing the distributed algorithms, and show that these measures are essentially controversial with each other. (3) We propose distributed algorithms and optimization techniques that exploit the properties of graph simulation and the analyses of distributed algorithms. (4) We experimentally verify the effectiveness and efficiency of these algorithms, using both real-life and synthetic data.

Graph pattern matching is often defined in terms of subgraph isomorphism, an np-complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow pattern matching to be conducted in cubic-time. However, they fall short of capturing the topology of data graphs, i.e. , graphs may have a structure drastically different from pattern graphs they match, and the matches found are often too large to understand and analyze. To rectify these problems, this paper proposes a notion of strong simulation , a revision of graph simulation, for graph pattern matching. (1) We identify a set of criteria for preserving the topology of graphs matched. We show that strong simulation preserves the topology of data graphs and finds a bounded number of matches. (2) We show that strong simulation retains the same complexity as earlier extensions of simulation, by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation, which allows us to effectively conduct pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms, using real-life data and synthetic data.

Reuse is an important mechanism for improving the efficiency of software development. For Internet-scale software produced through service composition, the simple reuse granularity at service is often inefficient due to the large number of available services. This paper proposes a novel architecture which enables efficient reuse of process fragments. In the proposed architecture, services are organized into a network, called Service Composition Network (SCN), based on their co-occurence in the existing composite services. The reusable process fragments are extracted by decomposing existing composite services according to both the structural constraint of the process and the relevance of services in the same process fragment. The design principles and a prototype implementation of this architecture are presented, the performance of the proposed approach is analyzed, and an application is described to demonstrate the effectiveness of it.

With the increasing prevalence of large scale cloud computing environments, how to place requested applications into available computing servers regarding to energy consumption has become an essential research problem, but existing application placement approaches are still not effective for live applications with dynamic characters. In this paper, we proposed a novel approach named EnaCloud, which enables application live placement dynamically with consideration of energy efficiency in a cloud platform. In EnaCloud, we use a Virtual Machine to encapsulate the application, which supports applications scheduling and live migration to minimize the number of running machines, so as to save energy. Specially, the application placement is abstracted as a bin packing problem, and an energy-aware heuristic algorithm is proposed to get an appropriate solution. In addition, an over-provision approach is presented to deal with the varying resource demands of applications. Our approach has been successfully implemented as useful components and fundamental services in the iVIC platform. Finally, we evaluate our approach by comprehensive experiments based on virtual machine monitor Xen and the results show that it is feasible.

Composite service evolution is one of the most important challenges to deal with in the field of service composition. In particular, this paper presents, LiveMig, an approach to live migration of composite service instance, which is a critical step for online composite service evolution. In LiveMig, a set of change operations preserving soundness is first defined. Second, a live instance state migration algorithm is proposed to determine if the state migration is allowed or not, and to compute the exact state after the migration. Finally, the correctness of LiveMig is theoretically proved, and an extensive set of simulations are performed to show its feasibility and effectiveness.

In recent years, many QoS-based web service selection methods have been proposed. However, as QoS changes dynamically, the atomic services of a composite web service could be replaced with other ones that have better quality. The performance of a composite web service will be decreased if this replacement happens frequently in runtime. Predicting the change of QoS accurately in select phase can effectively reduce this web services “thrash”. In this paper, we propose a web service selection algorithm GFS (Goodness-Fit Selection algorithm) based on QoS prediction mechanism in dynamic environments. We use structural equation to model the QoS measurement of web services. By taking the advantage of the prediction mechanism of structural equation model, we can quantitatively predict the change of quality of service dynamically. Optimal web service is selected based on the predicted results. Simulation results show that in dynamic environments, GFS provides higher selection accuracy than previous selection methods.

In this paper, we propose a novel approach for composing existing web services to satisfy the correctness constraints to the design, including freeness of deadlock and unspecified reception, and temporal constraints in Computation Tree Logic formula. An automated synthesis algorithm based on learning algorithm is introduced, which guarantees that the composite service is the most general way of coordinating services so that the correctness is ensured. We have implemented a prototype system evaluating the effectiveness and efficiency of our synthesis approach through an experimental study.

Grid computing has emerged as a new paradigm of distributed computing technology on large-scale resource sharing and coordinated problem solving. Based on a proposed Web service-based grid architecture, we have designed a service grid middleware system called CROWN which aims to promote the utilization of valuable resources and cooperation of researchers nationwide and world-wide. To address the issues of CROWN resource management, we proposed some key technologies including trustworthy remote and hot service deployment, overlay-based distributed resource organization, resource scheduling and load balance, and federation-based virtual organization management. A status of the wide-area CROWN testbed is also introduced in this paper. Three typical applications including AREM, MDP and gViz are deployed on the CROWN testbed. Experience of CROWN testbed deployment and application development shows that the middleware can support the typical scenarios such as computing-intensive applications and data-intensive applications etc.

Most of the current trust models in peer-to-peer (P2P) systems are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. Hence, there exists an inherent tradeoff between trust and anonymity. To the best of our knowledge, there is currently no P2P protocol that provides complete mutual anonymity as well as authentication and trust management. We propose a zero-knowledge authentication scheme called pseudo trust (PT), where each peer, instead of using its real identity, generates an unforgeable and verifiable pseudonym using a one-way hash function. A novel authentication scheme based on zero-knowledge proof is designed so that peers can be authenticated without leaking any sensitive information. With the help of PT, most existing identity-based trust management schemes become applicable in mutual anonymous P2P systems. We analyze the security and the anonymity in PT, and evaluate its performance using trace-driven simulations and a prototype PT-enabled P2P network. The strengths of our design include (1) no need for a centralized trusted party or CA, (2) high scalability and security, (3) low traffic and cryptography processing overheads, and (4) man-in-middle attack resistance.

Encouraging resource sharing and cooperation among different parties is one of the central goals of grid computing. In real environments, however, selfish or malicious nodes can seriously degrade the sharing and cooperation performance of a grid. To solve this problem, we propose QIA, a novel Q-learning based resource Allocation mechanism that sustains Incentive for every participating node. Exploiting an economic model, QIA recognizes the importance of trust factor when allocating resources. Each provider considers a combined metric, which is composed of the bid price and the trust value, of a requester when allocating its resources. The incomplete information is a key issue for a provider in determining the relative weight of bid price and trust value. We propose a reinforcement Q- learning technique to resolve the issue, which is able to adapt the dynamics of grid environments. We implemented QIA in a real grid test-bed, CROWN grid. Comprehensive experiments have been conducted, which demonstrate the efficacy of QIA.

Although many efforts have been put on the load balance in network and job scheduling systems, most of them, however, can not be applied in the service grid environment directly since they are often designed for a homogeneous system with limited scalability. It is still a challenge problem to balance the load among service grid nodes which are often highly dynamic, heterogeneous and linked by wide-area network. In this paper, we present a load balance strategy using several bulletin-boards as load intermediates among grid nodes. A modified thresholds based load transfer algorithm has been applied with a non-preemptive selection policy. Based on the strategy above, a load balance system is realized in CROWN, a service oriented grid middleware, and deployed in the CROWN testbed. The performance evaluations have shown that our strategy can effectively balance the load of service invocation, and improve the system throughput.

With the fast development of Internet and rapid acceptance of Web Service technology, more and more service resources have emerged. Service composition which integrates the functionalities of different services is a promising technique for developing applications across multiple organizations. However, in a distributed, dynamic and autonomous environment, such as a service composition-based system, the availability and reliability are big concerns in terms of nonfunctional properties. In this paper, we propose a novel service composition method, ANGEL, with the target of the improvement of system availability. We adopt redundant mechanism in ANGEL and propose a model to improve the property of the service availability. We model the multiple services selection problem based on redundant mechanism as a nonlinear mixed integer programming problem and therefore, we propose two heuristic algorithms to select multiple feasible services that have the same functions, but with better availability. In order to maintain the availability of composite services, we further introduce monitor and detection mechanisms. Through the comprehensive experiments, we find that our proposed techniques can indeed achieve better availability as expected.

As the amount of Web services over the Internet grows continuously, these services can be interconnected to form a service overlay network (SON). On the basis of SON, building value-added services by service composition is an effective method to satisfy the changeable functional and non-functional QoS (quality of service) requirements of customers. However, the previous research on QoS- aware service composition in SON mainly focuses on the context where services have simple interactions, and it can not support application scenarios with complex business collaboration in electronic business. In this paper, we propose the HOSSON (hierarchical service composition framework in SON) framework, which can be used to construct more general-purpose SON through describing the relations among services using business protocols. In HOSSON, business protocols instead of interactive messages are adopted to simplify the description of service composition requirements and a novel approach named protocol computing are proposed to implement service composition on demand. Furthermore, two algorithms, OSS and MCSS, are designed to support service selection for QoS-aware service composition. Finally, comprehensive simulations are conducted to evaluate the performance of algorithms.

Most of the current trust models in peer-to-peer (P2P) systems are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. Hence, there exists an inherent tradeoff between trust and anonymity. To the best of our knowledge, there is currently no P2P protocol that provides complete mutual anonymity as well as authentication and trust management. We propose a zero-knowledge authentication scheme called pseudo trust (PT), where each peer, instead of using its real identity, generates an unforgeable and verifiable pseudonym using a one-way hash function. A novel authentication scheme based on zero-knowledge proof is designed so peers can be authenticated without leaking any sensitive information. With the help of PT, most existing identity-based trust management schemes become applicable in mutual anonymous P2P systems. We analyze the levels of security and anonymity in PT, and evaluate its performance using trace-driven simulations and a prototype implementation. The strengths of pseudo trust include the lack of need for a centralized trusted party or CA, high scalability and security, low traffic and cryptography processing overheads, and man-in-middle attack resistance. We aim for the pseudo trust design to be included in the P2P trust and anonymity context.

The increasing complexity and dynamics of grid environments have posed great challenges for secure and privacy-preserving collaboration in a virtual organization. In this paper, we propose PEACE-VO, a secure policy-enabled collaboration framework for virtual organizations. PEACE-VO employs role mapping to define trust relationships across autonomous domains. Nevertheless, a critical issue emerges when the system applies role mapping, which is potential policy conflict in a local domain. We first develop two concepts to depict such possible conflicts within the collaboration policy. Next, we propose a fully distributed evaluation algorithm to detect potential policy conflicts, which does not require domains to disclose their full local security policies and therefore preserves critical domain privacy. Finally, we design two dedicated protocols for virtual organization management and authorization services, respectively. We have successfully implemented the PEACE-VO framework with two fundamental protocols, i.e., VO management protocol and service authorization protocol, in the CROWN grid. Comprehensive experimental study shows our approach is scalable and efficient.

In order to establish trust relationship between service requesters and providers in an open decentralized environment, we propose a novel trust negotiation framework, TOWER, which integrates distributed trust chain construction of trust management and aims to enhance the grid security infrastructure. Our approach leverages attribute-based credentials to support flexible delegation, and dynamically constructs trust chains. A novel TRust chAin based Negotiation Strategy (TRANS) is proposed to establish trust relationship on the fly by gradually disclosing credentials according to various access control policies. Our approach has been successfully implemented as useful components and fundamental security services in the CROWN Grid, and techniques such as trust tickets and policy caching that can greatly increase service efficiency are used. Finally, we evaluate our approach by comprehensive experiments and the results show that it is feasible.

CROWN is a service-oriented grid computing middleware enabling resources integration in multiple heterogeneous domains and establishing dynamic cooperative relationship among researchers nationwide and worldwide. However, several security challenges should be addressed in CROWN due to the heterogeneous distribution of resources and the dynamic collaborations and resource sharing. In this paper, we present a security and trustworthiness architecture, CROWN-ST, for CROWN. The aim of this architecture is to provide a fine-grained and extensible framework for security and trustworthiness that enables employing distributed access control and dynamic trust establishment among service providers and consumers in a Grid environment. Based on this open and flexible architecture, a series of fundamental services which consist of secure communication, authentication, access control, credential federation, trust management and negotiation are implemented. Finally, comprehensive experimental studies are conducted to demonstrate the feasibility and performance of current CROWN-ST implementation.

Computational resource discovery is of great importance in grid environments. Existing approaches do not consider the characteristics of application resource requirements. We propose, Resource Category Tree (RCT), which organizes computational resources based on their characteristics represented by primary attributes (PA). RCT adopts a structure of AVL tree, with each node representing a specific range of PA values. Though RCT adopts a hierarchical structure, it does not require nodes in higher levels maintain more information than those in lower levels, which makes RCT highly scalable. RCT is featured by self-organization, load-aware self-adaptation and fault tolerance. Based on RCT, commonly used queries, such as range queries and multi-attribute queries, are well supported. We conduct performance evaluations through comprehensive simulations.

In order to maximize resource utilization as well as providing trust management in grid, we propose a novel framework - Trust-Incentive Resource Management (TIM). Having child model, club model, bid model and trust model, TIM dynamically manages grid resource by integrating values of prices, trust, and incentive. In this mechanism, providers set the price according to demand and supply, and consumers maximize the surplus upon budget and deadline. A weighted voting scheme is also proposed to secure the grid system by declining the join request from malicious nodes. A TIM prototype has been successfully implemented in a real grid system, CROWN grid. We evaluate the proposed approach through comprehensive experiments and achieve improved results in resource allocation efficiency, system completion time, and aggregated resource utilization.

Our key project, CROWN (China Research and Development Environment Over Wide-area Network), aims to empower in-depth integration of resources and cooperation of researchers nationwide and worldwide using grid technologies. It adopts service oriented architecture. Current service grids do not consider the separation of services and underlying resources, potentially causing low job processing efficiency and resource utilization. In this paper, we propose a novel architecture for grid systems, called Open Service Provisioning and Consuming Environment (OpenSPACE). OpenSPACE is adopted by CROWN and is evaluated by prototype implementation based on real applications.

Service grid is a widely distributed environment, where service deployers and containers may be located in different autonomous domains. In such cases, different from traditional scenarios such as J2EE applications, the access control policy should not be determined by a deployer or a container only. Existing grid application deployment solutions do not address this unique requirement. In this paper, we propose a general approach, namely CROWN.ST, an access control policy negotiation solution for remote hot-deployment of grid services in CROWN (China R&D Environment Over Wide-area Network). Based on an access control policy language derived from non-recursive stratified Datalog with constraints, we design the negotiation procedure and three types of meta-policies. We implement a CROWN.ST prototype and evaluate our design by comprehensive experiments

Security in collaborative groups is an active research topic and has been recognized by many organizations in the past few years. In this paper, we propose a fine-grained and attribute-based access control framework for our key project, CROWN grid. To avoid single point of failure and enhance scalability of the system, we employ a distributed delegation authorization mechanism. We successfully implement our proposed access control in CROWN grid, and evaluate this approach by comprehensive experiments.

Inter-organizational business processes usually require complex and time-consuming interactions between partners than simple interactions supported by WSDL. Automated reconciliation is essential to enable dynamic inter-organizational business collaboration. To the best of our knowledge, however, there is not a practical automated reconciliation algorithm available. In this paper, we propose a practical automated reconciliation algorithm, called IPR (interaction process reconciliation) based on Petri net, which is able to effectively facilitate dynamic interactions among trading partners in a peer-to-peer fashion. We implement a prototype IPR server in our lab, and evaluate our design by comprehensive experiments. Results show that IPR significantly outperforms existing approaches in terms of matching success rate, response time, and matching efficiency.

The author first discusses the status of knowledge base management systems (KBMSs). A new data model and an approach for knowledge base management systems is presented regarding the integration of the relational model with term rewriting techniques. Based on this model an efficient KBMS has been designed and implemented with C and ORACLE, which has the following features: multi-user languages on the extensions of SQL, QBE and PROLOG; data/knowledge definition, representation and manipulation; reasoning and explaining; security and integrity check; and optimal recursive processing.>