Abstract:The uncertainty of running time of randomized algorithms provides a better opportunity for asynchronized parallelization. There are many computing experiments verifying that the asynchronized parallelizating acceleration of randomized algorithms are linear or even superlinear. For randomized algorithm RDP solving for SAT (satisfiability) problem, the relation among efficiency of asynchronized parallelization, distribution of running time and number of processors are investigated. In this paper, a model of piecewise-linear distribution is applied to simulate the running time distribution of randomized algorithms. This model of distribution is a kind of single peak. Both theoretical analysis and computing experiment indicates that asynchronied parallelization of randomized algorithms are of near linear acceleration when the processors are less and the single peak is located near the front of running time distributions.

Abstract:As a challenging problem of the upcoming next-generation networks, multi-constrained quality-of- service routing (QoSR) is to find a feasible path that satisfies the multiple constraints simultaneously. For the NP complete problem, the heuristic SA_MCP by applying the simulated annealing to Dijkstra’s algorithm is proposed. SA_MCP first uses a non-linear energy function to convert multiple QoS weights to a single metric and then seeks to find a feasible path by simulated annealing. This paper overviews the simulated annealing method and analyzes the issues when it is applied to QoSR. Extensive simulations show the following conclusions: (1) SA_MCP has a high performance w.r.t. routing success ratio. (2) It has a good scalability in both network scale and weight number k. (3) It is insensitive to the distribution of QoS constraints. Furthermore, when most QoS requests are feasible, the running time of SA_MCP is about O(k(m+nlogn)), which is k times that of the traditional Dijkstra’s algorithm.

Abstract:The minimum cut problem between two distinguished nodes in a undirected planar network with limited capacities on both nodes and edges is discussed. The traditional method reduces the node-edge-capacity problem to an only-edge-capacity problem. But this method does not maintain the planarity of a planar network, so the special qualities of planar networks can not be used. The traditional algorithm runs in time O(n²logn). In this paper, approaches that fully use the planarity of planar networks are presented. For an s-t network in which the source and the sink are on a same face, the minimum cut problem to the shortest path problem in a planar graph is reduced, thus an algorithm that runs in time O(n) is obtained. For a common planar network, another method that reduces the node-edge-capacity problem to an only-edge-capacity problem is presented. This reduction method does not destroy the planarity of a planar network, so that the problem can be solved in time O(nlogn).

Abstract:A new parallel algorithm for the knapsack problem is proposed, in which the method of divide and conquer is adopted. Based on an CREW-SIMD machine with shared memory, the proposed algorithm needs O(2^n/4)^1-ε processors, 0≤ε≤1, and Oi>O(2^n/2) memory to find a solution for the n-element knapsack problem in O(2^n/4(2^n/4)^ε) time. The cost of the algorithm is O(2^n/2), which is optimal and an improved result over the past researches. The wrong results in corresponding literatures are also pointed out in this paper.

Abstract:ω-path partition problem is the generalization of path partition problem. It comes of broadcasting communication in parallel computer system, computer network and distributed control system. This problem can be described by graph theory terminology as follows. Let G=(V,E) be an undirected simple graph with nonnegative edge-weights, and ω≥0 be a real. {P₁, P₂, …, P_m} is called to be an ω-path partition of G if P₁, P₂, …, P_m are m pairwise vertex-disjoint paths of G such that , and V(P)()(1GVPVmii==Ui)≤ω (for all i=1, 2, …, m, where W(P_i)= ). The ω-path partition number of G is the smallest cardinality of ω-path partition of G. The ω-path partition problem of G is to find a minimum ω-path partition and the ω-path partition number of G. It is evident that ω-path partition problem for any graph is NP-complete by the NP-completeness of Hamiltonian path. In this paper, some properties of ω-path partition have been investigated for paths, trees and forests with nonnegative edge-weights respectively. Linear time algorithms have been presented to solve ω-path partition problem for any path and tree with nonnegative edge-weights respectively. Local realization techniques and complexities of these two algorithms have been discussed in detail. Based above algorithms, an O(n) algorithm has been designed to solve ω-path partition problems for forests with nonnegative edge-weights. The algorithms presented in this paper are concise, and require less time and space.

Abstract:Many organizations nowadays operate local area networks connecting hundreds of workstations and personal computers and use them as a cluster system. Dynamic load balancing is an important method to improve the performance on such heterogeneous system. Diffusion algorithm is a dynamic load balancing method for homogeneous system. In this paper, the diffusion algorithm is extended to heterogeneous system, the influence of the arrangement of different processors in the system on the convergence rate of the diffusion algorithm is studied, and an optimal method is proposed to improve the convergence rate. Primary result shows that it can find the better arrangement of the processors to accelerate the diffusion algorithm.

Abstract:In this paper, an approach to the revision of a finite belief set is presented. First, a procedure for generating all the minimal inconsistent sets is introduced, and the correctness of the procedure is proved. Then what discussed further is that how to apply the procedure to the implementation of some representative methods, and a implemented prototype for belief revision is introduced. At last, the presented approach is compared with other related work.

Abstract:At present sequential minimal optimization (SMO) algorithm is a quite efficient method for training large-scale support vector machines (SVM). However, the feasible direction strategy for selecting working sets may degrade the performance of the kernel cache maintained in SMO. After an interpretation of SMO as the feasible direction method in the traditional optimization theory, a novel strategy for selecting working sets applied in SMO is presented. Based on the original feasible direction selection strategy, the new method takes both reduction of the object function and computational cost related to the selected working set into consideration in order to improve the efficiency of the kernel cache. It is shown in the experiments on the well-known data sets that computation of the kernel function and training time is reduced greatly, especially for the problems with many samples, support vectors and non-bound support vectors.

Abstract:Skeleton is an important representation of objects. In this paper, an approach of extracting the skeleton based on the regions labeled from a gray image is developed. It specifies the complementary definitions of the ridge points, utilizes both contour and region information of an object, and uses hierarchical processing strategy. The multi-scale skeleton of an object can be robustly extracted, which is suitable for both regular and irregular objects. It is connected and single-pixel wide, and keeps the topological properties of the original object image. This approach is applied to real images, and the skeletons detected are consistent with visual apperception.

Abstract:In this paper, the convergent conditions in sequence or parallel update mode and the sufficient condition with only one global stable state for Hopfield network model with discrete time and continuous states when its neurons’ activation function is non-decreasing (not being strictly monotone increasing) are discussed. With the definition of a new energy function and the research on the properties of monotonously increasing function, the sufficient conditions is presented to converge in parallel or sequential update mode when neuron’s activation function is monotonously increasing (not be necessary to strictly increase). After obtained the condition for energy function to be convex with respect to the network states variables, it follows that a sufficient condition for network to have only one stable point with the minimum energy by regarding the operation of Hopfield network as solving a constrained convex optimal problem. When auto-connection weight value of each neuron in network is greater than the reciprocal of derivation of its activation function, the network will be convergent in sequence update mode. When the minimal eigenvalue of connection weights matrix is greater than the reciprocal of derivation of its neuron activation function, the network will be convergent in parallel update mode. If the energy function of network is convex, the network will have only one global stable point. These results extend the choice range of activation function of neuron when using Hopfield net to solution of optimization problem or to associative memory.

Abstract:The homography induced by the plane at infinity between two images, namely the infinite homography, plays a very important role in 3D computer vision since many vision problems could be substantially simplified by knowing it. Unlike homographies induced by ordinary planes which can usually be determined by correspondences of image points, the infinite homography must be determined indirectly since no real physical points lie on the plane at infinity. In this paper, how to determine the infinite homography through scene parallel planes is studied, and the following two conclusions are proved: (1) If only a pair of parallel planes is present in the scene, the infinite homography can be obtained by solving a 4th order polynomial, and at maximum, four possible solutions exist. (2) If at least two pairs of parallel planes exist in the scene, and if planes in different pairs are not parallel, then the infinite homograpgy can be linearly and uniquely determined. In addition, a geometric interpretation to the above results, and some practical algorithms are also provided. The proposed results in the paper are of interests in camera self-calibration and image based 3D reconstruction under both theoretical and practical standpoints.

Abstract:The Join algorithms of massive relations in relational databases based on tertiary storage are studied in this paper. At present, Hash-Based Join algorithms are the best ones. However, the effect of tape locate time is not taken into consideration in these algorithms. It has great influence on the time complexity of the Join algorithms to locate positions on tertiary storages. For this reason, two new Join algorithms of massive relations in relational databases are proposed based on tertiary storage, Disk-Based-Hash-Join algorithm and Tertiary-Only-Hash-Join algorithm. Adopting disk buffer technique and the method of storing hashed data concentratedly, the cost of the random position locating on tertiary storage is much lower than other algorithms so that the proposed Join algorithms are more efficient. The analysis and experimental results show that the performance of this algorithms is superior to others, and thus they are suitable for massive database management.

Abstract:Security policy model is the groundwork for secure or trusted system. Bell-LaPadula model with its good adaptability has comprehensive applications to multilevel security system, but it is short of the rules about integrity and consistency. Based on that model, an extended policy model is proposed, which is founded on the extended object hierarchy. By this way, the integrity becomes one of the inherence properties of the model. The object domains, extended security axioms and operation rules are also introduced or redefined. The proposed model more suits the requirements of multilevel security databases, and guarantees the consistency among policy model, system specification and other high-level security model. The extensions and enhancements, especially other properties besides security, are the necessary steps for transforming a policy model into a practical system.

Abstract:How to effectively organize and store the profile of moving objects in a mobile environment, which can effectively lower the paging and update cost, is an important problem in location management. Combining data mining into a mobile environment is a challenging research task, which has broad prospective applications. In this paper, a solution is provided to optimize the placement of location databases from the aspect of data mining. First a new hierarchical clustering algorithm is presented to cluster the moving log, then use the clustering results to dynamically reunite location databases, thus the paging and update cost can be lowered effectively.

Abstract:Previous work on pattern discovery in sequence data mainly considers finding global patterns, whereevery record in the temporal sequence contributes to support the patterns. However, local patterns, which arefrequent only in some time periods, are actually very common in practice and the efficient discovery of it ispotentially very useful. This paper presents a method for discovering generalized local sequential patterns with thestructure that supports efficiently locating and counting of the pattern instances and a two-phase method forefficiently mining of local patterns. Experimental results corresponded with the problem definition and verified thesuperiority of the approach.

Abstract:Structured documents are made up of a few logical components, such as title, sections, subsections andparagraphs. The components in each structured document can be represented by an ordered tree model, which canalso be viewed as a hierarchical concept relationship. To meet the user's requirements for more precise andconcentrated search results, the retrieval techniques should allow the user to retrieve document components withvarying granularity. This paper presents a method to query document database by content and structure. The keyidea is to construct a more comprehensive similarity function by taking advantage of the inherent hierarchicalstructure in documents. This work combines Information Retrieval techniques, semi-structured data query andproximate search for document documents. The proposed method is evaluated on the Encarta encyclopediadocument set and the experimental results show that it can provide more accurate and focused answers thantraditional document retrieval methods.

Abstract:Message delivery protocols are among the most important mechanisms in a mobile Agent system since cooperating mobile Agents need to communicate with each other. In this paper, a generic framework is presented for designing mobile Agent message delivery protocols. The framework uses a flexible and adaptive mailbox-based scheme, which associates each mobile Agent with a mailbox while allowing the decoupling between them, i.e., a mobile Agent can migrate to a new site without bringing its mailbox. By separating the concerns of locating the mailbox of a mobile Agent and delivering a message to the Agent, a large space of protocol design with flexibility is obtained. Using a three-dimensional model based on the scheme, the generic framework not only covers, as particular cases, several known protocols, but also allows for the design of new ones suited for various application requirements. By extensive simulation experiments, trade-offs between design parameter selection and their impact on the performance of derived protocol are analyzed. The conclusion of analysis can be used to guide applications of the framework.

Abstract:Two approaches are presented to stream cipher utilizing a peculiar dynamical system called as composite discrete chaotic dynamical system (for short, composite system), which consists of two chaotic dynamical systems. The secret keys are the initial state of the chaotic dynamical systems, and the plaintext is used as its composite sequence that decides the choice of iterating function in the iterating process. Because of sensitivity of the composite system to initial conditions and randomness in the iterating process, the approach mingles secret keys with plaintext when using the composite system to produce ciphertext. Therefore they hold very complex and sensitive nonlinear relations. The algorithm is also provided with uniform distributing ciphertext. These peculiarities prevent ciphertext to leak the information of plaintext and secret key and make the security of the algorithms not depend on the complexity of the ciphertext.

Abstract:Traditional information retrieval technologies satisfy users’ need to a great extent. However, for their all-purpose characteristics, they can not satisfy any query from the different background, with the different intention and at the different time. A personalized search algorithm by using content-based filtering is presented in this paper. The user model is represented as the probability distribution over the domain classification model. A method of computing similarity and a method of revising user model are provided. Compared with the vector space model, the probability model is more effective on describing a user’s interests.

Abstract:Probabilistic packet marking (PPM) is a practical and effective method for IP traceback ofdenial-of-service (DOS) attack. In this paper, an adaptive PPM algorithm is presented: a router marks a passingpacket with a probability which is adaptive to the distance that the packet has traversed, so that a minimumconvergence time for an attacking path can be achieved in the victim. With a new IP header overloading scheme, thelabeled fragment encoding scheme, a real-time reconstruction is provided, so that thousands of paths can be tracedsimultaneously. Compared with previous PPM schemes, a 50% decrease in convergence time is achieved, while thecomputation overhead and false positives in re construction are greatly reduced.

Abstract:Most high-speed IP routers exploit cell-based switching fabrics, whose scalability and performance are mainly affected by queuing scheme and scheduling algorithm. Input-queued router is referred to as an ideal structure in terms of scalability. However, it needs an efficient scheduling algorithm to guarantee throughput and delay. Several input-queued scheduling algorithms are surveyed in this paper. The scheduling algorithms are classified into four classes: maximum size matching, maximum weight matching, stable marriage matching, and deterministic scheduling algorithm. The similarities and the difference of different algorithms in mechanisms of each class are described, and their performances are compared. Finally, the future directions and possible open problems are discussed.

Abstract:IP routing architecture and algorithms of Internet is a sort of key technology. But in the practical application, the actual routing architecture and algorithms have still some problems. The purpose of this paper is to provide a sort of IP routing architecture and algorithms based on end_users control to resolve this problem. In this architecture, routing decision will be done mostly by end_users, but the task of router would be predigested to two simple functions, notify network information and assort with users decision .This paper will achieve above object through users self-organizing behaving. This architecture can adapt the extended requirement of network size and application need, and form a sort of distributed, scalable routing architecture and effective routing algorithm.