In this paper we propose a suffient condition for minimal routing in 3-dimensional (3-D) meshes with faulty nodes. It is based on an early work of the author on minimal routing in 2-dimensional (2-D) meshes. Unlike many traditional models that assume all the nodes know global fault distribution or just adjacent fault information, our approach is based on the concept of limited global fault information. First, we propose a fault model called faulty cube in which all faulty nodes in the system are contained in a set of faulty cubes. Fault information is then distributed to limited number of nodes while it is still suffient to support minimal routing. The limited fault information collected at each node is represented by a vector called extended safety level. The extended safety level associated with a node can be used to determine the existence of a minimal path from this node to a given destination. Specifically, we study the existence of minimal paths at a given source node, limited distribution of fault information, minimal routing, and deadlock-free and livelock-free routing. Our results show that any minimal routing that is partially adaptive can be applied in our model as long as the destination node meets a certain condition. We also propose a dynamic planar-adaptive routing scheme that offers better fault tolerance and adaptivity than the planar-adaptive routing scheme in 3-D meshes. Our approach is the first attempt to address adaptive and minimal routing in 3-D meshes with faulty nodes using limited fault information.

A major problem of mobile agents is their apparent inability to authenticate transactions in hostile environments. In this paper, a new secure anonymous mobile agent scheme is proposed for the prevention of agent tempering without compromising the mobility or autonomy of the agent. In the scheme, a mobile agent can produce valid signature on website's bid (it means to transact a contact with the web site) on behalf of its customer, without revealing the customer's real private key. In addition, the anonymity of the customer is also achieved when its agent transacts with the websites. Furthermore, the customer who issues a malicious agent or denies the transaction can be identified and detected by Agent Management Center (AMC). Therefore, the scheme is practical in the future electronic commerce over Internet.

In this paper, the 1-D real-valued discrete Gabor transform (RDGT) proposed in the previous work and its relationship with the complex-valued discrete Gabor transform (CDGT) are briefly reviewed. Block time-recursive RDGT algorithms for the efficient and fast computation of the 1-D RDGT coefficiients and for the fast reconstruction of the original signal from the coefficients are developed in both critical sampling and oversampling cases. Unified parallel lattice structures for the implementation of the algorithms are studied. And the computational complexity analysis and comparison show that the proposed algorithms provide a more efficient and faster approach to the computation of the discrete Gabor transforms.

Bayesian approach is an important method in statistics. The Bayesian belief net- work is a powerful knowledge representation and reasoning tool under the conditions of uncertainty. It is a graphics model that encodes probabilistic relationships among variables of interest. In this paper, an approach to Bayesian network construction is given for discovering the Chinese linguistic parameter relationship in the corpus.

In this paper, we present a programmable method of revising a nite clause set. We rst present a procedure whose formal parameters are a consistent clause set T and a clause A and whose output is a set of minimal subsets of T which are inconsistent with A. The maximal consistent subsets can be generated from all minimal inconsistent subsets. We develop a prototype system based on the above procedure, and discuss the implementation of knowledge base maintenance. At last, we compare the approach presented in this paper with other related approaches. The main characteristic of the approach is that it can be implemented by a computer program.

Dynamic programming algorithms based on Lagrange multiplier method is often used for obtaining an optimal bit allocation strategy to minimize the total distortion given a constrained rate budget in both source and channel coding applications. Due to possible large quantizer set and improper initialization, the algorithm often suers from heavy computational complexity. There have been many solutions in recent years to the above question. In this paper, a simple but efficiient algorithm is presented to further speed up the convergence of the algorithm. This algorithm can be easily realized and get the final solution much faster. The experimental result shows that our new algorithm can figure out the optimal solution with a speed 5-7 times faster than the original algorithm.

Web hyperlink structure analysis algorithm plays a signicant role in improving the precision of Web information retrieval. Current link algorithms employ iteration function to compute the Web resource weight. The major drawback of this approach is that every Web document has a xed rank which is independent of Web queries. This paper proposes an improved algorithm that ranks the quality and the relevance of a page according to users' query dynamically. The experiments show that the current link analysis algorithm is improved.

In this paper, the parameter which is the source of the complexity of disjunction- free default reasoning is determined. It is shown that when the value of this parameter is xed, the disjunction-free default reasoning can be solved in time bounded by a polynomial whose degree does not depend on the parameter. Consequently, disjunction-free default reasoning is xed parameter tractable.

Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions. Namely, given any two permutations, nd the short-est distance between them. This problem is related with genome rearrangement. The sorting of signed permutations is studied. Because in genome rearrangement, genes are oriented in DNA se-quences. The transpositions which have been studied in the literature can be viewed as operations working on two consecutive segments of the genome. In this paper, a new kind of transposition which can work on two arbitrary segments of the genome is proposed, and the sorting of signed permutations by reversals and this new kind of transpositions are studied. After establishing a lower bound on the number of operations needed, a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.

In statistical language models, how to integrate diverse linguistic knowledge in a general framework for long-distance dependencies is a challenging issue. In this paper, an improved language model incorporating linguistic structure into maximum entropy framework is presented. The proposed model combines trigram with the structure knowledge of base phrase in which trigram is used to capture the local relation between words, while the structure knowledge of base phrase is considered to represent the long-distance relations between syntactical structures. The knowledge of syntax, semantics and vocabulary is integrated into the maximum entropy framework. Experimental results show that the proposed model improves by 24% for language model perplexity and increases about 3% for sign language recognition rate compared with the trigram model.

In many video standards based on inter-frame compression such as H.26x and MPEG, block-matching algorithm has been widely adopted as the method for motion estimation because of its simplicity and eectiveness. Nevertheless, since motion estimation is very complex in computing. Fast algorithm for motion estimation has always been an important and attractive topic in video compression. From the viewpoint of making motion vector field smoother, this paper proposes a new algorithm SMVFAST. On the basis of motion correlation, it predicts the starting point by neighboring motion vectors according to their SADs. Adaptive search modes are used in its search process through simply classifying motion activity. After discovering the ubiquitous ratio between the SADs of the collocated blocks in the consecutive frames, the paper proposes an effective half-stop criterion that can quickly stop the search process with good enough results. Experiments show that SMVFAST obtains almost the same results as the full search at very low computation cost, and outperforms MVFAST and PMVFAST in speed and quality, which are adopted by MPEG-4.

This paper describes a new framework for synthesizing Chinese landscape painting using an image-based approach. The framework involves two stages: a preprocessing phase, in which a few brush stroke texture primitivities (BSTP) are collected from samples of hand-made Chinese paintings, and the control picture is constructed to provide color IDs of mountains, and the on-line phases, in which the fog image is synthesized and mountains are \drawn" by mapping multiple layers of BSTP guided by the control picture. When more complex shading is needed, the shading picture is constructed and used during the BSTP mapping phase. Finally, the synthesized Chinese landscape paintings of a variety of styles are given and they look more close to the hand-made work than those produced with previous modeling methods.

It is widely accepted that the design of morphological filters, which are optimal in some sense, is a difficult task. In this paper a novel method for optimal learning of morphological filtering parameters (Genetic training algorithm for morphological lters, GTAMF) is presented. GTAMF adopts new crossover and mutation operators called the curved cylinder crossover and master-slave mutation to achieve optimal filtering parameters in a global searching. Experimental results show that this method is practical, easy to extend, and markedly improves the performances of morphological filters. The operation of a morphological filter can be divided into two basic problems including morphological operation and structuring element (SE) selection. The rules for morphological operations are predefined so that the filter's properties depend merely on the selection of SE. By means of adaptive optimization training, structuring elements possess the shape and structural characteristics of image targets, and give specific information to SE. Morphological lters formed in this way become certainly intelligent and can provide good filtering results and robust adaptability to image targets with clutter background.

This paper describes an immersive system, called 3DIVE, for interactive volume data visualization and exploration inside the CAVE virtual environment. Combining interactive volume rendering and virtual reality provides a natural immersive environment for volumetric data visualization. More advanced data exploration operations, such as object level data manipulation, simulation and analysis, are supported in 3DIVE by several new techniques. In particular, volume primitives and texture regions are used for the rendering, manipulation, and collision detection of volumetric objects; and the region-based rendering pipeline is integrated with 3D image lters to provide an image-based mechanism for interactive transfer function design. The system has been recently released as public domain software for CAVE/ImmersaDesk users, and is currently being actively used by various scientic and biomedical visualization projects.

In this paper a plane-based backward warping algorithm is proposed to generate novel views from multiple reference images. First, depth information is employed to reconstruct space planes from individual reference images and calculate the potential occluding relationship between these planes. Then the planes which represent each identical space plane from dierent reference images are compared with each other to decide the one with the best sample rate to be preserved and used in the later warping period while the other samples are abandoned. While the image of a novel view is produced, traditional methods in computer graphics, such as visibility test and clipping, are used to process the planes reconstructed. Then the planes processed are projected onto the desired image from the knowledge on which plane the desired image pixels are warped from can be acquired. Finally, pixels' depth of the desired image is calculated and then a backward warping is performed from these pixels to the reference images to obtain their colors. The storage requirement in the algorithm is small and increases slowly with the number of reference images increases. By combining the strategy of only preserving the best sample parts and the backward warping algorithm, the sample problem could be well tackled.

Bayesian networks have become a popular technique for representing and reason- ing with probabilistic information. The fuzzy functional dependency is an important kind of data dependencies in relational databases with fuzzy values. The purpose of this paper is to set up a connection between these data dependencies and Bayesian networks. The connection is done through a set of methods that enable people to obtain the most information of independent conditions from fuzzy functional dependencies.

Clustering in very large databases or data warehouses, with many applications in areas such as spatial computation, web information collection, pattern recognition and economic analysis, is a huge task that challenges data mining researches. Current clustering methods always have the problems: 1) scanning the whole database leads to high I/O cost and expensive mainte-nance (e.g., R*-tree); 2) pre-specifying the uncertain parameter k, with which clustering can only be rened by trial and test many times; 3) lacking high efficiency in treating arbitrary shape under very large data set environment. In this paper, we first present a new hybrid-clustering algorithm to solve these problems. This new algorithm, which combines both distance and density strategies, can handle any arbitrary shape clusters effectively. It makes full use of statistics information in mining to reduce the time complexity greatly while keeping good clustering quality. Furthermore, this algorithm can easily eliminate noises and identify outliers. An experimental evaluation is performed on a spatial database with this method and other popular clustering algorithms (CURE and DBSCAN). The results show that our algorithm outperforms them in terms of efficiency and cost, and even gets much more speedup as the data size scales up much larger.

The conventional lock scheme tends to suffer from a cascade of blockings, while the optimistic concurrency control (OCC) scheme may suer from wasting resources. To over-come these problems, some researchers have proposed a combination of OCC and lock in trans-action processing. Using this method, Thomasian proposed the hybrid method for conventional distributed transaction processing, and Lam proposed the DOCC-DA protocol for distributed real-time database system based on forward validation. This paper proposes a new protocol, called Hybrid Distributed Optimistic Concurrency Control Embedded in two-Phase Commit, which is based on back validation. The new protocol makes use of access invariance and runtime information which can guarantee a rerun transaction to meet its deadline and abort the fruitless run transactions as early as possible. A series of simulation experiments have been done to investigate the performance of the new protocol. The results show that its performance is consistently better than that of other protocols.