The faster higher-order cellular automaton for hyper-parallel undistorted data compression

This paper defines second-order and third-order permutation global functions and presents the corresponding higher-order cellular automaton approach to the hyper-parallel undistorted data compression.The genetic algorithm is successfully devoted to finding out all the correct local compression rules for the higher-order cellualr automaton.The correctness of the higher-order compression rules,the time complexity,and the systolic hardware implementation issue are discussed.In comparison with the first-order automation method reported,the proposed higher-order approach has much faster compression speed with almost the same degree of cellular structure complexity for hardware implementation.     

Fast evaluation of Bounded Slice-line Grid

Bounded Slice-line Grid (BSG) is an elegant representation of block placement, because it is very intuitionistic and has the advantage of handling various placement constraints. However, BSG has attracted little attention because its evaluation is very time-consuming. This paper proposes a simple algorithm independent of the BSG size to evaluate the BSG representation in O(nloglogn) time, where n is the number of blocks. In the algorithm, the BSG-rooms are assigned with integral coordinates firstly, and then a linear sorting algorithm is applied on the BSG-rooms where blocks are assigned to compute two block sequences, from which the block placement can be obtained in O(n log logn) time. As a consequence, the evaluation of the BSG is completed in O(nloglogn) time, where n is the number of blocks. The proposed algorithm is much faster than the previous graph-based O(n^2) algorithm. The experimental results demonstrate the efficiency of the algorithm.     

An Optimum Placement Search Algorithm Based on Extended Corner Block List

A non-slicing approach,Corner Block List(CBL),has been presented recently.Since CBL only can represent floorplans without empty rooms,the algorithm based on CBL cannot get the optimum placement.In this paper,an extended corner block list,ECBLλ,is proposed.It can represent non-slicing floorplan including empty rooms.Based on the optimum solution theorem of BSG(bounded-sliceline grid),it is proved that the solution space of ECBLn,where n is the number of blocks,contains the optimum block placement with the minimum area.A placement algorithm based on ECBLλ,whose solution space can be controlled by setting λ,the extending ratio,is completed.Whenλ is set as n,the algorithm based on ECBLn is the optimum placement search algorithm.Experiments show that λ has a reasonable constant range for building block layout problem,so the algorithm can translate an ECBLλ representation to its corresponding placement in O(n) time,Experimental results on MCNC benchmarks show promising performance with 7% improvement in wire length and 2% decrease in dead space over algorthms based on CBL.Meanwhile,compared with other algorithms,the proposed algorithm can get better results with less runtime.     

Leakage current estimation of CMOS circuit with stack effect

Leakage current of CMOS circuit increases dramatically with the technology scaling down and has become a critical issue of high performance system. Subthreshold, gate and reverse biased junction band-to-band tunneling (BTBT) leakages are considered three main determinants of total leakage current. Up to now, how to accurately estimate leakage current of large-scale circuits within endurable time remains unsolved, even though accurate leakage models have been widely discussed. In this paper, the authors first dip into the stack effect of CMOS technology and propose a new simple gate-level leakage current model. Then, a table-lookup based total leakage current simulator is built up according to the model. To validate the simulator, accurate leakage current is simulated at circuit level using popular simulator HSPICE for comparison. Some further studies such as maximum leakage current estimation, minimum leakage current generation and a high-level average leakage current macromodel are introduced in detail. Experiments on ISCAS85 and ISCAS89 benchmarks demonstrate that the two proposed leakage current estimation methods are very accurate and efficient.     

Asynchronous heterogeneous mechanism for hyper-distributed hyper-parallel AI processing

This paper proposes an asynchronous heterogeneous propagation approach of concurrent competitive waves for hyper-distributed hyper-parallel heuristic problem-solving.This approach is much more powerful than the synchronous homogeneous mechanisms and the asynchronous superimposition algorithms,and has universal validity and availability.The basic conception,concurrent algorithm and its properties are discussed.The theory and conclusions drawn in this paper are of essential importance for the hardware implementation of hyper-distributed hyper-parallel processing based on chaotic cellular networks.     

S-Club: an overlay-based efficient service discovery mechanism in CROWN Grid

Information service plays a key role in grid system, handles resource discovery and management process. Employing existing information service architectures suffers from poor scalability, long search response time, and large traffic overhead. In this paper, we propose a service club mechanism, called S-Club, for efficient service discovery. In S-Club, an overlay based on existing Grid Information Service (GIS) mesh network of CROWN is built, so that GISs are organized as service clubs. Each club serves for a certain type of service while each GIS may join one or more clubs. S-Club is adopted in our CROWN Grid and the performance of S-Club is evaluated by comprehensive simulations. The results show that S-Club scheme significantly improves search performance and outperforms existing approaches. Chunming Hu is a research staff in the Institute of Advanced Computing Technology at the School of Computer Science and Engineering, Beihang University, Beijing, China. He received his B.E. and M.E. in Department of Computer Science and Engineering in Beihang University. He received the Ph.D. degree in School of Computer Science and Engineering of Beihang University, Beijing, China, 2005. His research interests include peer-to-peer and grid computing; distributed systems and software architectures. Yanmin Zhu is a Ph.D. candidate in the Department of Computer Science, Hong Kong University of Science and Technology. He received his B.S. degree in computer science from Xi’an Jiaotong University, Xi’an, China, in 2002. His research interests include grid computing, peer-to-peer networking, pervasive computing and sensor networks. He is a member of the IEEE and the IEEE Computer Society. Jinpeng Huai is a Professor and Vice President of Beihang University. He serves on the Steering Committee for Advanced Computing Technology Subject, the National High-Tech Program (863) as Chief Scientist. He is a member of the Consulting Committee of the Central Government’s Information Office, and Chairman of the Expert Committee in both the National e-Government Engineering Taskforce and the National e-Government Standard office. Dr. Huai and his colleagues are leading the key projects in e-Science of the National Science Foundation of China (NSFC) and Sino-UK. He has authored over 100 papers. His research interests include middleware, peer-to-peer (P2P), grid computing, trustworthiness and security. Yunhao Liu received his B.S. degree in Automation Department from Tsinghua University, China, in 1995, and an M.A. degree in Beijing Foreign Studies University, China, in 1997, and an M.S. and a Ph.D. degree in computer science and engineering at Michigan State University in 2003 and 2004, respectively. He is now an assistant professor in the Department of Computer Science and Engineering at Hong Kong University of Science and Technology. His research interests include peer-to-peer computing, pervasive computing, distributed systems, network security, grid computing, and high-speed networking. He is a senior member of the IEEE Computer Society. Lionel M. Ni is chair professor and head of the Computer Science and Engineering Department at Hong Kong University of Science and Technology. Lionel M. Ni received the Ph.D. degree in electrical and computer engineering from Purdue University, West Lafayette, Indiana, in 1980. He was a professor of computer science and engineering at Michigan State University from 1981 to 2003, where he received the Distinguished Faculty Award in 1994. His research interests include parallel architectures, distributed systems, high-speed networks, and pervasive computing. A fellow of the IEEE and the IEEE Computer Society, he has chaired many professional conferences and has received a number of awards for authoring outstanding papers.     

Learning-based tracking of complex non-rigid motion

This paper describes a novel method for tracking complex non-rigid motions by learning the intrinsic object structure. The approach builds on and extends the studies on non-linear dimensionality reduction for object representation, object dynamics modeling and particle filter style tracking. First, the dimensionality reduction and density estimation algorithm is derived for unsupervised learning of object intrinsic representation, and the obtained non-rigid part of object state reduces even to 2-3 dimensions. Secondly the dynamical model is derived and trained based on this intrinsic representation. Thirdly the learned intrinsic object structure is integrated into a particle filter style tracker. It is shown that this intrinsic object representation has some interesting properties and based on which the newly derived dynamical model makes particle filter style tracker more robust and reliable.Extensive experiments are done on the tracking of challenging non-rigid motions such as fish twisting with selfocclusion, large inter-frame lip motion and facial expressions with global head rotation. Quantitative results are given to make comparisons between the newly proposed tracker and the existing tracker. The proposed method also has the potential to solve other type of tracking problems.     

Algebraic Conditions for Classifying the Positional Relationships Between Two Conics and Their Applications

In many fields of computer science such as computer animation, computer graphics, computer aided geometric design and robotics, it is a common problem to detect the positional relationships of several entities. Based on generalized characteristic polynomials and projective transformations, algebraic conditions are derived for detecting the various positional relationships betweeu two planar conics, namely, outer separation, exterior contact, intersection, interior contact and inclusion. Then the results are applied to detecting the positional relationships between a cylinder (or a cone) and a quadric. The criteria is very effective and easier to use than other known methods.     

Improving retrieval performance by region constraints and relevance feedback

In this paper, region features and relevance feedback are used to improve the performance of CBIR. Unlike existing region-based approaches where either individual regions are used or only simple spatial layout is modeled, the proposed approach simultaneously models both region properties and their spatial relationships in a probabilistic framework. Furthermore, the retrieval performance is improved by an adaptive filter based relevance feedback. To illustrate the performance of the proposed approach, extensive experiments have been carried out on a large heterogeneous image collection with 17,000 images, which render promising results on a wide variety of queries.     

A General Probability Formula of the Number of Location Areas＇ Boundaries Crossed by a Mobile Between Two Successive Call Arrivals

Mobility management is a challenging topic in mobile computing environment. Studying the situation of mobiles crossing the boundaries of location areas is significant for evaluating the costs and performances of various location management strategies. Hitherto, several formulae were derived to describe the probability of the number of location areas‘ boundaries crossed by a mobile. Some of them were widely used in analyzing the costs and performances of mobility management strategies. Utilizing the density evolution method of vector Markov processes, we propose a general probability formula of the number of location areas‘ boundaries crossed by a mobile between two successive calls. Fortunately, several widely-used formulae are special cases of the proposed formula.     

A Model for Slicing JAVA Programs Hierarchically

Program slicing can be effectively used to debug, test, analyze, understand and maintain objectoriented software. In this paper, a new slicing model is proposed to slice Java programs based on their inherent hierarchical feature. The main idea of hierarchical slicing is to slice programs in a stepwise way, from package level, to class level, method level, and finally up to statement level. The stepwise slicing algorithm and the related graph reachability algorithms are presented, the architecture of the Java program Analyzing TOol (JATO) based on hierarchical slicing model is provided, the applications and a small case study are also discussed.     

Data extraction from the web based on pre-defined schema

With the development of the Internet,the World Web has become an invaluable information source for most organizations,However,most documents available from the Web are in HTML form which is originally designed for document formatting with little consideration of its contents.Effectively extracting data from such documents remains a non-trivial task.In this paper,we present a schema-guided approach to extracting data from HTML pages .Under the approach,the user defines a schema specifying what to be extracted and provides sample mappings between the schema and th HTML page.The system will induce the mapping rules and generate a wrapper that takes the HTML page as input and produces the required datas in the form of XML conforming to the use-defined schema .A prototype system implementing the approach has been developed .The preliminary experiments indicate that the proposed semi-automatic approach is not only easy to use but also able to produce a wrapper that extracts required data from inputted pages with high accuracy.     

Step-coordination algorithm of traffic control based on multi-agent system

Aiming at the deficiency of conventional traffic control method, this paper proposes a new method based on multi-agent technology for traffic control. Different from many existing methods, this paper distinguishes traffic control on the basis of the agent technology from conventional traffic control method. The composition and structure of a multi-agent system （MAS） is first discussed. Then, the step-coordination strategies of intersection-agent, segment-agent, and area-agent are put forward. The advantages of the algorithm are demonstrated by a simulation study.     

ARMiner: A Data Mining Tool Based on Association Rules

In this paper,ARM iner,a data mining tool based on association rules,is introduced.Beginning with the system architecture,the characteristics and functions are discussed in details,including data transfer,concept hierarchy generalization,mining rules with negative items and the re-development of the system.An example of the tool‘s application is also shown.Finally,Some issues for future research are presented.     

Ontology-Based Semantic Cache in AOKB

When querying on a large-scale knowledge base,a major technique of improving performance is to preload knowledge to minimize the number of roundtrips to the knowledge base.In this paper,an ontology-based semantic cache is proposed for an agent and ontology-oriented knowledge base (AOKB).In AOKB,an ontology is the collection of relationships between a group of knowledge units (agents and/or other sub-ontologies).When loading some agent A,its relationships with other knowledge units are examined,and those who have a tight semantic tie with A will be preloaded at the same time,including agents and sub-ontologies in the same ontology where A is.The proloaded agents and ontologies are saved at a semantic cache located in the memory.Test results show that up to 50% reduction in running time is achieved.     

Formal Ontology: Foundation of Domain Knowledge Sharing and Reusing

Domain analysis is the activity of identifying and representing the relevant information in a domain,so that the information can be shared and reused in similar systems.But until now,no efficient approaches are available for capturing and representing the results of domain analysis and then for sharing and reusing the domain knowledge.This paper proposes an ontology-oriented approach for formalizing the domain models.The architecture for the multiple-layer structure of the domain knowledge base is also discussed.And finally,some genetic algorithm-based methods have been given for supporting the knowledge sharing and reusing.     

A new approach to fuzzy modeling and control for nonlinear dynamic systems: Neuro-fuzzy dynamic characteristic modeling and adaptive control mechanism

The study on nonlinear control system has received great interest from the international research field of automatic engineering. There are currently some alternative and complementary methods used to predict the behavior of nonlinear systems and design nonlinear control systems. Among them, characteristic modeling (CM) and fuzzy dynamic modeling are two effective methods. However, there are also some deficiencies in dealing with complex nonlinear system. In order to overcome the deficiencies, a novel intelligent modeling method is proposed by combining fuzzy dynamic modeling and characteristic modeling methods. Meanwhile, the proposed method also introduces the low-level learning power of neural network into the fuzzy logic system to implement parameters identification. This novel method is called neuro-fuzzy dynamic characteristic modeling (NFDCM). The neuro-fuzzy dynamic characteristic model based overall fuzzy control law is also discussed. Meanwhile the local adaptive controller is designed through the golden section adaptive control law and feedforward control law. In addition, the stability condition for the proposed closed-loop control system is briefly analyzed. The proposed approach has been shown to be effective via an example. Recommended by Editor Young-Hoon Joo. This work was jointly supported by National Natural Science Foundation of China under Grant 60604010, 90716021, and 90405017 and Foundation of National Laboratory of Space Intelligent Control of China under Grant SIC07010202. Xiong Luo received the Ph.D. degree from Central South University, Changsha, China, in 2004. From 2005 to 2006, he was a Postdoctoral Fellow in the Department of Computer Science and Technology at Tsinghua University. He currently works as an Associate Professor in the Department of Computer Science and Technology, University of Science and Technology Beijing. His research interests include intelligent control for spacecraft, intelligent optimization algorithms, and intelligent robot system. Zengqi Sun received the bachelor degree from Tsinghua University, Beijing, China, in 1966, and the Ph.D. degree from Chalmers University of the Technology, Gothenburg, Sweden, in 1981. He currently works as a Professor in the Department of Computer Science and Technology, Tsinghua University. His research interests include intelligent control of robotics, fuzzy neural networks, and intelligent flight control. Fuchun Sun received the Ph.D. degree from Tsinghua University, Beijing, China, in 1998. From 1998 to 2000, he was a Postdoctoral Fellow in the Department of Automation at Tsinghua University, where he is currently a Professor in the Department of Computer Science and Technology. His research interests include neural-fuzzy systems, variable structure control, networked control systems, and robotics.     

HarkMan—A Vocabulary-Independent Keyword Spotter for Spontaneons Chinese Speech

In this paper,a noverl technique adopted in HarkMan is introduced.HarkMan is a keywore-spotter designed to automatically spot the given words of a vocabulary-independent task in unconstrained Chinese telephone speech.The speaking manner and the number of keywords are not limited.This paper focuses on the novel technique which addresses acoustic modeling,keyword spotting network,search strategies,robustness,and rejection.The underlying technologies used in HarkMan given in this paper are useful not only for keyword spotting but also for continuous speech recognition.The system has achieved a figure-of-merit value over 90%.     

Adaptive filtering under minimum information divergence criterion

Traditional filtering theory is always based on optimization of the expected value of a suitably chosen function of error, such as the minimum mean-square error (MMSE) criterion, the minimum error entropy (MEE) criterion, and so on. None of those criteria could capture all the probabilistic information about the error distribution. In this work, we propose a novel approach to shape the probability density function (PDF) of the errors in adaptive filtering. As the PDF contains all the probabilistic information, the proposed approach can be used to obtain the desired variance or entropy, and is expected to be useful in the complex signal processing and learning systems. In our method, the information divergence between the actual errors and the desired errors is chosen as the cost function, which is estimated by kernel approach. Some important properties of the estimated divergence are presented. Also, for the finite impulse response (FIR) filter, a stochastic gradient algorithm is derived. Finally, simulation examples illustrate the effectiveness of this algorithm in adaptive system training. Recommended by Editorial Board member Naira Hovakimyan under the direction of Editor Jae Weon Choi. This work was supported in part by the National Natural Science Foundation of China under grants 50577037 and 60604010. Badong Chen received the B.S. and M.S. degrees in Control Theory and Engineering from Chongqing University, Chongqing, China, in 1997 and 2003, respectively, and the Ph.D. degree in Computer Science and Technology from Tsinghua University, Beijing China, in 2008. He is currently a Postdoctor of the Institute of Manufacturing Engineering, Department of Precision Instruments and Mechanology, Tsinghua University, Beijing, China. His research interests are in signal processing, adaptive control, and information theoretic aspects of control systems. Yu Zhu received the B.S. of Radio Electronics in 1983 at Beijing Normal University, and the M.S. of Computer Applications in 1993, and the Ph.D. of Mechanical Design and Theory in 2001 at China University of Mining & Technology. He is now a Professor of the Institute of Manufacturing Engineering of Department of Precision and Mechanology of Tsinghua University. His current research interests are parallel machanism and theory, two photon micro-fabrication, ultra-precision motion system and motion control. Jinchun Hu received the Ph.D. in Control Science and Engineering from Nanjing University of Science and Technology, Nanjing, China, in 1998. Since then, he has been a postdoctoral researcher in Nanjing University of Aeronautics and Astronautics in 1999 and Tsinghua University in 2002 respectively. His research interests are in flight control, aerial Robot and intelligent control. Dr. Hu is currently an Associate Professor of the Department of Computer Science and Technology of Tsinghua University, Beijing, China. Zengqi Sun received the B.S. degree from the Department of Automatic Control, Tsinghua University, Beijing, China, in 1966 and the Ph.D. degree in Control Engineering from the Chalmas University of Technology, Sweden, in 1981. He is currently a Professor of the Department of Computer Science and Technology, Tsinghua University, Beijing, China. He is the author or coauthor of more than 100 paper and eight books on control and robotics. His research interests include robotics, intelligent control, fuzzy system, neural networks, and evolutionary computation.