Abstract:Sorting is an important operation of transaction processing. It is a relatively mature field, as many algorithms for memory sorting, disk sorting and parallel sorting have come forth in the past decades. In this paper, the sorting algorithm is studied from a thoroughly different standpoint, and the THSORT (Tsinghua SORT), a parallel sorting algorithm on a single computer, is brought forward. THSORT uses several processes to control different components of a computer, which enables the data input, sorting and output to be run concurrently, and thus greatly enhances the parallelism and efficiency of the hardware. Experimental results based on a computer with two RAIDs (redundant array of inexpensive disks) indicate that THSORT has almost doubled the performance of NTSORT (new technology SORT), a famous sorting program. Moreover, THSORT has won the 2002 PennySort competition and is still holding the world record in the Daytona category.

Abstract:Finding obstacle-avoiding shortest path is an important problem in VLSI design, and connection graph is a fundamental tool to resolve the problem. The known best graph grounded on knowledge of free area, and it has O(t) vertices and O(tlogt) edges, in which t is the number of extreme edges of the obstacles. In this paper, a generalized connection graph G_G is introduced, which is derived from some new conception such as generalized free area. G_G is made up with vertex that represents the generalized free area and edges for their adjacency. It has only Θ(t) vertices and Θ(t) edges, and it is planar graph. An O(tlogt) time algorithm using plane scanning is designed to construct G_G, and the do not change direction heuristic together with A^* algorithm is used for getting the shortest obstacle-avoiding path using G_G through the conception of formal path. This algorithm shorten the time complexity from O(tlogt)to Θ(t).

Abstract:Reducing communication overhead is extremely important for parallelizing compiler to generate efficient codes for distributed-memory systems. In this paper, a redundant parallel execution model (RPEM) is proposed as an execution model for target programs optimized by the new algorithm. The region graph is introduced, and an effective algorithm is proposed to maximize the regions in the region graph. A region-based data-flow analysis algorithm is proposed to perform communication optimization. The overhead of data-flow analysis can be reduced by performing analysis on the maximized region graph. The coarse grain analysis also helps to communication lift up and aggregation. This communication optimization algorithm is able to perform inter-loop and inter-procedure analysis. Experimental results show that this algorithm is effective in reducing both communication volume and number of messages in programs with a large communication amount.

Abstract:A problem of reversal distance on star-tree is discussed. The problem of 3SAT is induced to the problem of the reversal distance on star-tree with object partially fixed. The fact desribed below is proved, it is still NP-hard to solve the problem of reversal distance on star-tree in which only need to decide the signs of the other symbols to minimizing the sum of distance between object and the given sequences. A polynomial approximation algorithm for the problem is given.

Abstract:Relevance feedback (RF) is used as an effective solution for content-based image retrieval (CBIR). Although it is effective, the RF-CBIR framework does not address the issue of feature extraction for dimension reduction and noise reduction. In this paper, a novel method is proposed for extracting features for the class of images represented by the positive images provided by subjective RF. Principal component analysis (PCA) is used to reduce both noise contained in the original image features and dimensionality of feature spaces. The method increases the retrieval speed and reduces the memory significantly without sacrificing the retrieval accuracy.

Abstract:The algorithm of incremental learning in cover based constructive neural networks (CBCNN) is investigated by using BiCovering algorithm (BiCA) in this paper. This incremental learning algorithm based on the idea of CBCNN can set up many postive-covers and negative-covers, and can modify and optimize the parameters and structure of the neural networks continuously, and can add the nodes according to the need and prune the redundant nodes. BiCA algorithm not only keep the advantages of CBCNN but also fit for incremental learning and could enhance the generalization capability of the neural networks. The simulational results show that the BiCA algorithm is not sensitive to the order of the sample and could learn quickly and steady even if the performance of initial CBCNN is not very good.

Abstract:In this paper, an example-based facial sketch system is presented, which automatically generates a sketch from an input image. All the example sketches are drawn with a particular style. There are two key elements in this system, a non-parametric sampling method and a flexible sketch model. Given an input image pixel and its neighborhood, the conditional distribution of a sketch point is computed by querying the examples and finding all similar neighborhoods. An expected sketch image is then drawn from the distribution to reflect the drawing style. Finally, good quality facial sketches are obtained.

Abstract:An unsupervised learning approach for analysis of human motion is proposed. In this approach, by learning a set of hidden Markov models under constrains of minimal descript length criterion, a continuous gestures sequence could be segmented and clustered, and thus the segments and labels of the original sequence are automatically extracted. The approach contains two steps. First continuous gestures are discretized and an original solution is found in discrete domain based on MDL criterion. Then coming back to continuous domain, a set of HMMs is learnt under constrains of MDL criterion, The HMMs exploit richer dynamics and thus generate better results. Experimental results by using real human gesture data demonstrate the effectiveness of the approach.

Abstract:Lip synchronization is the key issue in speech driven face animation system. In this paper, some clustering and machine learning methods are combined together to estimate face animation parameters from audio sequences and then apply the learning results to MPEG-4 based speech driven face animation system. Based on a large recorded audio-visual database, an unsupervised cluster algorithm is proposed to obtain basic face animation parameter patterns that can describe face motion characteristic. An Artificial Neural Network (ANN) is trained to map the cepstral coefficients of an individual's natural speech to face animation parameter patterns directly. It avoids the potential limitation of speech recognition. And the output can be used to drive the articulation of the synthetic face straightforward. Two approaches for evaluation test are also proposed: quantitative evaluation and qualitative evaluation. The performance of this system shows that the proposed learning algorithm is suitable, which greatly improves the realism of face animation during speech. And this MPEG-4 based learning are suitable for driving many different kinds of animation ranging from video-realistic image wraps to 3D Cartoon characters.

Abstract:OLAP (online analytical processing) queries are complex. When implemented in SQL (structured query language), they usually involve multi-table join and aggregate operations. As a result, how to improve the performance of the multi-table join and aggregate operations becomes a key issue for ROLAP (relational OLAP) query evaluation. To solve this problem, an aggregation algorithm based on group numbers named MuGA (group number based aggregation with multi-table join) is proposed in this paper. By taking the characteristics of star schema into consideration, the algorithm combines the aggregation operation with the novel multi-table join algorithm, Mjoin (multi-table join), and replaces the sorting and hashing method by computed group numbers in aggregation computing. As a result, the algorithm can not only reduce the CPU time, but also reduce the disk I/Os for OLAP queries. As illustrated by the experiments, the performance of the algorithm MuGA is superior to original aggregation methods and the new sorting based method for aggregation.

Abstract:Multi-replication definition (MRD) is a new trend of database replication, but it will increase the propagation costs. In this paper, three optimized propagation algorithms for MRD are presented, D-M, ILS and LIS. D-M Algorithm gets the minimum individual propagation cost by dividing replication objects and merging propagation objects. Based on it, ILS makes the total costs to the least in strict Chain Topology scenarios, and LIS gets optimized total costs in other common situations by decomposing the propagation task. Their correctness and efficiencies are validated both theoretical and experimentally.

Abstract:One of the most important features for a peer-to-peer (P2P) distributed system is to share information and services among nodes with equivalent capabilities and responsibilities by pooling their resources together. Nowadays, most of the existing P2P systems such as Napster and Gnutella only provide some kinds of coarse granularity information sharing without taking account of the content of the file. And, typically nodes (peers) are defined statically. In addition, there is no mechanism to support the join of nodes with temporary network addresses. In this paper, a prototyping P2P system, BestPeer is presented. The BestPeer is unique in several ways. Firstly, it combines the power of mobile agents into P2P systems to perform operations at peers?sites. Secondly, it is self-configurable. A node can dynamically select the set of peers with which it can communicate directly based on some optimization criterion. Thirdly, the BestPeer provides a location independent global named lookup server (LIGLO) to identify peers with dynamic (or unpredictable) IP addresses. The BestPeer is evaluated on a PC cluster consisting of 32 Pentium II running Java-based storage manager. The experimental results show that the BestPeer provides excellent performance compared with traditional non-configurable models. Further experimental study reveals its superiority over Gnutella抯 protocol.

Abstract:The purpose of good database logical design is to eliminate data redundancy and insertion, deletion and update anomalies. For temporal databases, temporal schemes may be normalized by using constraints of temporal functional dependencies (TFDs) with multiple temporal granularities. However, the adoption of temporal dimension and usage of multiple temporal granularities make it very complicated to design a temporal database. Generally, the set of temporal types that can be processed by a system and involved in lots of applications, meet totally ordered relation, and the set of TFDs with a totally ordered set of temporal types is closely related to the Armstrong axioms of traditional functional dependencies (FDs). By analyzing the existing relationships between TFDs and FDs and utilizing corresponding algorithms for traditional set of FDs, some important algorithms such as membership and finite closure of attributes algorithms are proposed for given set of TFDs. These algorithms are the basis of further normalization for temporal databases.

Abstract:Nowadays the most salient trend with network is the increase in data rates while there is significant effort in developing new protocols and services. However, the traditional network devices which are custom logic based or pure software based, could hardly satisfy both performance and flexibility requirements. To overcome this obstacle, the parallel and programmable network processors have been involved into processing path of routers (switch). Besides network processors which are built on ASIP technology and optimized for network applications, possess the characteristic of hardware and software solution simultaneously. Network processors extend the classic store-and-forward pattern to store-process-and-forward, which makes room for complex QoS control and payload processing. In this paper, the related research work is introduced from two aspects, system and application, and the system issues and challenges of network processors are analyzed. In the end, the future evolution of network processors and associate researches are also speculated.

Abstract:With the rapid development of software industry, the copyright protection of software product already becomes a very important issue. In this paper, the software watermarking technique is presented in detail. An overview of software watermarking including the taxonomy, the methods of attacking, the current algorithms, and their advantages and disadvantages are presented in this paper. Finally the state of arts and possible new directions of software watermarking are also stated.

Abstract:Communication subsystem is crucial for cluster computing, which affects its efficiency, adaptability and scalability. Large-Scale applications require challenging communication performance and availability from cluster systems. Multi-Networking communication is a novel approach to improve the communication performance and availability by using multiple network links in parallel. In this paper, the effect of multi-process multiplexing one network link is analyzed, a dynamic link dispatch scheme is proposed, and the design and implementation of a multi-networking communication layer, MNC is introduced, which extends GM messaging layer, and supports multi-Myrinet parallel communication. MNC provides multi-process effectively exploiting the raw performance of multi-Myrinet, and improves the communication performance of application layer significantly. Compared with one-way Myrinet/GM environment, the communication bandwidth between MNC processes has increased by 34% on the PC cluster interconnected with 2-way Myrinet.

Abstract:Virtual interface architecture (VIA) established a communication model with low latency and high bandwidth, and defined the standard of user-level high-performance communication specification in cluster system. In this paper, the current development, the principle and implementations of VIA are analyzed, and a user-level high-performance communication software MyVIA based on Myrinet is presented, which is comfortable with VIA specification. First, the design principle and the framework of MyVIA are described, and then the optimized technologies for MyVIA are proposed, which include UTLB, continued physical memory and varied NIC buffer, the pipelining process based on resource and DMA chain, physical descriptor ring and dynamic cache. The experimental results indicate that the bandwidth of MyVIA for 4KB message is 250MB/s, the lowest one-way latency is 8.46ms, which show that the performance of MyVIA surpasses that of other VIA.

Abstract:With the ever-increasing development of Internet, today抯 data-centric applications require storage platforms not only to possess some properties including high capacity and high scalability, but also to support structured data directly, which is beyond the abilities of current file systems and DBMS. In this paper, a model of network-attached object-based storage devices is presented. It provides storage and index interfaces for structured data employing the power of embedded processors, which eliminates the bottleneck of conventional storage systems. Then the architecture of cluster storage based on the model OStorage is proposed. It introduces the uniform storage of data and meta-data as well as query-locating mechanism to adapt storage hierarchies to structured data. These two methods improve the scalability and availability of the storage system. The prototype of Ostorage is implemented. The experimental results show that the throughput of it increases with the system scale linearly.

Abstract:In this paper, the problem of efficient monitoring for the network flow is regarded as the problem to find out the minimum weak vertex cover set for a given graph G=(V,E). An approximation algorithm is presented. It is proved that the algorithm has a ratio bound of 2(lnd+1), where d is the maximum degree of the vertices in graph G. It is showed that the running time of the algorithm is O(|V|²).

Abstract:An overlay-based congestion management mechanism for assured forwarding in differentiated services (DiffServ) network is presented in this paper. In the proposed scheme, a control packet is sent from the ingress to the egress router every fixed time interval. The ingress router employs a simple additive increase and explicitly decrease algorithm to adjust the aggregate's sending rate according to the QoS (quality of services) information reflected from the egress routers. For the performance evaluation of the proposed scheme, the simulation of the (proportional) fairness of aggregates traffic and packet loss ratio is presented.