Loading...
ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 March 2005, Volume 42 Issue 3
Paper
The Separation between Storage and Computation
Ma Yili, Fu Xianglin, Han Xiaoming, and Xu Lu
2005, 42(3):  . 
Asbtract ( 1432 )   PDF (552KB) ( 2238 )  
Related Articles | Metrics
Classical computer architecture is challenged by the development of current computing application. Systems constructed by fix-linked computation and storage can not satisfy the demand of dynamic computing. To resolve this problem, the concept of physical separation and logic separation between storage and computation is introduced, and a three-dimensional reconstructed computing environment is constructed based on this concept. In this case, user program, storage and computation can be assembled dynamically to satisfy the demand of application. Without the restriction of resource location and operating environment, the computing process presents the feature of being data-driven, and computing on demand is realized as well. Therefore, the computing system can provide the user with more wide service.
Supervised Independent Component Analysis by Maximizing J-Divergence Entropy
Huang Yaping, Luo Siwei, and Qi Yingjian
2005, 42(3):  . 
Asbtract ( 403 )   PDF (341KB) ( 462 )  
Related Articles | Metrics
Independent component analysis (ICA) is one of the most exciting topics in the fields of neural computation, advanced statistics, and signal processing, which finds independent components from observing multidimensional data based on higher order statistics. The theory of independent component analysis is traditionally associated with the blind source separation (BSS). Since the recent increase of interest in ICA, it has been clear that this principle has a lot of other interesting applications, especially feature extraction. But traditional independent component analysis mainly aims at BSS and is not suitable for recognition and classification due to ignorance of the contribution of independent components to recognition performance. In order to overcome this problem, a new supervised ICA algorithm based on J-divergence entropy is proposed, which can measure the difference of classes. Experiment results of face and iris recognition show that the algorithm improves the performance efficiently.
A Fast Kernel-Based Nonlinear Discriminant Analysis Method
Xu Yong, Yang Jingyu, Jin Zhong, and Lou Zhen
2005, 42(3):  . 
Asbtract ( 406 )   PDF (424KB) ( 421 )  
Related Articles | Metrics
The least squares solution of novel discriminant analysis method, based on kernel trick, is equivalent to kernel-based Fisher discriminant analysis. The discriminant vector of the novel method is efficiently solved from linear equations. Moreover, corresponding classifying strategy is very simple. The most striking advantage of the novel method is that only a few original training samples are sorted as “significant” nodes for constructing discriminant vector. As a result, corresponding testing is much more efficient than the nave kernel Fisher discriminant analysis. In addition an appropriative, optimized algorithm is developed to improve the efficiency of selecting “significant” nodes. Experiments on benchmarks and face databases show that the performance of the novel method is comparative to kernel-based Fisher discriminant analysis, with superiority in efficiency.
An Active Learning Approach for Neural Network Ensemble
Wang Zhengqun, Chen Shifu, and Chen Zhaoqian
2005, 42(3):  . 
Asbtract ( 613 )   PDF (365KB) ( 1205 )  
Related Articles | Metrics
After analyzing the relationship among the generalization error of the neural networks ensemble, the generalization error, and the diversity of the individual neural network, a individual neural networks active learning algorithm ALA is proposed, which encourages individual neural network to learn from the expected goal and others, so all individual neural networks are trained simultaneously and interactively. In the stage of combining individual neural networks, a selective approach is proposed, which adds a bias to every individual network and selects part of individual networks to constitute an ensemble. Experiment results show that an efficient neural networks ensemble system can be constructed by using the individual networks learning algorithm ALA and selective ensemble approach.
An Effective Unsupervised Feature Selection Method for Text Clustering
Liu Tao, Wu Gongyi, and Chen Zheng
2005, 42(3):  . 
Asbtract ( 799 )   PDF (345KB) ( 1286 )  
Related Articles | Metrics
Feature selection has been successfully applied to text categorization, but rarely applied to text clustering, because those effective supervised feature selection methods can't be applied to text clustering due to the unavailability of class label information. So a new feature selection method called “K-Means based feature selection (KFS)” method is proposed in this paper, which addresses the unavailability of label information by performing effective supervised feature selections on different K-Means clustering results. Experimental results show that ① KFS successfully selects out the best small part of features and significantly improves the clustering performance; and ② Compared with other feature selection methods, KFS is very close to the ideal supervised feature selection methods and much better than any unsupervised methods.
A Micro-Scheduling Method on Directed Cyclic Graph
Wen Yanzhi, Lian Ruiqi, Wu Chengyong, Feng Xiaobing, and Zhang Zhaoqing
2005, 42(3):  . 
Asbtract ( 254 )   PDF (404KB) ( 498 )  
Related Articles | Metrics
Instruction scheduling plays a critical role in compiler. How to detect structural hazards before facilitating the resource of the processor, and how to exploit the parallelism of the source code have become one of the hotspots of instruction scheduling when it tries to improve the execution efficiency of the program and to increase the flexibility of the code. So far, micro-scheduler has achieved some effect but it does not support the scheduling on directed cyclic graph generated by software pipeline. A new micro-scheduling method is provided and implemented based on IA-64 architecture in open research compiler which can reduce the execution cycles of the program and the stalls of the pipeline effectively with satisfying execution efficiency.
Design and Implementation of a Memory Model Simulator
Wu Junmin, Yang Chao, Chen Guoliang, Zhang Miaohui, and Men Ke
2005, 42(3):  . 
Asbtract ( 406 )   PDF (528KB) ( 504 )  
Related Articles | Metrics
Cache coherence and memory consistency are two important problem to a shared memory parallel computer. Many coherence protocol and consistency model have been proposed for different systems. Simulation is a quantitative approach to compare different consistency model and coherence protocol. This paper gives a scheme and implementation of a shared memory model simulator—MMS. First the framework of the simulator is described. MMS includes an execution engine and a virtual shared memory system. The engine can execute parallel threads and simulate the behavior of shared memory system. Several memory consistency models are realized, such as sequential consistency model, weak consistency model, release consistency model and lazy release consistency model. Then different memory consistency models, including SC, WC, RC and LRC, are compared between different parallel computer architecture models, including SMP and DSM. The behavior of different memory consistency models is also simulated in solving different type computing problem, including computing intensive problem, communication intensive problem and memory intensive problem. To achieve high performance several cache coherence protocols are proposed. Finally it is concluded that for different computer architectures, proper memory consistency model and proper cache coherence protocol should be employed.
Formal Method Research on Integer Multiplier Verification
Wang Haixia and Han Chengde
2005, 42(3):  . 
Asbtract ( 314 )   PDF (402KB) ( 516 )  
Related Articles | Metrics
Model checking based on decision diagram causes memory explosion in integer multiplier verification. An efficient solution to this problem is backward substitution method. As the kernel of backward substitution method, the performance of function substitution algorithm is crucial to the efficiency of verification process using backward substitution method. If the variable to be substituted is ensured to be the top variable of the function to be substituted, the function substitution algorithm can be simplified. By setting variable order and variable substitution order, an improved backward substitution method is presented, where in each substitution, the variable substituted is the top variable of the decision diagram of function to be substituted. As experiment shows, under 1GB memory, the improved method enhances the scale of Add-Step multiplier which can be verified from 84×84 bits to 256×256 bits,and Diagonal multiplier from 84×84 bits to 206×206 bits.
Study of Multiview Video Coding Based on the FGS Coding Method
Huang Chao and Li Jintao
2005, 42(3):  . 
Asbtract ( 343 )   PDF (341KB) ( 414 )  
Related Articles | Metrics
The data amount of multiview video is several times that of general video. If effective compression technique is not used, it is impossible to transmit and store multiview video effectively, which also becomes the barrier of the extensive application of the multiview video. Therefore, it is necessary to do research in developing new multiview video compression techniques. With the development of network, more attention has been given to the technique which can provide interactive multiview video, and how to effectively transport multiview video through network has become more and more important. In this paper, a new multiview video codec based on the FGS(fine granularity scalable)coding method is proposed. Experiments indicate that this codec can improve the transmission of multiview video, while providing high coding efficiency .
Image Fusion Using SGNN
Bao Fumin, Li Aiguo, and Qin Zheng
2005, 42(3):  . 
Asbtract ( 412 )   PDF (453KB) ( 455 )  
Related Articles | Metrics
There have been some reports on approaches to image fusion based on neural networks recently. But these approaches have some shortages, such as being complex on computing, and having to have their network structures and many parameters to be set by users in advance. Self-generating neural network (SGNN) is a self-organization neural network, whose network structures and parameters need not to be set by users, and its learning process needs no iteration. In this paper, an approach to image fusion using SGNN is proposed. This newly proposed approach consists of three steps: ①pre-processing of the images. It removes the noises in the images by discrete wavelet transforms; ②clustering pixels using SGNN; and ③ fusing images using fuzzy logic algorithms. The approach has advantages of being wieldy used by users and having high computing efficiency. The experimental results demonstrate that the MSE (mean square error) reduced by this proposed approach decreases 30%~60% than that by Laplacian pyramid and discrete wavelet transform approaches.
Fast Texture Synthesis Algorithm Using PSO
Zhang Yan, Li Wenhui, Meng Yu, and Pang Yunjie
2005, 42(3):  . 
Asbtract ( 343 )   PDF (725KB) ( 444 )  
Related Articles | Metrics
Texture synthesis is of importance to computer vision and graphics. The technique has great potential in many applications, especially in image editing, computer animation, real-time rendering for large scale of scenes, realistic and non-photorealisitic rendering etc.. In this paper, a survey of traditional and contemporary texture synthesis methods is presented. Fast texture synthesis algorithm using PSO is an effective texture synthesis algorithm. Particle swarm optimization (PSO) is applied to improve the process of searching and matching in the texture synthesis by patch-based sampling, thus changing the throughout search method of the original algorithm and speeding up the process of synthesis without influencing the quality of the image. It is shown that high-quality texture can be synthesized in several seconds on a midlevel PC, and this algorithm works well for a wide variety of texture ranging from regular to stochastic. How the number of the particles and the iterations influence the speed of the synthesis is analyzed in detail.
Real Time Detection and Recognition of Passenger Flow Based on Image Sequences
Gao Chengying, Liu Ning, and Luo Xiaonan
2005, 42(3):  . 
Asbtract ( 462 )   PDF (549KB) ( 1030 )  
Related Articles | Metrics
A new pedestrian tracking and recognizing method is presented aiming at solving the problems in tracking and accounting pedestrian flow in visible light, such as low accuracy in dividing moving object and poor recognizing effect. Firstly, the moving object is divided by combining the SODP with edge detection and measure according to the consistency of the moving objects in the visual flow. Secondly, the tracking feature vectors are extracted rapidly with rough sampling based on the pedestrian moving model and the part feature of moving object. And the satisfying accuracy and recognizing speed are obtained when a pattern recognizes moving objects with features such as projection ratio of moving object outline and figure factors, and with the moving object assorting tool based on artificial neural network. The method is used in real time tracking and accounting the pedestrian flow in large malls, and the practical test results indicate that satisfying effect is obtained in both processing efficiency and recognizing accuracy with this method. Moreover, it has good adaptability to external influence such as light of the test spot, shadow of pedestrian, and change of pedestrian flow.
An Algorithm for Computing the Finite Closure of Attributes for Temporal Functional Dependencies with Multiple Time Granularities
Yao Chunlong, and Hao Zhongxiao,
2005, 42(3):  . 
Asbtract ( 307 )   PDF (400KB) ( 483 )  
Related Articles | Metrics
In order to design temporal databases effectively, temporal functional dependencies (TFDs) supporting for multiple granularities of time are used to normalize temporal schemes. A crucial problem that needs to be solved for normalization of temporal databases is to compute the finite closure of attributes for TFDs. Usages of multiple granularities of time make it very complex to compute the finite closure of attributes. In fact, TFDs are proper extensions of traditional functional dependencies (FDs). Thus, there exist close relationships between TFDs and traditional FDs. By analyzing the relationships and properties of close sets of temporal types, an algorithm for computing effectively the finite closure of attributes is proposed by using the corresponding algorithm for traditional FDs. According to the analysis and the comparison with related algorithms, the algorithm proposed is more effective than the other ones.
An Incomplete Combination Lattice of Dimension and Its Incremental Construction Method
Gao Hongbin, Lin Youfang, and Huang Houkuan
2005, 42(3):  . 
Asbtract ( 305 )   PDF (393KB) ( 510 )  
Related Articles | Metrics
Dimension structures of multidimensional model in data warehouse are hierarchical and this also leads the logical dimension structure to be hierarchical so that the dynamic characteristics of analysis, which often switches between different levels of dimension, can be better supported. Traditional algebraic lattice structure does not support more than one key in a single dimension simultaneously, while combination lattice structure supports composite keys in a single dimension by extending the traditional model. The concept of incomplete combination lattice of dimension is introduced to further improve the former combination lattice model. Incomplete combination lattice of dimension makes it possible to reduce the space of cube views while modeling data cube dimensions. Operations on combination lattice are also presented, and then used to implement an incremental method of constructing combination lattice structure.
A Depth-First Search Algorithm for Mining Maximal Frequent Itemsets
Yan Yuejin, Li Zhoujun, and Chen Huowang
2005, 42(3):  . 
Asbtract ( 454 )   PDF (359KB) ( 615 )  
Related Articles | Metrics
Maximal frequent itemsets mining is a fundamental and important problem in many data mining applications. Since the MaxMiner algorithm first introduced the enumeration tree for MFI mining in 1998, there have been several proposed methods using depth-first search to improve performance. Here presented is DFMfi, a new depth-first search algorithm for mining maximal frequent itemsets. DFMfi adopts bitmap data format, several popular prune techniques which prune the search space efficiently, and local maximal frequent itemsets for superset checking quickly. Experimental comparison with the previous work indicates that it accelerates the generation of maximal frequent itemsets obviously, thus reducing CPU time.
Query Processing for Ontology-Based XML Data Integration
Tao Chun, Zhang Liang, and Shi Baile
2005, 42(3):  . 
Asbtract ( 495 )   PDF (541KB) ( 437 )  
Related Articles | Metrics
There has been a significant focus on data integration for a long time. Recently XML has become the de-facto standard for publishing and exchanging data on the Web. And researchers presented various integration schemes of XML data, but XML itself is not very appropriate for describing the global schema. One of the schemes which uses ontology to describe global schema gains our research interest. Because the original research work did not really present an algorithm to generate maximal query execution plan, after formalizing the scheme, a naive algorithm named NaiveMaxQEP to generate the maximal query execution plan is provided in this paper. And then an optimized algorithm OptMaxQEP is presented based on the assumption of limited number of incomplete roles in the global ontology. Finally, in order to support efficiency of distributed resource integration, an optimization algorithm NetOptQEP working on the generated maximal query execution plans to produce network-cost optimized plans is also presented.
An Approach to Generate Semantic Network of Concept Based on Structural Corpus
Zheng Qinghua, Wang Zhaojing, and Sun Xia
2005, 42(3):  . 
Asbtract ( 271 )   PDF (395KB) ( 573 )  
Related Articles | Metrics
Recent literature in computational terminology has shown an increasing interest in identifying various semantic relations between concept, which are important for large-scale natural language application systems such as question answering (QA), information retrieval (IR), machine translation (MT), and so on. Taking a natural-language-oriented Web answer system, named NL-WAS, as the application background, a novel approach to generate semantic network of concept based on the semi-structural corpus is proposed. According to the characteristic of the corpus, proper document extraction templates are adopted for 4 kinds of relations between concepts, namely, synonymy, hyponymy, hypernymy and parataxis. Moreover, different window sizes are designed to calculate the relative degree between concepts, and then by choosing the threshold through experimental results and switching the role can obtain all kinds of relationships. Finally, using proper rules, the concept semantic network is optimized. Now the proposed algorithm has already been implemented and applied in the natural language-oriented Web answer system. It is shown that the semantic network of concept can improve the result of the question search of NL-WAS system effectively.
Dynamic Parameter Learning Approach for Information Retrieval with Genetic Algorithm
Zhang Min, Lin Chuan, and Ma Shaoping
2005, 42(3):  . 
Asbtract ( 281 )   PDF (434KB) ( 482 )  
Related Articles | Metrics
Parameter setting in information retrieval (IR) systems affects retrieval performances greatly. These parameters are always data-dependent and sensitive, which causes the fallibility of experiential values. Moreover, supervised parameter learning approaches are not applicable for lacking of relevant information while retrieving. Therefore, an automatic unsupervised parameter learning mechanism is necessary and important. In this paper, the effectiveness of traditional manual parameter setting with fixed experiential values is studied first, which indicates that the traditional way is not feasible or reliable to use widely in practice. Then, a dynamic parameter learning approach with genetic algorithm (GA) is proposed. Experiments have been done on Okapi system using large scale data sets of TREC11, TREC10 and TREC9 web track collections, each of which is more than 10GB. Results show that by dynamic parameter learning, the system always gets or approaches the best retrieval performance.
Performance Analysis of HTTP Service Based on Network Active Measuremnet
Fan Chao, Xie Gaogang, Zhang Dafang, and Li Zhongcheng
2005, 42(3):  . 
Asbtract ( 429 )   PDF (471KB) ( 354 )  
Related Articles | Metrics
Internet workload is dominated by Web traffic today, which demonstrates its perceived performance by some well-known metrics, such as response time and download rate. The popular approaches to measuring HTTP performance are Web server and client logs, or traffic traces. The performance differences are compared to improve protocol design and implementation by building corresponding pattern to various parameters from different levels existing behind Web browsing, such as the number of connections per page, the connection sizes, etc., or by simulating HTTP processes under different workload or version. But the customers' urgent demand is how to detect service response time and Web page download rate, which provide impactful knowledge to pinpoint the source of HTTP performance problems, and how to detect performance outliers and alarm timely. The performance of HTTP service along the end-to-end path is obtained through the method of active measurement. Furthermore, with the experimental data the composing and distribution of HTTP service response time are analyzed. And the high variation of the download rate is found in multiple accesses to the same Web page, which proves that some popular approaches to performance fault detection, such as mean and standard deviation calculation, do not fully serve the turn. Therefore a better algorithm based on box plots to detect performance outliers of HTTP service is presented.
Research on Authentication Trustworthiness Theory
Wang Lunwei, Liao Xiangke, and Wang Huaimin
2005, 42(3):  . 
Asbtract ( 327 )   PDF (297KB) ( 395 )  
Related Articles | Metrics
One of the foundations of operating system security is authentication. Without being sure with whom an entity interacts, the three fundamental properties—confidentiality, integrity and availability—can be trivially violated. But there are several uncertainty factors in the user authentication procedure in current operating systems, such as the uncertainties of authentication mechanisms, the uncertainties of authentication rules and the uncertainties of authentication conclusions. This paper borrows the idea of uncertainty reasoning in expert system field, puts forward the thought of authentication trustworthiness, and gives the authentication trustworthiness factor model. The model describes the measure for these uncertainty factors in user authentication procedure. Aiming at some important and especially secure systems needing several authentication mechanisms, this paper gives and demonstrates the parallel propagation formula of authentication trustworthiness factor. After calculating the user's final authentication trustworthiness, the system decides whether the user has passed system authentication. By introducing the thought of authentication trustworthiness into authentication system, it can not only describe the uncertainty factors existing in authentication system very well, but also enhance the security of those systems needing multiple authentication mechanisms very well.
A Preemptive Scheduling Problem with Different Interrupted Time Cost on Identical Parallel Machines
Zhou Huaqi, Lu Mingming, and Zhu Hong
2005, 42(3):  . 
Asbtract ( 352 )   PDF (375KB) ( 366 )  
Related Articles | Metrics
A new preemptive scheduling problem P|ptmn(δ\-i)|C\-{max} is proposed in this paper, in which a preemption penalty δ\-i is introduced if a task is interrupted and resumed later. This problem has numerous applications in task scheduling, distributed computing, and network communication. Firstly, P|ptmn(δ\-i)|C\-{max} is proved to be an NP-hard optimization problem. Then an LPT algorithm is presented. LPT is relatively succinct and easy to implement. However, the approximation ratio of LPT is unsatisfied. In order to improve the approximation ratio, a new LPT-based algorithm is designed. In this LPT-based algorithm, the technique of LPT is applied to not only the execution time p\-i but also the interrupt time δ\-i, therefore avoiding the worst case of LPT algorithm. In the key part of the LPT-base algorithm, the averaging technique is employed to enhance the parallelism.
Software Simulation for Hardware/Software Co-Verification
Wang Shihao, Wang Xinmin, and Liu Mingye
2005, 42(3):  . 
Asbtract ( 344 )   PDF (314KB) ( 499 )  
Related Articles | Metrics
With the development of integrated circuits and computer science, software and hardware of the target system become more and more sophisticated while the traditional methods of the embedded system design appear to be outdated. For complicated embedded systems, co-verification is often used to verify the system co-design, in which hardware simulator based on hardware specification is used to validate the hardware design while the processor architecture model known as instruction set simulator (ISS) is used to interpret the target code of the embedded software, generate output, and drive the hardware. The ISS simulates the embedded software at detailed timing level for the target processor, simulating at such a low-level that it often becomes the bottleneck for hardware/software co-simulation. In this paper, a fast software simulating method is put forward, in which, an open-source RTOS is extended and hardware-simulating driver is used to build connection for the hardware/software simulator. The simulating method based on the compiled code model for the embedded software verifies the software from the system behavior level, so higher co-verification performance can be achieved. Combined the with verification method of ISS, the high-level co-verification method can achieve faster and more effective co-verification. Finally, examples of co-design and results of co-verification are presented to show the correctness of the co-verification method.
Survey of Web Communities Identification
Yang Nan, Gong Danzhi, Li Xian, and Meng Xiaofeng
2005, 42(3):  1. 
Asbtract ( 496 )   PDF (425KB) ( 1695 )  
Related Articles | Metrics
WWW is a complicated collection of hypertext and expands with tremendous speed. Finding and applying usable information of Web is a challenging job. There exist a lot of communities while Web evolves. These communities are very important information in Web organization. Knowing these communities is helpful to overview the whole Web. Organizing Web into communities has many advantages. With communities, users can navigate their interesting information, Internet/Intranet service providers can arrange efficient ports, and manufacturers can find right consumers. Community also reflects sociality of Web, because Web is a social network. At present, many communities are found and maintained by human effort. It is costly and difficult to update. Nevertheless, there are still many unknown and newly emerged communities. It is impossible to find them manually. Therefore, this motivates many researches on automatic or semi-automatic discovering technologies. The method of community extraction consists of two categories, one is topic-oriented, the other is non-topic. They have different data sources. The former uses results from search engine by a query term and the latter uses a raw data from a crawler. But this field is still new and there remain still many problems. This paper analyzes the algorithms of community finding at present, and describes the challenging problems and promising research trends.