Abstract:According to parameterized complexity theory, a decidable parameterized problem is fixed-parameter tractable if and only if it can be kernelized. Kernelization is the most widely applied and effective technique in the parameterized algorithm design. It is one of the hottest issues in parameterized complexity theory. This paper firstly introduces four main kernelization techniques, which are compared and analyzed with practical examples. Then it discusses how to apply these techniques to parameterized problems, such as covering problems, packing problems and cutting problems. Finally, the paper gives the future research directions about kernelization, especially the new possible kernelization technique and the kernel optimization of several FPT problems.

Abstract:The Strip-Mining technique is significant for improving SRF bandwidth utilization on the stream processor. It is critical to quantify the program execution time influenced by the strip size for achieving optimalstrip size. In order to achieve the theoretical optimal strip size, this paper proposes an optimal strip-miningtechnique based on a parameter model to minimize the execution time. Firstly, the paper builds a prefetching and reusing optimizations guided parameter model that characterizes the effect of strip size on program behavios.Secondly, based on the model analysis, this paper explores the optimal strip size selection approaches to the computation intensive programs and memory intensive programs respectively. Finally, an optimal strip-miningtechnique for any program is proposed. The experimental results show that our strip-mining technique caneffectively hide and avoid the memory access latency, so as to exploit the powerful computation ability of stream processor.

Abstract:The key of optimizing quantum reversible logic lies in automatically constructing quantum reversible logic circuits with the minimal quantum cost. In order to improve the efficiency of an automatic synthesis and optimization of the reversible logic, a semi-template technique and a fast algorithm was proposed. Template is an efficient optimizing tool, and the semi-template technique can significantly improve the matching efficiency in optimization. R-M synthesis arithmetic is a good iterative method in reversible logic synthesis. Based on the original idea of R-M arithmetic, by constructing an optimal and collision-free Hash function, a new fast algorithm for synthesizing the quantum reversible logic circuits was proposed. This algorithm can construct optimal quantum reversible logic circuits with various types of gates and quantum cost. The experimental results show that to the best of the knowledge in the same testing environment, the results are much better than others.

Abstract:The traveling salesman problem (TSP) is one of the classic NP-Hard combinatorial optimization problems. Efficient heuristics for the TSP have been the focus in research of computer science at all times. As a new tool to describe the structure of the TSP, the fat is essential for heuristic algorithm design. Since research on the fat is still at the beginning stage, It still lacks theoretical results and related heuristic algorithms. In this paper Firstly, the fat computational complexity for the TSP is investigated. It’s proved that it is NP-Hard to obtain the fat of the TSP through construction of biased instances, i.e., there is no algorithm to get the full fat of the TSP in polynomial time on the assumption P?NP. Furthermore, a meta-heuristic——dynamic candidate set search (DCSS) was proposed by analysis of the relationship between local optimal solutions and the fat. And the DCSS was applied to the LKH, one of the best existing algorithms for the TSP to improve it. Extensively wide experimental results on typical instances from the benchmark—TSPLIB indicate that the improved algorithm has a better performance than the LKH in terms of solution quality. This new fat-based heuristic shows a new way for other NP-hard problems.

Abstract:Incremental search reuses information from previous searches to find solutions to a series of similar search problems. It is potentially faster than solving each search problem from scratch. This is very important because many artificial intelligence systems have to adapt their plans continuously to changes in the world. If the changes are small, incremental search will be very efficient. BDD (binary decision diagram)-Based heuristic search combines the advantages of BDD-based search and heuristic search. Heuristic search impacts the size of the resulting search trees and BDDs can be used to efficiently describe the sets of states based on their binary encodings. This article first introduces BDD-based heuristic search and incremental search. Combining the two methods, it then gives a BDD-based incremental heuristic search algorithm BDDRPA*. The experimental results show that BDDRPA* is a very efficient incremental heuristic search algorithm. It can be used to solve many problems like symbolic replanning and robot navigation problems and so on.

Abstract:The performance of Chinese word segmentation has been greatly improved by character-based approaches in recent years. With the help of powerful machine learning strategies, the words extraction via combination of characters becomes the focus in Chinese word segmentation researches. In spite of the outstanding capability of discovering out-of-vocabulary words, the character-based approaches are not as good as word-based approaches in in-vocabulary words segmentation with some internal and external information of the words lost. In this paper we propose a joint decoding strategy that combines the character-based conditional random field model and word-based Bi-gram language model, for segmenting Chinese character sequences. The experimental results demonstrate the good performance of our approach, and prove that two sub models are well integrated as the joint model of character and word could more effectively enhance the performance of Chinese word segmentation systems than any of the single model, thus is fit for many applications in Chinese information processing.

Abstract:In data mining, lots of clustering algorithms have been developed, and most of them are limited by scalability and interpretability. To solve this problem, a concept-based data clustering model is presented. From the perspective of the metadata describing samples, some basic concepts are extracted from the preprocessed dataset firstly in this model, and then generalizes, higher level concepts representing clustering results. Finally, the samples are classified into different final concepts and the clustering process is completed. On the premise of ensuring the accuracy of the clustering results, this model can greatly decrease the number of tuples needing to be processed, improving the data scalability of clustering algorithms. In addition, to discover and analyze knowledge based on concepts, this model can improve the interpretability of clustering results, and facilitate to interact with users. Experimental results show that the proposed model is more useful to the algorithms with higher computation cost and better results.

Abstract:Evaluating the force of Internet news is an important aspect in the social security field. This paper establishes a quantitative analysis model for calculating the Internet news force with information retrieval methods based on the correlative information got through information retrieval technologies. This method can help people understand how great the news affects the social security. A lot of experiments, lead to a conclusion: this method can rank a stream of news effectively, and also can find most important news items from a number of news which belong to different types; its result is very close to people’s judgment.

Abstract:This paper describes objects by Riemannian manifolds and creates Voronoi diagrams based on charts. Difficulties in studying Voronoi diagrams for Riemannian manifolds are discussed. A theorem in existence is given, which demonstrates the present condition of Voronoi diagrams for Riemannian manifolds in a chart. According to the idea and theorem, this paper describes the algorithm of creating charts for two-dimensional Riemannian manifolds and presents the definitions of transition and blend functions. Finally, the algorithm of creating Voronoi diagrams based on charts is given, and some examples are provided.

Abstract:Anchor shot detection is a fundamental step for segmenting news video into stories. In this paper, a algorithm is developed for anchor shot detection based on face detection and SIFT. Face detection is first used to filter out the shots which do not have any face in the special area. Then, color histogram is used to judge whether two shots are similar, and the distinctive image features from scale-invariant key points are detected and matched to find groups of shots which may be anchor shots. Last, anchor shots are identified based on the same prior information of anchor shots. Compared with other algorithms, the significant advantage of the proposed algorithm is that the algorithm is based on neither the templates nor the learned classifiers. The method has been tested on many kinds of news video, which demonstrates its effectiveness.

Abstract:Recent progress on location aware services, GPS and wireless technologies has made it possible to real-timely track moving object and collect a large quarlity of trajectories data. As a result, how to effectively discover the knowledge from these trajectory data becomes an attractive and interesting research topic. The new trajectory outlier detection, proposed in this paper, can be used to determine whether two trajectories are globally matched by calculating the local matching degree between every base comparing unit pairs. Firstly, this paper proposes a new distance measure approach, which treats k consecutive points as a local comparing unit to depict the local features in terms of trajectories, via calculating the matching degree between trajectory segments. In addition, the critical concepts as local match, global match and trajectory outlier are presented. Secondly, based on this distance measure method, a new trajectory outlier detection algorithm based on R-tree is proposed to improve the efficiency of outlier detection. The main idea behind this algorithm is to eliminate unnecessary distance computation by R-tree and distance characteristic matrix between every trajectory pair. Extensive experiments demonstrate the efficiency and effectiveness of the proposed algorithm for trajectory outlier detection.

Abstract:Many challenges arise in subgraph query processing of graph-structured XML data. This paper studies the subgraph query processing of graph-structured XML data and proposes. A hash-based structural join algorithm, HGJoin to handle reachability queries on graph-structured XML data. Then, the algorithm is extended to process subgraph queries in form of bipartite graphs. Finally, based on these algorithms and cost model presented in this paper, a method to process subgraph queries in form of general DAGs is proposed. It is notable that all the algorithms above can be slightly modified to process subgraph queries in form of general graphs. Analysis and experiments show that all the algorithms have high performance.

Abstract:Many machine learning methods such as generative model and discriminative model have been applied to image semantic automatic image annotation. However, due to the “semantic gap”, the imbalanced training data, and the multi-label characteristic of image annotation, the annotation performance still calls for improvement. In this paper, an image annotation method is proposed which augments the classical generative model with the proposed discriminative hyperplane tree. Based on the high visual generative probability training images (neighborhood) of the unlabeled image, the local hyperplane classification tree is adaptively established. The semantic relevant training image set is obtained through top-down hierarchical classification procedure by exploiting the discriminative information at each level. The joint probability between the unlabeled image and the semantic words is estimated based on the obtained semantic relevant local training set under the proposed framework. This method combines the advantages of both generative model and the discriminative models. From the aspect of generative model: by exploiting the discriminative information of the semantic cluster in the discriminative hyperplane tree, a local generative set is progressively refined, and therefore, improves accuracy. From the aspect of discriminative model: the multiple label assignment can be naturally implement by estimating the joint probability, which reduces the limitation of discriminative model induced by the imbalanced and overlapping training set. The experiments on the ECCV2002 benchmark show that the method outperforms state-of-the-art generative model-based annotation method MBRM and discriminative model based ASVM-MIL with F1 measure improving by 14% and 13% respectively.

Abstract:An index structure ACEI (advanced CEI) is proposed in this paper to optimize the storage of CEI (containment-encoded intervals)-based interval index structure for data stream processing which involves a lot of operations of the numerical range query. It is necessary to construct a main memory-based query index with a low storage cost and little search time. The CEI index structure has low storage utilization, although it supports for high-speed query. To solve this problem, index structure ACEI is proposed. Based on CEI, through structural adjustment and optimization of parameters, ACEI can maintain the high speed of query operation and reduce the space complexity from O(R+N·W/L+N·log(L)) to O(sqrt(R·N)+ N·sqrt(W)). Experiments show that ACEI structure can greatly improve the storage utilization and can be used for interval index against a large endpoint range.

Abstract:In this paper, the concept of network distance prediction is firstly presented, and a brief discussion is made on different classification criteria. Then, based on the difference in prediction mechanisms, the existing research on distance prediction is classified into three types: the virtual coordinate based prediction mechanism, the network topology based prediction mechanism and the network proximity estimation mechanism. After a comparison between among the different prediction mechanisms, a comprehensive survey on network distance prediction is made, and the existing prediction mechanisms and their results are analyzed, Furthermore, the shortcomings and problems are outlined. In the end, the future trend of network distance prediction is discussed.

Abstract:Based on the broadcast nature of wireless signal, this paper proposes an approach that exploits the overhearing data omitted in conventional MAC protocols to eliminate the spatial correlation. Particularly, sensor nodes can prevent the transmission of redundant data in link layer by using the data they overhear to compress their own sensory data collaboratively before the transmission. Firstly, this paper formulates the problem that sensor nodes collaborate their compression to optimize their lifetime, and establish linear programming model for it. This paper also proposes a lower complexity (O(N²)) heuristic node selection algorithm while achieving a nearly optimal performance. Based on that, an efficient Collaborative ComPression-based MAC (CCP-MAC) protocol is designed to implement the above node selection algorithm in a distributed way. As a result, the corresponding node can receive the data it overhears from the selected sensor node subset to compress redundant data before the transmission. Experimental results show that by exploiting the data nodes overhear CCP-MAC can collaborate the nodes to compress sensory data, thereby conserve energy significantly to prolong the network lifetime.

Abstract:To satisfy various requirements restricted delegation of in grid applications, a hierarchical role-based delegation authorization execution model for service grid is proposed. The dynamic characteristic of delegation role granting or revocation and the associated constraint of delegation role granting are effectively supported. The fine-grained associated role dependency is implemented by adding trustworthiness. Partial delegation problem is easily solved by defining the role tree as the basic unit of delegation authorization and by pruning the role tree. The delegation spread tree with trustworthiness is defined to implement multi-step delegation in a fine-grained manner. The delegation certification is proposed to fully express temporary delegation, associated role delegation, partial delegation, multi-step delegation. Based on above works, a set of formal delegation authorization execution rules is proposed and proved, and the delegation authorization execution process is effectively controlled. The exhibited example shows that the model can satisty various requirements of restricted delegation in grid applications.

Abstract:In order to enhance service availability and improve system performance, it is necessary to configure multiple HAs on the home link and efficiently balance load among these HAs. This paper proposes the Home Agent Load balancing method based on Active Overload Prevention (HALAOP). HALAOP actively selects optimal HA for each registration request to prevent HA’s overload in advance, rather than just passively switching load between HAs like previous methods. HALAOP introduces a dynamic load evaluate algorithm to provide the basis for optimal load balancing decision. In addition, the load slicing mechanism is introduced to eliminate unnecessary additional overhead. The results of numeric analysis show that HALAOP can be more efficient in reducing probability of registration failure due to HA’s overload and registration delay at lower additional cost than previous methods.

Abstract:Dynamic changes in service environment will affect fault diagnosis algorithm. In order to reduce the impact, challenges of fault diagnosis in dynamic environment are analyzed in this paper. Multi-layer management model is presented to model the service system, Bipartite Bayesian network is chosen to model the dependency relationship and binary symmetric channel is chosen to model noises. To deal with the dynamic fault set caused by fault recovery mechanism, prior fault probability is modified based on fault persistent time statistic; To deal with the dynamic model, expected model is built based on the time of observing symptoms and original models in current window. Simulation results show that this fault diagnosis algorithm is efficient in dynamic Internet service environment.

Abstract:The security of wireless sensor networks has attracted much attention in recent years and the key management is the focus. EBS-based dynamic key management scheme is a new approach for wireless sensornetworks. Its major advantages are its enhanced network survivability, high dynamic performance and better support for network expansion. But it suffers from the collusion problem, which means it is prone to the cooperative attack of the compromised nodes. In this paper, the feature of the collusion problem is analyzed and an optimization model is proposed, maximizing the length of the shortest collusion chain, which is the key issue of the problem. A discrete particle swarm optimization algorithm for the collusion problem is also presented based on the optimization model proposed. Simulation results show that compared with the former works, the resilience of the network and the difficulty to compromise the whole network are both greatly improved.

Abstract:In this paper, existing lifetime-aware routing algorithms are divided into two categories: General Max-Min (GMM) algorithm and Conditional Max-Min (CMM) algorithm. Motivated by algorithmic mechanism design, two truthful mechanisms for these two types of algorithms are proposed: SMM for GMM algorithm and SMM-VCG for CMM algorithm. By giving appropriate payments to the relay nodes, the proposed mechanisms gurantee that existing algorithms achieve their design objectives even in the presence of selfish nodes. It is shown that the payment ratio is relatively small and stable due to the nature of lifetime-aware routing algorithms, which is also confirmed by experiments.

Abstract:This paper studies the traditional client puzzle scheme and proposes an adaptive scheme which erforms a lightweight client-server interaction to flexibly adjust the puzzle difficulty according to the eal-time statuses of both client and server. To evaluate the applicability, the authors combine the two schemes and develop an adaptive DoS-resistant security framework for Peer-to-Peer networks. The theoretical analyses and experimental results show that the adaptive client puzzle scheme can ffectively defend against various DoS attacks without significantly influencing legitimate clients’ experiences even in a highly malicious environment.

Abstract:In this paper, new attacks against trust recommendation are identified and relationships between these attacks are analyzed. Then a trust model is presented with recommendation trust revision support based on Bayesian Decision-Making theory and the minimum- loss principle. The proposed trust model with recommendation trust revision (TMRTR) is employed in ad hoc networks for optimizing ad hoc routing. Simulation results in MATLAB environment show the method proposed is helpful to reduce the impact of some new threats to trust management and improves the effect of trust management. Synchronously, the proposed system can effectively detect malicious nodes in ad hoc networks.

Abstract:An improved impossible differential attack on the block cipher CLEFIA is presented. CLEFIA was proposed by Sony Corporation at FSE 2007. Combining some observations with new tricks, the wrong keys are filtered out more efficiently, and the original impossible differential attack on 11-round CLEFIA-192/256 published by the designers, is extended to CLEFIA-128/192/256, with about 2^103.1 encryptions and 2^103.1 chosen plaintexts. By putting more constraint conditions on plaintext pairs, we present an attack on 12-round CLEFIA for all three key lengths with 2^119.1 encryptions and 2^119.1 chosen plaintexts. Moreover, a birthday sieve method is introduced to decrease the complexity of the precomputation. And an error about the time complexity evaluation in Tsunoo et al.’s attack on 12-round CLEFIA is pointed out and corrected.

Abstract:This paper presents a head detection and trifocal tensor pointer transfer based multi-camera collaboration. In this approach, people’s head position is detected after background subtraction and tracked by Kalman and PDA. Trifocal tensor transfer is used to locate objects in the virtual top view by the corresponding head points in two camera views. Compared with existing approach, the approach doesn’t need camera calibration and coplanar precondition, nor does the deterioration of epipolar transfer exist. The experimental comparison between this approach and other traditional ones proves its effectiveness and accuracy.

Abstract:Locally linear embedding greatly depends on whether the neighborhood graph can realistically reflect the underlying geometry structure of the data manifolds. The topological structure of constructed neighborhood with the existing approaches is unstable. It is sensitive to the noisy and sparse data sets. Based on the relative cognitive law, the relative transformation is presented, by which the relative space and the relative manifold are further constructed. The relative transformation can improve the distinguishing ability between data points and reduce the impact of noise and sparsity of data. To determine the neighborhood in the relative space and the relative manifold can more truly reflect the manifold structure, based on which the enhanced local linear embedding algorithms are developed with significantly improved performance. Besides, the speed is also enhanced with this approach. The experiments on challenging benchmark data sets validate the proposed approach.

Abstract:A triangle mesh compression algorithm based on reverse subdivision is introduced. By improving reverse Butterfly simplification algorithm, a mesh simplification algorithm based on reverse Modified Loop scheme is proposed. The dense triangle mesh is decomposed into progressive meshes which consist of a base mesh and a series of displacement wavelets. The progressive meshes are compressed with embedded zerotree coding by constructing displacement wavelets tree structure. The experiments show that the proposed approach is faster and more efficient than previous related techniques. The proposed algorithm can be used for progressive transmission over wireless networks and 3D graphics real-time rendering on mobile terminals.