Abstract:Bigraph was proposed by Robin Milner in 2001 as a formal theoretical model based on graphs in attempt to provide a design, simulation and analysis platform for ubiquitous computing and present a unified, extensible framework for the existing process algebra. In this paper first introduces the basic concepts of bigraph and reveals relationships among precategory, category, s-category and symmetric partial monoidal category which form the mathematical basis of bigraph, and then summarizes bigraphical algebra system while providing a simplified representation of the discrete normal form in bigraph with a proof. Next, it discusses some questions related to the definition of bigraphical categories and quotient translations after making a survey of the development of bigraph and its applications. This study argues that bigraphical category should be small category other than large category. Moreover, the paper illustrates how to convert the large category derived by quotient to small category. Finally, it outlines the extensions of bigraphical models and their applications.

Abstract:The intermediate logic is a three-valued logic proposed by Zhu Wu-Jia. A propositional intermediate logic is proposed in this paper where the intermediate unary connective ~ and the contrary connective ◁ are introduced, and the negative connective ¬ is defined in terms of the unique binary connective →. A Gentzen-typed deduction system is given such that the system is sound and complete with the three-valued semantics of the propositional intermediate logic.

Abstract:Soft error has a great influence on computing reliability of space devices and could result in silent data corruption (SDC), which means wrong outcomes of a program without any crash detected. As SDC-causing fault always propagates silently, it is very difficult to detect SDC. In this paper, an approach for detecting SDC is proposed by using program invariant. A program invariant is a set of properties of program. Normally, the invariant holds during runtime. But when soft error occurs, the invariant is often violated due to the impact of soft error. Based on this principle, invariant-based asserts are inserted into source code. Once an exception is thrown by an assert, it indicates that soft error is detected. By analyzing the propagation of the fault that leads to SDC, the locations where asserts are embedded are selected and then invariants are extracted. Some of the invariants are converted to asserts based on their permeability, which indicates the capabilities of detecting soft error. The proposed approach is evaluated by fault injection experiment which shows that it achieves high coverage with low overhead. The approach broadens the ways of protecting satellite system from soft error.

Abstract:With the development of distributed computing, service-based software system which is constructed mainly by self-management Web services has become the main trend of software structure. The structure and behavior of service-based software system are continuously changed with user demands. Aiming at complex execution behaviors of web services, this paper presents an evolution model of dynamic behavior based on service interaction characteristics. Based on the WSDL documents of Web services, this model first builds complex structural network for the development evaluation of service-oriented software system. Taking into consideration of the optimal selection of Web services, characters of combination interaction and dynamic recombination, this work models the growth evolution and dynamic behavior of service-based software systems. Experiments are performed on large-scale real Web service data sets, such as Seekda and QWS. Different from hierarchical topological structure of traditional software system, the results show that the software systems consisted of self-management Web service exhibit more modularity structure. Compared with the regulation of single Web service evolution in the system, such as preferential attachments and dynamic recombination, the property of service structure network has more significant influence to the final form of the system. This model is instructive and meaningful to the analysis and management of service software.

Abstract:Microblogs have gradually become popular platforms for users to acquire and share information with the public, which have brought a profound impact on information propagation. This paper presents a survey of predicting information propagation in microblogs. It is important to public opinion monitoring, online marketing and personalized recommendation. The paper first introduces the mechanism of information propagation, and reveals the characteristics of information propagation in microblogs through a brief overview of the qualitative research. Then, representative work is reviewed for the prediction of information propagation from three aspects including information centered prediction, user centered prediction and information-user centered prediction. The three corresponding tasks are predicting the popularity of information, predicting individual spread behaviors and predicting the path of information dissemination respectively. Next, the publicly available data sets for information propagation in microblogs are summarized. Finally, the key challenges are discussed to suggest the future research directions.

Abstract:Multi agent system, one of important branches of distributed artificial intelligence, has been widely applied to modeling a serious of complex systems in diverse research fields. Significant research effort has sought to solve constraint programming with distributed constraint optimization which is a popular framework for multi agent system. The contributions of this research proceed from previous work in the following ways. First, based on the existing research, the applicability of distributed constraint optimization is analyzed, and general process of distributed constraint optimization algorithms is extracted. Second, a relatively complete classification of algorithms is provided from the perspective of quality assurance and solving strategies. Next, considering execution mechanism, a thorough analysis of a large number of classic algorithms proposed in recent years is carried out. Moreover, the experimental analysis of some typical algorithms with the metrics of communication, solution quality and efficiency is provided. Finally, combining the advantage of distributed constraint optimization technology, the application characteristics of distributed constraint optimization problem are proposed, and future work is discussed.

Abstract:Chinese event trigger extraction is a challenging task. To tackle the difficulties of obtaining the semantic information of event arguments and extracting those context-poor event mentions in Chinese event trigger extraction, this paper proposes a semantics-driven joint model to integrate the components of Chinese event trigger extraction. First, considering the nature of Chinese language (e.g., flexible sentence structure and ellipsis), it provides a pattern-based method to identify core arguments and supplement arguments to better represent argument semantics, and applies the method to improve the performance of Chinese trigger extraction. Secondly, regarding the consistency among relevant event mentions in a document or discourse, it introduces the semantics among relevant event mentions to formulate a 2-dimensional joint model of Chinese trigger detection and type allocation to extract those context-poor event mentions. Finally, it provides experimental results on the ACE 2005 Chinese corpus to show that the presented model significantly outperforms the state-of-the-art system.

Abstract:Rough set theory proposed by professor Pawlak is an important mean to solve the problem of uncertain boundary region. Pawlak constructed two crisp boundaries for the set with uncertainty boundary but did not give any exact or approximate methods of using the existing knowledge base to build an approximation set of a target concept .In order to solve this problem, in the previous researches a method for looking for this kind of approximation target concept (set) is proposed. However, that method does not give out a kind of optimal approximation set. In this paper, firstly, the concept of the similarity between the target set and its approximation set and the method for constructing approximation set of rough set are reviewed, and the operation properties are proposed and proved respectively. Secondly, an interval of λ is found, and in this interval R_λ(X) is more similar to the target concept X than the upper-approximation set R(X) or lower-approximation set R(X). Finally, the conditions of R_0.5(X) as an optimal approximation set of the target concept X are proposed.

Abstract:The current research on information extraction mainly focuses on affirmative information. However there are more negation and uncertainty information in natural language texts. For purpose of separating them from affirmative information, it is necessary to make an intensive study of negation and uncertainty information extraction. For this task, this study firstly constructs a Chinese corpus including 16 841 sentences. Employing the sequence labeling model and the convolution tree kernel model, it systematically explores the efficiency of various kinds of serialized dependency features and structured parsing features. Finally, it proposes a meta-decision tree model to integrate the above two models. Experimental results show that the performances of the new method on negation and uncertainty information extraction achieve 69.84% and 58.57% of accuracy respectively, providing a solid foundation for related studies in the future.

Abstract:As more and more data have both spatial and textual attributes, spatial keyword query (SKQ) has been proposed to enhance the data search. An SKQ takes a spatial location and a set of keywords as arguments, and returns objects satisfying spatial and textual constraints which are then probably ranked according to certain functions. This paper investigates the current spatial keyword search techniques. It first defines the problem and analyzes the challenges. Then, it discusses the basic spatial keyword query processing techniques. Specifically, it categorizes the proposed queries according to their components, and then classifies the existing query processing techniques into three groups. For each group, the paper reviews the proposed indexing and query processing techniques. The paper also compares these techniques from several perspectives. In addition, it discusses extensions to the basic SKQ. Finally, it addresses research work related to SKQ, as well as some future research directions.

Abstract:Moving object gathering pattern represents a group event or incident that involves congregation of moving objects, enabling the prediction of anomalies in traffic system. However, effectively and efficiently discovering the specific gathering pattern remains a challenging issue since the large number of moving objects generate high volume of trajectory data. In order to address this issue, this article proposes a moving object gathering pattern mining method that aims to support the mining of gathering patterns by using spatio-temporal graph. In this method, firstly an improved density based clustering algorithm (DBScan) is used to collect the moving object clusters. Then, a spatio-temporal graph is maintained rather than storing the spatial coordinates to obtain the spatio-temporal changes in real time. Finally, a gathering mining algorithm and its improved version are developed by searching the maximal complete graphs which meet the spatio-temporal constraints. The effectiveness and efficiency of the proposed methods are outperformed other existing methods on both real and large trajectory data.

Abstract:Since the semantic social network (SSN) is a new kind of complex networks, the traditional community detection algorithms which require presetting the number of the communities, cannot detect the overlapping communities. To solve this problem, an overlapping community structure detecting algorithm in semantic social networks based on the link-block is proposed. First, the measurement of the semantic weight of links for the link-block is established depending on the analysis of LBT. Secondly, a method to measure the semantic links weight of link-block area is developed to provide the measurement of semantic information. Thirdly, the overlapping community detection cluster method is designed, based on the semantic weight of links, with the link-block as the element. Finally, the SQ modularity for the measurement of semantic communities is obtained. The efficiency and feasibility of the algorithm and the semantic modularity are verified by experimental analysis.

Abstract:Various approaches have been proposed to release histogram on static datasets with differential privacy, while little work exist that handle dynamic datasets. Those existing static approaches are ill-suited for the practical applications on data stream due to the inherent complexity of publishing streaming histograms. With this consideration, this paper addresses the challenge by proposing a partitioning-based method, called SHP (streaming histogram publication), which partitions the count values of each sliding window into different groups for releasing the final histogram. In view of different global sensitivity of queries adopted by this paper, three incremental utility-based mechanisms for adding Laplace noise are proposed to achieve differential privacy. The three mechanisms are sliding window mechanism, time point mechanism, and adaptive sampling mechanism, respectively. In the third mechanism, SHP relies on the adaptive sampling method to predict the next arriving count value at non-sampling time points. If the difference between the predicted value and the true value is less than a user-defined threshold, then it releases the predicted value, otherwise, releases the true value. This mechanism can save privacy budget in terms of sampling interval updates. Experimental results or real datasets show that the utility of SHP based on sampling is better than the other two mechanisms.

Abstract:Software defined network (SDN) is an emerging network paradigm that proposes to decouple the control and data forwarding plane. Leveraging the centralized control ability and open programming interfaces SDN provides, network management can be dramatically simplified, and network services can be dynamically controlled by applications. Traffic engineering (TE) is a category of mechanisms that promises to optimize network performance through analyzing, predicting and regulating data flow in network. The unique features of SDN provide TE with unified and real-time global network view, flexible control manner and better policy for scalable traffic management, exhibiting profound research significance. This paper surveys the state-of-art works on TE for SDN. In terms of the methods, application and deployment of measurement, works on traffic measurement architecture, network invariant detection and measurement resource management with SDN are reviewed. The problems in traditional network traffic management are analyzed, and SDN-based data traffic management methods for efficient load balance and control traffic management methods for centralized bottleneck relief are presented. Moreover, network failure resilience technologies in SDN are described. Finally, the technological approaches are summarized and future research issues are discussed.

Abstract:Coverage and connectivity are basic problems in WSN. This paper studies distributed coverage and connection hole repairing scheme (DHCRS) based on the probabilistic sensing model in hybrid WSN. This method detects probabilistic coverage holes and builds the model of their repairing radius. It also creates relationship model between the repairing radius and the repairing displacement of mobile sensor. This displacement not only determines the priority of the hole with its area, but also confirms the destination of mobile sensor in repairing circle of coverage hole. Once mobile node moved to this location, coverage hole simultaneously satisfy minimum detection probability and connectivity. Each mobile sensor repairs the hole of the highest priority. Simulation results show the proposed algorithm effectively obtains better probabilistic coverage rate and maintains the network connectivity at the same time.

Abstract:Vehicular ad hoc networks (VANETs) are characterized by intermittent connectivity, high mobility of vehicle nodes and dynamic topology. This makes data delivery in VANETs very challenging. Pervious works that based on historical traffic pattern or historical data delivery delay to predict current traffic conditions on the roads are not accurate. Deploying roadside units (RSUs) is a possible solution to overcome the challenges, but it often requires investment. Driven by the fact that there are large amounts of outside parked vehicles in urban areas, this paper proposes a parking backbone based data delivery paradigm (PBBD) for VANETs. PBBD does not need any RSUs, but leverages a virtual overlay network formed by outside parked vehicles to help transmitting messages among vehicles. This scheme consists of two parts. First, to each road, parked vehicles both at roadside and off-street are grouped into a cluster as large as possible. An urban overlay network is established based on this type of clusters for data transmission. Secondly, novel message delivery schemes are designed to efficiently transmit messages to destination vehicles through the proposed virtual overlay network. Simulation results based on a real city map and realistic traffic situations show that PBBD achieves a higher delivery ratio with lower network transmission overhead and reasonable transmission delay.

Abstract:This paper analyzes the traditional anonymous roaming authentication protocol, and points out the deficiencies of their uncontrolled anonymity and communication delay. A controllable anonymous roaming authentication protocol is proposed in this paper for heterogeneous wireless networks. This protocol can complete verifying the legitimacy of the identity of the mobile terminal through one message interaction. If the mobile terminal has malicious operation, the home network authentication server can help remote network authentication server to revoke the identity anonymity of the mobile terminal. The protocol accomplishes anonymous authentication and possesses controllability on malicious anonymity at the same time, thus effectively preventing the occurrence of malicious behavior and the communication delay. This protocol is safe in the CK security model.

Abstract:Virtualization technology is becoming more and more prevalence with the rise of cloud computing. The physical machines for service hosting are gradually being replaced by virtual ones. Driven by reliability and flexibility considerations, virtual machine images increase sharply, and how to manage them efficiently and economically has become a big challenge. Since large amount of duplicated data blocks exist in different virtual machine images, an efficient deduplication method is vital to the virtual machine image management. The existing deduplication works are not very suitable for cloud environments as they employ time-consuming algorithms which can cause serious performance interference to the neighboring virtual machines. This paper proposes a local deduplication method which can greatly optimize the deduplication process of virtual machine. The main idea of the method is to convert the global deduplication to a local one, thus considerably reducing the space and time complexity. In this method, the images are classified into different groups through an improved k-means clustering algorithm according to image similarities. When a new image is entered, a sampling method is used to choose an appropriate group to perform the deduplication operation. Experiments show that this approach is robust and effective. It can significantly reduce (more than 50%) the performance interference to hosting virtual machine with an acceptable increase (about 1%) in disk space usage.

Abstract:Traditional kernel monitoring models based on virtualization have two main drawbacks: 1) Virtual machine monitor (VMM) is vulnerable to attacks due to its non-trivial complexity and considerable attack surface; 2) VMM executes redundant virtualization functionalities, leading to heavy performance loss. To address those issues, this paper proposes a secure and efficient kernel monitoring model, named HyperNE, based on hardware virtualization. In HyperNE, any virtualization functionalities that are isolation and protection unrelated are removed from VMM, and guest OS is allowed to directly conduct privileged operations with no need to interact with VMM. Meanwhile, without sacrificing isolation guarantees, HyperNE utilizes a newly supported virtualization feature to transfer execution between security monitoring applications and guest OS in a controlled manner with no VMM involvement. As a result, HyperNE can not only eliminate the attack surface of VMM and effectively reduce trusted computing base (TCB) size of monitoring model, but also greatly improve system and monitoring performance by avoiding virtualization overheads.