Abstract:With the rapid development and wide application of the Internet technology, many problems of Artificial Intelligence, for example scheduling, planning, resource allocation etc., are formally distributed now, which turn into a kind of multi-agent system problems. Accordingly, the standard constraint satisfaction problems turn into distributed constraint satisfaction problems, which become the general architecture for resolving multi-agent system. This paper first briefly introduces the basic concepts of distributed CSPs, and then summarizes the basic and the improved algorithms. Their efficiency and performance are analyzed and the typical applications of distributed CSPs in recent years are discussed. Finally, this paper presents the extensions of the basic formalization and the research trends in this area. Recent related work indicates that the future work will focus on the theoretical research to present the solid theoretical foundation for the practical problems.

Abstract:Heterogeneous distributed real-time simulation system is a special kind of real-time system. This paper solves its fault-tolerant problem based on the CSP (checkpoint-based spare processor) model, which is an improvement of the traditional SP (spare processor) model with checkpoint mechanism. Firstly, two propositions are put forward based on the characters of simulation system. Secondly, the Worst Case Response Time of the simulation tasks are analyzed based on Markov chains and the schedulability analysis rules for simulation task are presented. In the end of the paper, a fault-tolerant scheduling algorithm CSP-RTFT is proposed and simulated. The results show that the algorithm can achieve better stability, higher task accept ratio than SP-RTFT which is based on SP model, whereas the resource utilization ratio is lower than those based on PB model.

Abstract:Multidimensional time sequences are an important kind of data stored in the information system. Similarity search is the core of their applications. Usually, these sequences are viewed as curves in multi-space, and the Euclidean Distance is computed to measure similarity between these curves. Although Euclidean Distance can reflect the whole deviation between two sequences or subsequences, it ignores their inherent changing features. To remedy it, this paper presents a new algorithm. In this algorithm, the shape features of sequences or subsequences are subtly combined with spatial index structure (k-d tree), which makes it possible to match shape of sequences or subsequences without any extra cost whiling searching the tree. The experimental result demonstrates that the algorithm is effective and efficient.

Abstract:Smoothed complexity of algorithm can explain the practical performance of algorithm more efficiently. Condition number of matrix is a main root to result in large error in solution during the running of Gaussian algorithm. Sankar, et al. performed a smoothed analysis of condition number of symmetric matrix under zero-preserving perturbations. However, the smoothed complexity presented by Sankar, et al. was higher and more complicated. To solve this problem, two key inequalities are presented. The inequalities are used to improving the smoothed complexity of condition number of symmetric matrix. The smoothed analysis of bits of precision needed by using Gaussian algorithm is performed and lower smoothed complexity is presented.

Abstract:This paper considers the problem of scheduling n jobs on m parallel unbounded batch machines to minimize the total weighted completion time. Each job is characterized by a positive weight, a release time and a processing time. Each unbounded batch machine can process up to B (B≥n) jobs as a batch simultaneo usly. The processing time of a batch is the longest processing time among jobs in the batch. Jobs processed in the same batch have the same completion time, I.e., their common starting time plus the processing time of the batch. A polynomial time approximation scheme (PTAS) for this problem is presented.

Abstract:This paper considers the problem of scheduling n jobs on m parallel unbounded batch machines to minimize the total weighted completion time. Each job is characterized by a positive weight, a release time and a processing time. Each unbounded batch machine can process up to B (B≥n) jobs as a batch simultaneously. The processing time of a batch is the longest processing time among jobs in the batch. Jobs processed in the same batch have the same completion time, i.e., their common starting time plus the processing time of the batch. A polynomial time approximation scheme (PTAS) for this problem is presented.

Abstract:The availability of a P2P (peer-to-peer) file sharing system is heavily affected by the high churn rate of users. When the largest P2P file sharing system Maze in CERNET is developed, the log collected in the system is used to get a better understanding of the users’ characteristics, to find the key factor which influences the resource availability, and to instruct the future development of Maze system. In this paper, the concept of P2P file sharing systems’ availability is redefined from users’ perspective. With the log of Maze, it is the first study to use clustering technique to quantitatively categorize users in a P2P file sharing system. Based on the thorough study of behavior of the active users amounting to 0.77% of the total users and the impact on Maze’s availability, this paper concludes that this kind of users plays a similar role to server so that they greatly increase the availability of system and are feasible resource to improve the performance of P2P file sharing systems.

Abstract:Most Web bibliographies cannot meet the retrieval requirements of the researchers with different academic levels. The reason resulting in the problem is analyzed, and the idea of constructing an auxiliary Web bibliography retrieval structure for the users to obtain more proper bibliographies is proposed. Based on the idea, an algorithm of mining the longest sequential frequent phrases for extracting features of the bibliographies is designed, and an extended feature hierarchical tree describing the relationship among the features, among the bibliographies, and among the features, the bibliographies and its construction is presented. The experiments show that the new method outperforms the current popular TFIDF method in extraction features. The theoretical analysis explains that the extended feature hierarchical tree has constringent structure, reveals the relationship between phrases and bibliographies, and provides better assistant retrievals.

Abstract:Semantic routing is one of key parts in P2P routing researches. The intelligent search mechanisms support flexible semantic expression but hold low scalability and recall rate. Contrastively, semantic overlay network is scalable but either is difficult to organize or take too large maintenance spending. This paper proposes a new P2P semantic routing model in which node array is organized by match path and probability balance tree, and then an approximately balance distributed structure is obtained. All nodes will take routing decision according to query content while limiting maintenance spending to relative low level. The model supports flexible semantic search and high scalability, and ensures that each node can reach any corner of the network. The model runs with no center service in which all nodes simultaneously take index storage and data storage, and forward task to share system’s running load by only maintaining a little local information.

Abstract:With the abroad application of instant messaging and explosive growth of users in current years, IM worms have higher outbreak frequency, wider coverage and deeper hurt, which have been a serious threat to network security. In this paper, the concept and research situation of IM (instant messaging)worms, function component, execution mechanism and comparison with other worms are presented, then the network topology and propagation models are discussed, and finally the critical techniques of IM worm prevention are given. Some major problems and research trends in this area are also addressed.

Abstract:With the progress of peer-to-peer (P2P) technology, the Internet applications model is in a great reformation. In order to get an all-win solution among the Internet users, Internet service providers and content providers, it is necessary to measure and analyze the P2P applications from their perspectives. In this paper, the content of P2P measurement is introduced firstly, and then the existing research on P2P measurement is classified into 3 areas: topology measurement, traffic measurement and availability measurement. After comparing between measurement methods, the comprehensive survey on P2P measurement is given, and then the existing measurements and their results are analyzed in depth, furthermore, the shortcomings and problems are outlined. In the end, the future trend of the P2P measurement is discussed.

Abstract:The measurements based on flow characteristics have been playing more and more important roles in the analysis of Network Behavior. As a main method of flow recognition, the timeout strategies have a very important impact on the correctness and performance of flow measurement. This paper firstly discusses the state-of-art of flow timeout strategies, and points out where they are applicable and their shortcomings. To deal with the short flows that take a large part of the total flows in the networks, the paper presentes a Dynamical Timeout Strategy (DToS) based on the analysis of flows’ length distribution and flows’ rate metrics in detail. This method could improve the performances of network measurement and the efficiency of the resource usage in measurement systems by using different timeout strategies dealing with flows that have different rate features based on analyzing the usage of target network. It could also apperceive network abnormal behavior efficiently, and trigger emergent methods to ensure the safety of measurement system. After that the feasibility and robustness of this method are analyzed. At last, some experiments are employed to show the rationality of DToS strategy. The fitness area of strategy is also anatomized in the paper.

Abstract:Many overlay multicast systems proposed in recent years focus on designing an optimized tree for a single data source. They cannot be extended to any-source multicasting because one tree per source is too costly. The existing P2P (peer-to-peer) systems that allow many data sources have high maintenance overhead and lack the flexibility in supporting host diversity. This paper proposes an any-source capacity-constrained overlay multicast service based on a non-DHT (distributed hash table) overlay network specifically suitable for the purpose of multicast. The nodes have different capacities in supporting different numbers of direct children during a multicast session. No explicit multicast trees are maintained on top of the overlay. This paper presents two distributed multicast algorithms that are able to deliver a multicast message from any source to all nodes in the expected O(log_cn) hops, which is asymptotically optimal, where c is the average node capacity and n is the number of members in a multicast group.

Abstract:Active interest management manages interest with active routing method. It combines communication and interest management together to decide communication relationship between objects in distributed virtual environment (DVE). On analysis of active interest management, layered interest management and some other related technologies, concept of level of interest (LOI) and an evaluating model of LOI between objects in DVE are put forward in active leveled interest management. LOI is used to control the detail of communication to reduce traffic load. Therefore, the system’s scalability can be improved furthermore.

Abstract:This paper proposes an algorithm for globally approximating real algebraic plane curves of degree k with B-spline curves of the same degree. Each connected component is approximated with a B-spline curve. It is suitable for all irreducible real plane algebraic curves with arbitrary genus (including singular curves). This method is based on our blowup sampling method of algebraic curves, which solves the difficult problem of sampling around singular points in essence. The experimental results show that the algorithm achieves better accuracy than the existed methods.

Abstract:Captured motion data is widely used in virtual human motion control and synthesis. Usually, the motion data has a native skeleton definition. To apply captured motion on virtual human skin model, the model should have an underlying skeleton that matches the one defined by the motion data. This paper proposes an algorithm called LMSA (lazy match based on semantic analysis) which generates skeleton for existing human model and matches it to the motion data when the motion data is loaded. The LMSA algorithm first generates Candidate-Joint-Set for a human model with a group of parallel planes and then applies the same semantic analysis to both the Candidate-Joint-Set and the skeleton of motion data to match them. By using LMSA algorithm, different motion data can be applied to the existing human model directly without predefining skeleton for human model.

Abstract:This paper presents a novel approach for the progressive transmission of highly detailed surfaces interactively. Based on the characteristics in human vision, 3D surfaces are converted into the hierarchical quadtree in parameter space and a normal texture atlas. By taking advantage of normal mapping, only the silhouette to current viewpoint is refined and transmitted, and consequently the amount of patches needed to transfer each frame is greatly reduced. The structure of the representation is simple, so efficient compression scheme can be applied to encoding the hierarchical topological structure. At the same time, the parametric patches can be transmitted in arbitrary order due to their regular connectivity, so the truly view-dependent transmission could be achieved in high efficiency. Experiment results show that the approach proposed is feasible and highly efficient in meeting the requirement, especially to those models with highly detailed surfaces.

Abstract:It is very important to efficiently select visible surfaces in rendering complex scenes. As for this, a method is presented in this paper by combining the strategies for image-based selection and object-based selection. First, it classifies the surfaces by their normals, and manages every class of surfaces in hierarchical indexing structures by their positions in 3D space. Then, the visible surfaces are pixel-driven searched from near to far. As the index structures can manage the surfaces orderly, this search can be calculated quickly and all visible surfaces can be obtained. Meanwhile, the selected visible surfaces can be fused automatically to act as the occluders to implicitly cull the occluded surfaces in large quantities. Compared with existing methods for selecting visible surfaces, the new method is fast and in high precision, and can conveniently handle the scenes with dynamic objects.

Abstract:For arbitrary triangular control meshes, a surface algorithm based-on bivariate box-spline is developed.Bivariate 3-direction is a triangulation with the least directions. Box spline built on it is widely applied in CAGD.Its standard surface algorithm is only for normal control mesh in which every point has valence 6. Starting with bivariate 3-directional quartic box-splines, the paper proposes an algorithm for arbitrary triangular control meshes.The analysis of its properties especially continuity are presented in detail. The constructed surfaces by the algorithm are convex preserving, and they are piecewise C¹. The algorithm can be easily applied for global or local interpolation, which is indispensable in 3D surface reconstruction from scattered points.