Abstract:A new method for shape modification of NURBS surfaces is proposed in this paper. Explicit formulae for computing new control points are derived by using constrained opimization method. Examples are also given to compare the results of Piegl's method with those of the new method.

Abstract:Branch-and-Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. In this paper, the lower bound of running time Ω(m/p+hlogp)(the base of all logarithms in this paper is 2) is presented for general parallel best-first B&B algorithms on shared memory systems, where p is the number of processors available, h is the number of expanded nodes, and m is the total number of active nodes in state-space tree. In addition, a new general parallel best-first B&B algorithm on PRAM-EREW is proposed by devising the shared memory into p cubeheaps. Theoretical analysis shows that it is the fastest algorithm for h<p^2p, and it is asymptotically optimal in this type of general parallel B&B algorithms. Computational experiments are conducted to solve 0-r knapsack problem.

Abstract:Financial data mining is one of the most challenging research directions in information society. Financial data with random characteristics make it difficult to find out the rule hidden in data. In this paper, it is pointed out that correlation coefficient can not capture nonlinear information, which is the serious defect of classic correlation analysis. Furthermore, the properties of the high-order correlation coefficient are discussed, and it is proved that high-order correlation can not only describe the hidden nonlinear correlation, but also fill up the space between classic correlation and independence. The computational simplicity makes the high-order correlation coefficient be an effective technique to track nonlinear relation between variables. Finally, the above results are applied to the correlative analysis between stock price and stock trading volume, and the computing results show that the high-order correlation coefficient can track the time-varying nonlinear characteristics.

Abstract:Randomized algorithms are playing a more and more important role in computation because of their simplicity and fastness. But sometimes the good performance of randomized algorithms does not require completely independent random variables as their input. In this paper, a new random algorithm is introduced for the classical problem of estimating the cardinality of a union of sets, which only needs pair-wise independent random input. This approach helps to reduce the random bits used in the algorithm. For fixed accuracy parameter ε and confidence parameter δ, the algorithm needs O(t^1/2) random bits, much fewer than those of a standard randomized algorithm O(tlogtM). And the running time bounds of the algorithm do not increase essentially O(t²logM), where t is the number of sets and M is the maximal cardinality of an individual set).

Abstract:In this paper, a Version-control Set Refreshing Algorithm (VSRA) is proposed, which uses incremental maintenance, version-control and batch processing mechanism to guarantee on-line maintenance and data consistency. VSRA not only reduces communication between database and data warehouse, but also promotes the refreshing efficiency of materialized views. Users can perform on-line analytical process at any time and get correct results with VSRA.

Abstract:In this paper, a review is presented on the SR (spatial reasoning) and the GIS (geographic information system). The use and the general development situation of the SR and the GIS are introduced. By analyzing large amount information, the key attributes, the major directions of research and the hotspot of research of the SR and the GIS are given.

Abstract:Multiple LOD modeling is an effective approach to speed up the rendering of 3D scenes. An algorithm that creates multiple levels of detail for 3D scene by merging near-coplanar faces is presented in this paper. First a Gauss sphere is defined for the modeling of the scene, which is divided into patches uniformly. Faces of objects in the scene are then attached to the respective spherical patches according to their normal direction. If faces attached to the same patch are adjacent to each other, they are merged to form a near coplanar area (superface). Isolated vertices inside the area are removed and the area is retriangularized. To further improve the simplification, vicinity vertices on the border of the area are merged. The algorithm adopts a planar separation rule to support the hierarchical model. The experimental result shows that the algorithm can achieve the desired simplification effect.

Abstract:A new method is presented in this paper to decide whether a point is in a polygon or a polyhedron. By taking a preprocessing to organize facets of polyhedrons and edges of polygons in to layers, it employs the binary searching algorithm to perform tests instead of handling all facets and edges. Experimental results show that it is simple, robust, and easy to use.

Abstract:Media mapping in video-on-demand server networks is a new combinatorial optimization problem. The network of video servers can be implemented on the top of a closely connected network of workstations or on a wide area network of servers. This paper addresses the media mapping problem, taking the user access patterns, overall storage capacity and communication bandwidth limitations of the server network into account. A number of methods based on local search algorithms for the solution of the mapping problem are proposed and verified by use of a set of benchmark problems. The simulations show that these heuristic solutions can achieve nearly optimal solutions in a short computational time.

Abstract:Non-Repudiation in data sending and receiving is essential in the secure communication. In recent years, this kind of cryptographic protocols has been mainly implemented by the intervention of the trusted third party in transmission and encryption of data, thus the dependability and security of the trusted third party become a bottleneck in these secure systems. In this paper, a fair non-repudiation cryptographic protocol (NCP) for both sender and receiver is proposed. It is a more efficient and secure protocol, which solves the bottleneck problem of trusted third party. And its formal analysis is presented using the belief logic. Finally its applications to E-mail communication are discussed.

Abstract:A novel neural network based rule extraction method is proposed in this paper. This method consists of a primary network and its corresponding mapping network, which includes twice convergent processes. The knowledge acquisition and network construction of the method are fulfilled by the first convergence of the primary network. Here by a mapping network corresponding to the converged primary network is created whose convergence is capable of realizing the rule extraction. Since there is no need of enumerating the overall space of solutions for this method to extract rules, therefore the searching efficiency is greatly increased and the computation complexity is dramatically reduced. Meanwhile, a stop criterion of rule extraction in terms of difference of belief degree is also proposed in this paper. A lot of simulation experiments and practical applications illustrate and verify the validity and correctness of the proposed method.

Abstract:In this paper, a synchronization QoP (quality of presentation) mapping concept is proposed for meeting the quality requirement of multimedia real-time transmission. The essence of this idea is to create a tool to measure the synchronization quality for distributed multimedia systems from the viewpoint of perceptive field through building the fuzzy mapping from QoS (quality of service) to QoP. Based on Dr. Ralf Steinmetz's perception experiment, the algorithm to construct the synchronization QoP mapping is proposed. This algorithm is based on approximating perceptual annoying curves. By extracting the fuzzy membership functions, it implements the fuzzy mapping from QoS to QoP. With this algorithm, the paradigm which applies the fuzzy QoP mapping to time model of multimedia synchronization in real-time multimedia communication is also presented. Using the fuzzy membership function of fuzzy QoP mapping as conditions of fuzzy control mechanism, the transition of synchronization semantics can be controlled to adjust the quality of media synchronization.

Abstract:Generalized selective scheduling (GSS) is presented to uniformly process loops and acyclic code. GSS does not differentiate acyclic code from cyclic code, but generates the result of global compaction and software pipelining for them respectively. The program is parallelized not by hierarchical simplification, but by only one-pass sequential scanning. As the first global scheduling based on general graphs instead of traces or directed acyclic graphs, GSS breaks the boundary between acyclic and cyclic code scheduling. It views nested loops from a fresh angle, realizing the direct scheduling of nests by properly calculating availability sets and live variable sets. It is applicable to programs with arbitrary control flow.

Abstract:β-Acyclic database scheme has a number of desirable properties, but most former researches about β-acyclic are based on graph theory, without consideration on other canonical properties of database. With the concept of mixed dependency basis, this paper defines the concepts of strict conflict-free and extended strict conflict-free, and proves that decomposition satisfies lossless join, keeps dependency, β-acyclic and 4NF if and only if it is extended strict conflict-free in the mixed environment. Based on this, the paper gives the algorithm for judging strict conflict-free and β-acyclic decomposition in mixed environment, then shows that the complexity of the algorithm is linear using an example based on line graph. This conclusion can directly guide real database designing.

Abstract:BAN family of logic is used to analyze the security of cryptographic protocols. Five logics in the BAN family of logic are analyzed, including GNY, AT91, MB, SVO and BAN logic itself. Many defects of BAN family of logic are presented, including some defects found in research. A model is presented to describe the BAN family of logic first. And then the defects of BAN family of logic are classified according to this model. Some problems concerning BAN family of logic are presented in order to stimulate further research.

Abstract:Obstacle detection plays an important role in intelligent vehicle system research. In this paper, the general theory of obstacle detection algorithm is presented based on Ground Plane Transformation. A parametric model for obstacle detection applications is constructed and the influences of the internal, external and pose parameters of the camera on the transformation matrix are discussed. In order to fulfill the requirement in the vibration situations, a new obstacle detection algorithm is proposed based on stereo vision disparity analysis. Experiments show that low computation amount and high reliability can be achieved with the new algorithm.

Abstract:Physical processors are often viewed as a logical processor grid or process grid to ease the parallel algorithm implementation and to provide useful coordination information among parallel processes. However, the shape of processor grid has great impact on the final performance of user's parallel programs. How to select a suitable or even optimal processor grid for an parallel algorithm on certain parallel machines becomes an urgent problem. In this paper, a novel method named MDCPS (minimum degree of communication point set) is proposed, which tries to find out the optimal processor grid for parallel program independent the impaction of load balance through analysis on its communication pattern. The analysis results on ScaLAPACK parallel Cholesky factorization program match the experimental results well and show that the proposed method can select the optimal processor grid for parallel program successfully.

Abstract:Testing of communication libraries for parallel computing plays an important role in parallel computing systems. In general, testing of communication libraries is done by some testers designed to test every or several parts of the libraries separately. However, many errors of libraries can not be tested by the separate methods, and they will appear when many parts of libraries are running by combination of them in term of a kind of complicated and organic way. But it is rather difficult that the complicated and organic combinations result from the design of library testers themselves. This paper proposes two new testing approaches, which are based on the feature of layered library architectures and test lower libraries by portable testers of upper libraries. The testers of upper libraries can also be regarded as application programs of lower libraries, but they are different from general application programs of lower libraries. They almost cover every part of lower libraries, combine them organically, and form a complicated situation in run time, which can not be easily obtained only by testers of lower libraries. In this case, the errors may be exposed which can escape from the testers of lower libraries.

Abstract:The nesting problem of irregular shapes has not been solved completely so far. This paper introduces case (master drawing) based reasoning method for solving nesting problem and presents the structure frame of nesting system based on the master drawings. The key aspect of this method is shape matching, which can be described as when the spare groups and board are provided, how to retrieve corresponding master drawing from drawing database. A similarity retrieval algorithm for master drawings is proposed in this paper based on the Findler distance between pattern strings of the shapes' simplified skeletons. A numerical example shows the method is effective.