Power Efficient Sub-Array in Reconfigurable VLSI Meshes

Given an m×n mesh-connected VLSI array with some faulty elements, the reconfiguration problem is to find a maximum-sized fault-free sub-array under the row and column rerouting scheme. This problem has already been shown to be NP-complete. In this paper, new techniques are proposed, based on heuristic strategy, to minimize the number of switches required for the power efficient sub-array. Our algorithm shows that notable improvements in the reduction of the number of long interconnects could be realized in linear time and without sacrificing on the size of the sub-array. Simulations based on several random and clustered fault scenarios clearly reveal the superiority of the proposed techniques.     

Modeling semantics in composite Web service requests by utility elicitation

When meeting the challenges in automatic and semi-automatic Web service composition, capturing the user’s service demand and preferences is as important as knowing what the services can do. This paper discusses the idea of semantic service requests for composite services, and presents a multi-attribute utility theory (MAUT) based model of composite service requests. Service requests are modeled as user preferences and constraints. Two preference structures, additive independence and generalized additive independence, are utilized in calculating the expected utilities of service composition outcomes. The model is also based on an iterative and incremental scheme meant to better capture requirements in accordance with service consumers’ needs. OWL-S markup vocabularies and associated inference mechanism are used as a means to bring semantics to service requests. Ontology conceptualizations and language constructs are added to OWL-S as uniform representations of possible aspects of the requests. This model of semantics in service requests enables unambiguous understanding of the service needs and more precise generation of the desired compositions. An application scenario is presented to illustrate how the proposed model can be applied in the real business world. Qianhui Althea Liang received her Ph.D from the Department of Electrical and Computer Engineering, University of Florida in 2004. While pursuing her Ph.D, she was a member of Database Systems Research and Development Center at the University of Florida. She received both her bachelor’s and master’s from the Department of Computer Science and Engineering, Zhejiang University, China. She joined the School of Information Systems at Singapore Management University, Singapore, as an assistant professor in 2005. Her major research interests are service composition, dynamic service discovery, multimedia Web services, and applied artificial intelligence. Jen-Yao Chung received the M.S. and Ph.D degrees in computer science from the University of Illinois at Urbana-Champaign. Currently, he is the senior manager for Engineering and Technology Services Innovation, where he was responsible for identifying and creating emergent solutions. He was Chief Technology Officer for IBM Global Electronics Industry. Before that, he was program director for IBM Institute for Advanced Commerce Technology office. He is the co-founder of IEEE technical committee on e-Commerce (TCEC). He has served as general chair and program chair for many international conferences, most recently he served as the steering committee chair for the IEEE International Conference on e-Commerce Technology (CEC06) and general chair for the IEEE International Conference on e-Business Engineering (ICEBE06). He has authored or coauthored over 150 technical papers in published journals or conference proceedings. He is a senior member of the IEEE and a member of ACM. Miller is founding Dean of the School of Information Systems (SIS) at Singapore Management University, and also serves as Practice Professor of Information Systems. Since 2003, he has led efforts to launch and establish the undergraduate, graduate and professional programs of the SIS. Immediately prior to joining SMU, Dr. Miller served as Chief Architect Executive for the Business Consulting Services unit of IBM Global Services in Asia Pacific. He held prior industry appointments with Fujitsu Network Systems, and with RWD Technologies. Dr. Miller started his professional career as an Assistant Professor at Carnegie Mellon University, conducting research and teaching related to Computer-Integrated Manufacturing and Robotics applications and impacts. He has a Bachelors of Engineering Degree in Systems Engineering (Magna Cum Laude) from the University of Pennsylvania and a Masters of Science in Statistics and a Ph.D in Engineering and Public Policy from Carnegie Mellon University.     

Asymptotic stability and disturbance attenuation properties for a class of networked control systems

In this paper, stability and disturbance attenuation issues for a class of Networked Control Systems (NCSs) under uncertain access delay and packet dropout effects are considered. Our aim is to find conditions on the delay and packet dropout rate, under which the system stability and H∞ disturbance attenuation properties are preserved to a desired level. The basic idea in this paper is to formulate such Networked Control System as a discrete-time switched system. Then the NCSs’ stability and performance problems can be reduced to the corresponding problems for switched systems, which have been studied for decades and for which a number of results are available in the literature. The techniques in this paper are based on recent progress in the discrete-time switched systems and piecewise Lyapunov functions.     

Building a Tool for Battle Planning: Challenges,Tradeoffs, and Experimental Findings

Use of knowledge-based decision aids can help alleviate the challenges of planning complex operations. We describe a knowledge-based tool capable of translating a high-level concept for a tactical military operation into a fully detailed, actionable plan, producing automatically (or with human guidance) plans with realistic degree of detail and complexity. Tight interleaving of planning, adversary estimates, scheduling, routing, attrition and consumption processes comprise the computational approach of this tool. Although originally developed for Army large-unit operations, the technology is generic and also applies to a number of other domains, particularly in critical situations requiring detailed planning within a constrained period of time. In this paper, we focus particularly on the engineering tradeoffs in the design of the tool. An experimental comparative evaluation indicated that the tool's performance compared favorably with human planners. Alexander Kott is a Program Manager at Defense Advanced Research Projects Agency (DARPA). While performing the research described in this paper, he was the Director of R&D at Carnegie Group, Inc., and a Technical Director at BBN Technologies in Pittsburgh, PA. His work included development of algorithms and decision aids for dealing with dynamic planning and scheduling in constrained, uncertain and adversarial environments, and research in dynamic distributed decision-making systems, such as in military command and control. He earned his PhD from the University of Pittsburgh where he explored the use AI techniques for innovative design of systems. He can be reached at DARPA, 3701 N Fairfax Drive, Arlington, VA, 22203. Raymond Budd is a member of the technical staff at BBN Technologies. His areas of interest include knowledge representations, knowledge engineering, and planning and scheduling. He received a BS in computer science from the University of Pittsburgh. Contact him at BBN Technologies 1300 N. 17th Street, Suite 400, Arlington, VA 22209. Larry Ground is a senior analyst with Green River Associates, Inc. His research interests include development of tools for analysis and decision support of Army maneuver and logistics planning. Retired from the US Army as a Lieutenant Colonel, he served in a variety of command and staff positions and taught at the US Army Command and General Staff College. He is a Certified Professional Logistician by the International Society of Logistics. Contact him at Green River Associates, Inc., Fredericksburg, VA. Lakshmi Rebbapragada is a senior computer engineer at US Army CECOM Research, Development and Engineering Center (RDEC). Her research interests include application of advanced technologies to tactical planning, execution-based replanning, VA Standards for Ontology based Knowledge sharing re-use, and Network Centric Infrastructure for Command and Control. She is a member of the IEEE Standard Upper Ontology (SUO) Working Group. She has a Ph.D in High Energy Physics from Bristol University U.K. She can be contacted at PM UA NSI Battle Command, Bldg. 2405, Ft. Monmouth, NJ 07703. John Langston is a senior analyst with Austin Information Systems. He served in a variety of command and staff positions in the US Army, including extensive combat experience in the Republic of Vietnam. Retired as a Lieutenant Colonel, he is widely recognized for his extensive research and knowledge in the areas of military leadership and decision making and has contributed significantly to the development of automated battle planning tools. Contact him at Austin Information Systems, Whispering Woods Cove, Parkville, MO 64152.     

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.     

Privacy preservation for data cubes

A range query finds the aggregated values over all selected cells of an online analytical processing (OLAP) data cube where the selection is specified by the ranges of contiguous values for each dimension. An important issue in reality is how to preserve the confidential information in individual data cells while still providing an accurate estimation of the original aggregated values for range queries. In this paper, we propose an effective solution, called the zero-sum method, to this problem. We derive theoretical formulas to analyse the performance of our method. Empirical experiments are also carried out by using analytical processing benchmark (APB) dataset from the OLAP Council. Various parameters, such as the privacy factor and the accuracy factor, have been considered and tested in the experiments. Finally, our experimental results show that there is a trade-off between privacy preservation and range query accuracy, and the zero-sum method has fulfilled three design goals: security, accuracy, and accessibility. Sam Y. Sung is an Associate Professor in the Department of Computer Science, School of Computing, National University of Singapore. He received a B.Sc. from the National Taiwan University in 1973, the M.Sc. and Ph.D. in computer science from the University of Minnesota in 1977 and 1983, respectively. He was with the University of Oklahoma and University of Memphis in the United States before joining the National University of Singapore. His research interests include information retrieval, data mining, pictorial databases and mobile computing. He has published more than 80 papers in various conferences and journals, including IEEE Transaction on Software Engineering, IEEE Transaction on Knowledge & Data Engineering, etc. Yao Liu received the B.E. degree in computer science and technology from Peking University in 1996 and the MS. degree from the Software Institute of the Chinese Science Academy in 1999. Currently, she is a Ph.D. candidate in the Department of Computer Science at the National University of Singapore. Her research interests include data warehousing, database security, data mining and high-speed networking. Hui Xiong received the B.E. degree in Automation from the University of Science and Technology of China, Hefei, China, in 1995, the M.S. degree in Computer Science from the National University of Singapore, Singapore, in 2000, and the Ph.D. degree in Computer Science from the University of Minnesota, Minneapolis, MN, USA, in 2005. He is currently an Assistant Professor of Computer Information Systems in the Management Science & Information Systems Department at Rutgers University, NJ, USA. His research interests include data mining, databases, and statistical computing with applications in bioinformatics, database security, and self-managing systems. He is a member of the IEEE Computer Society and the ACM. Peter A. Ng is currently the Chairperson and Professor of Computer Science at the University of Texas—Pan American. He received his Ph.D. from the University of Texas–Austin in 1974. Previously, he had served as the Vice President at the Fudan International Institute for Information Science and Technology, Shanghai, China, from 1999 to 2002, and the Executive Director for the Global e-Learning Project at the University of Nebraska at Omaha, 2000–2003. He was appointed as an Advisory Professor of Computer Science at Fudan University, Shanghai, China in 1999. His recent research focuses on document and information-based processing, retrieval and management. He has published many journal and conference articles in this area. He had served as the Editor-in-Chief for the Journal on Systems Integration (1991–2001) and as Advisory Editor for the Data and Knowledge Engineering Journal since 1989.     

A control-design-based solution to robotic ecology: Autonomy of achieving cooperative behavior from a high-level astronaut command

In this paper, we propose a cooperative control strategy for a group of robotic vehicles to achieve the specified task issued from a high-level astronaut command. The problem is mathematically formulated as designing the cooperative control for a general class of multiple-input-multiple-output (MIMO) dynamical systems in canonical form with arbitrary but finite relative degrees such that the outputs of the overall system converge to the explicitly given steady state. The proposed cooperative control for individual vehicle only need to use the sensed and communicated outputs information from its local neighboring vehicles. No fixed leader and time-invariant communication networks are assumed among vehicles. Particularly, a set of less-restrictive conditions on the connectivity of the sensor/communication networks are established, under which it is rigorously proven by using the newly found nice properties of the convergence of sequences of row stochastic matrices that the cooperative objective of the overall system can be achieved. Simulation results for a group of vehicles achieving a target and surrounding a specified object in formation are provided to support the proposed approach in this paper. Jing Wang received his B.S. degree and Ph.D. degree in control theory and control engineering, both from Central South University of Technology, China, in 1992 and 1997, respectively. He was a Postdoctoral Research Fellow at the Institute of Computing Technology, Chinese Academy of Sciences, from 1997 to 1999, and at the National University of Singapore, Singapore, from 1999 to 2002. Since March 2002, he has been with School of Electrical and Computer Science of University of Central Florida and now is a research assistant professor. He is the co-recipient of Best Theoretical Paper Award in 2002 at the 4th World Congress on Intelligent Control and Automation, Shanghai, China. His current research interests include cooperative control of multi-robot systems, nonlinear controls, robot control and motion planning, trajectory optimization, and control applications. He is a Member of IEEE and AIAA. Zhihua Qu received his Ph.D. degree in electrical engineering from the Georgia Institute of Technology in 1990. Since then, he has been with the University of Central Florida. Currently, he is a Professor in the Department of Electrical and Computer Engineering. His main research interests are nonlinear systems, robust and adaptive control designs, and robotics. He has published a number of papers in these areas and is the author of two books, Robust Control of Nonlinear Uncertain Systems by Wiley Interscience and Robust Tracking Control of Robotic Manipulators by IEEE Press. He is presently serving as an Associate Editor for Automatica and for International Journal of Robotics and Automation. He is a senior member of IEEE. Curtis M. Ihlefeld has been an electronics engineer for the National Aeronautics and Space Administration at the Kennedy Space Center since 1989. He is currently a member of the Kennedy Space Center Applied Physics Lab and has performed embedded processor systems design and control systems design for numerous Kennedy Space Center laboratories including the NASA Analytical Chemistry Lab, Optical Instrumentation Lab, Transducers Lab, and Data Acquisition Lab. Current projects include a control system design for a Lunar chemistry experiment that searches for water on the moon’s surface, a control system design and image processing tool set for space shuttle engine compartment photography, and a control system and image processing tool set for a space shuttle window defect measurement system. Presently he is performing research in the control of electroactive polymers. He holds an MS degree in electrical engineering from the University of Central Florida, and the title of his thesis was Application of Lyapunov Based Sensor Fault Detection in a Reverse Water Gas Shift Generator. He has one published conference proceedings paper and one journal article in the area of nonlinear fault tolerant control. Richard A. Hull received his B.S. in Engineering Science and Mechanics from the University of Florida, 1972, his M.S. and Ph.D. in Electrical Engineering from the University of Central Florida in 1993 and 1996, respectively. He has served as a Guidance and Control System Engineer in the Aerospace Industry for over 30 years, working for Lockheed Martin, Coleman Aerospace, McDonnell Douglas, and Boeing companies. He is currently a Principal Engineer in the Advanced Concepts Business Unit of Science Applications International Corporation (SAIC). He was a former recipient of the U.S. Air Force Laboratory Graduate Fellowship in Guidance and Control, and formerly served as Vice-Chairman of the Lockheed Martin Corporate Technical Focus Group for Guidance, Navigation and Control. His expertise and experience includes synthesis, simulation and analysis of guidance and control systems for hypersonic interceptor missiles, exo-atmospheric space vehicles, supersonic turbo-jets, space launch vehicle rockets, and high performance fighter aircraft. He is also a principal investigator for research in nonlinear robust control design methods, cooperative control of multiple platforms, and genetic algorithm design methods for aerospace applications. He has authored or co-authored over twenty conference and journal articles in the fields of nonlinear or cooperative control. He is a member of Institute of Electrical and Electronics Engineers (IEEE), a senior member of American Institute of Aeronautics and Astronautics (AIAA) and a member of the IEEE Control System Society. He has served as an Associate Editor of the Conference Editorial Board for the IEEE Control System Society since 1998, and is an adjunct professor and member of the graduate advisory council in Electrical Engineering for the Florida Institute of Technology (FIT).     

Fast agglomerative hierarchical clustering algorithm using Locality-Sensitive Hashing

The single linkage method is a fundamental agglomerative hierarchical clustering algorithm. This algorithm regards each point as a single cluster initially. In the agglomeration step, it connects a pair of clusters such that the distance between the nearest members is the shortest. This step is repeated until only one cluster remains. The single linkage method can efficiently detect clusters in arbitrary shapes. However, a drawback of this method is a large time complexity of O(n ²), where n represents the number of data points. This time complexity makes this method infeasible for large data. This paper proposes a fast approximation algorithm for the single linkage method. Our algorithm reduces the time complexity to O(nB) by rapidly finding the near clusters to be connected by Locality-Sensitive Hashing, a fast algorithm for the approximate nearest neighbor search. Here, B represents the maximum number of points going into a single hash entry and it practically diminishes to a small constant as compared to n for sufficiently large hash tables. Experimentally, we show that (1) the proposed algorithm obtains clustering results similar to those obtained by the single linkage method and (2) it runs faster for large data than the single linkage method. Hisashi Koga received the M.S. and Ph.D. degree in information science in 1995 and 2002, respectively, from the University of Tokyo. From 1995 to 2003, he worked as a researcher at Fujitsu Laboratories Ltd. Since 2003, he has been a faculty member at the University of Electro-Communications, Tokyo (Japan). Currently, he is an associate professor at the Graduate School of Information Systems, University of Electro-Communications. His research interest includes various kinds of algorithms such as clustering algorithms, on-line algorithms, and algorithms in network communications. Tetsuo Ishibashi received the M.E. degree in information systems design from the Graduate School of Information Systems at the University of Electro-Communications in 2004. Presently, he is a system engineer at Fujitsu Broad Solution & Consulting Inc. Toshinori Watanabe received the B.E. degree in aeronautical engineering in 1971 and the D.E. degree in 1985, both from the University of Tokyo. In 1971, he worked at Hitachi as a researcher in the field of information systems design. His experience includes demand forecasting, inventory and production management, VLSI design automation, knowledge-based nonlinear optimizer, and a case-based evolutionary learning system nicknamed TAMPOPO. He also engaged in FGCS (Fifth Generation Computer System) project of Japan and developed a new hierarchical message-passing parallel cooperative VLSI layout problem solver that ran on PIM (Parallel Inference Machine) in 1991. Since 1992, he has been a professor at the Graduate School of Information Systems, University of Electro-Communications, Tokyo, Japan. His areas of interest include media analysis, learning intelligence, and the semantics of information systems. He is a member of the IEEE.     

CCMPerf: A Benchmarking Tool for CORBA Component Model Implementations

Commercial off-the-shelf (COTS) middleware is now widely used to develop distributed real-time and embedded (DRE) systems. DRE systems are themselves increasingly combined to form systems of systems that have diverse quality of service (QoS) requirements. Earlier generations of COTS middleware, such as Object Request Brokers (ORBs) based on the CORBA 2.x standard, did not facilitate the separation of QoS policies from application functionality, which made it hard to configure and validate complex DRE applications. The new generation of component middleware, such as the CORBA Component Model (CCM) based on the CORBA 3.0 standard, addresses the limitations of earlier generation middleware by establishing standards for implementing, packaging, assembling, and deploying component implementations.There has been little systematic empirical study of the performance characteristics of component middleware implementations in the context of DRE systems. This paper therefore provides four contributions to the study of CCM for DRE systems. First, we describe the challenges involved in benchmarking different CCM implementations. Second, we describe key criteria for comparing different CCM implementations using key black-box and white-box metrics. Third, we describe the design of our CCMPerf benchmarking suite to illustrate test categories that evaluate aspects of CCM implementation to determine their suitability for the DRE domain. Fourth, we use CCMPerf to benchmark CIAO implementation of CCM and analyze the results. These results show that the CIAO implementation based on the more sophisticated CORBA 3.0 standard has comparable DRE performance to that of the TAO implementation based on the earlier CORBA 2.x standard.Arvind S. Krishna is a PhD student in the Electrical Engineering and Computer Science Department at Vanderbilt University and a member of the Institute for Software Integrated Systems. He received his MA in management from the Brila Institute for Technology and Science (BITS), Pilani, India and his MS in computer science from University of California, Irvine. His research interests include patterns, real-time Java technologies for Real-Time Corba, model-integrated QA techniques, and tools for partial evaluation and specialization of middleware. He is a student member of the IEEE and ACM. Contact him at the Inst. for Software Integrated Systems, 2015 Terrace Pl., Nashville, TN 37203.Balachandran Natarajan is a senior staff engineer at the Institute for Software Integrated Systems and a PhD student in electrical engineering and computer science at Vanderbilt University. His research focuses on applying patterns, optimization principles, and frameworks to build high-performance, dependable, and real-time distributed systems. He received his MS in computer science from Washington University. Contact him at the Inst. for Software Integrated Systems, 2015 Terrace Pl., Nashville, TN 37203.Aniruddha Gokhale is an assistant professor in the Electrical Engineering and Computer Science Department at Vanderbilt University and a senior research scientist at the Institute for Software Integrated Systems. His research focuses on real-time component middleware optimizations, distributed systems and networks, model-driven software synthesis applied to component middleware-based distributed systems, and distributed resource management. He received his PhD in computer science from Washington University. Contact him at the Inst. for Software Integrated Systems, 2015 Terrace Pl., Nashville, TN 37203.Douglas C. Schmidt is a professor in the Electrical Engineering and Computer Science Department at Vanderbilt University and a senior research scientist at the Institute for Software Integrated Systems. His research interests include patterns, optimization techniques, and empirical analyses of software frameworks and domain-specific modeling environments that facilitate the development of distributed real-time and embedded middleware and applications running over high-speed networks and embedded system interconnects. He received his PhD in information and computer science at the University of California, Irvine. Contact him at the Inst. for Software Integrated Systems, 2015 Terrace Pl., Nashville, TN 37203.Nanbor Wang is a Research Scientist in the Distributed Technologies Group at the Tech-X Corporation in Boulder, Colorado. He received M.S. and Ph.D. degrees in Computer Science from Washington University in St. Louis, Missouri. While working for his degree, he also worked as a Research Associate in the Center of Distributed Object Computing in the Department of Computer Science where he conducted research on design, implementation and analysis of object-oriented and component-based techniques for development of distributed systems and management of extra-functional concerns. Dr. Wangs work currently focuses on developing and applying middleware techniques, such as CORBA and Grid Computing, for enabling distributed and parallel scientific applications, such as, distributed data analysis, remote visualization and collaboration, and, work-flow management for large-scale scientific applications.Gautam H. Thaker was born in Amdavad, India, in 1955. He holds a BSEE (75) and MSEE (77) from Clemson University, Clemson, SC. He spent the 85-86 academic year at M.I.T. as a visiting researcher. His research interests include analysis, design, construction and validation of real-time, command and control systems. In particular he has focused on interactions between operating systems, networking protocols, and middleware technologies.     

BIST design for detecting multiple stuck-open faults in CMOS circuits using transition count

This paper presents a built-in self-test(BIST) scheme for detecting all robustly testable multiple stuck-open faults confined to any single complex cell of a CMOS circuit.The test pattern generator(TPG) generates all n.2^n single-input-change(SIC) orderd test pairs design is universal,i.e.,independent of the structure and functionality of the CUT.A counter that counts the number of alternate transitions at the output of the CUT,is used as a signature analyzer(SA).The design of TPG and SA is simple and no special design-or synthesis-for-testability techniques and /or additional control lines are needed.     

Node similarity in the citation graph

Published scientific articles are linked together into a graph, the citation graph, through their citations. This paper explores the notion of similarity based on connectivity alone, and proposes several algorithms to quantify it. Our metrics take advantage of the local neighborhoods of the nodes in the citation graph. Two variants of link-based similarity estimation between two nodes are described, one based on the separate local neighborhoods of the nodes, and another based on the joint local neighborhood expanded from both nodes at the same time. The algorithms are implemented and evaluated on a subgraph of the citation graph of computer science in a retrieval context. The results are compared with text-based similarity, and demonstrate the complementarity of link-based and text-based retrieval. Wangzhong Lu holds a Bachelor's degree from Hefei University of Technology (1993), and a Master's degree from Dalhousie University (2001), both in computer science. From 1993 to 1999 he worked as a developer with China National Computer Software and Technical Service Corp. in Beijing. From 2001 to 2005 he held industrial positions as a senior software architect in Atlantic Canada. He is currently with DST Systems, Charlotte, NC, as a senior data architect. Jeannette Janssen's research area is applied graph theory. She has worked on the problem of frequency assignment in cellular and digital broadcasting networks. Her current interest is in graph theory applied to the World Wide Web and other networked information spaces. Dr. Janssen did her Master's studies at Eindhoven University of Technology in the Netherlands, and her doctorate at Lehigh University, USA. She is currently an associate professor at Dalhousie University, Canada. Evangelos Milios received a diploma in electrical engineering from the National Technical University of Athens, and Master's and Ph.D. degrees in electrical engineering and computer science from the Massachusetts Institute of Technology. He held faculty positions at the University of Toronto and York University. He is currently a professor of computer science at Dalhousie University, Canada, where he was Director of the Graduate Program. He has served on the committees of the ACM Dissertation Award, and the AAAI/SIGART Doctoral Consortium. He has worked on the interpretation of visual and range signals for landmark-based positioning, navigation and map construction in single- and multi-agent robotics. His current research activity is centered on Networked Information Spaces, Web information retrieval, and aquatic robotics. He is a senior member of the IEEE. Nathalie Japkowicz is an associate professor at the School of Information Technology and Engineering of the University of Ottawa. She obtained her Ph.D. from Rutgers University, her M.Sc. from the University of Toronto, and her B.Sc. from McGill University. Prior to joining the University of Ottawa, she taught at Ohio State University and Dalhousie University. Her area of specialization is Machine Learning and her most recent research interests focused on the class imbalance problem. She made over 50 contributions in the form of journal articles, conference articles, workshop articles, magazine articles, technical reports or edited volumes. Yongzheng Zhang obtained a B.E. in computer applications from Southeast University, China, in 1997 and a M.S. in computer science from Dalhousie University in 2002. From 1997 to 1999 he was an instructor and undergraduate advisor at Southeast University. He also worked as a software engineer in Ricom Information and Telecommunications Co. Ltd., China. He is currently a Ph.D. candidate at Dalhousie University. His research interests are in the areas of Information Retrieval, Machine Learning, Natural Language Processing, and Web Mining, particularly centered on Web Document Summarization. A paper based on his Master's thesis received the best paper award at the 2003 Canadian Artificial Intelligence conference.     

Test Resource Partitioning Based on Efficient Response Compaction for Test Time and Tester Channels Reduction

This paper presents a test resource partitioning technique based on an efficient response compaction design called quotient compactor(q-Compactor). Because q-Compactor is a single-output compactor, high compaction ratios can be obtained even for chips with a small number of outputs. Some theorems for the design of q-Compactor are presented to achieve full diagnostic ability, minimize error cancellation and handle unknown bits in the outputs of the circuit under test (CUT). The q-Compactor can also be moved to the load-board, so as to compact the output response of the CUT even during functional testing. Therefore, the number of tester channels required to test the chip is significantly reduced. The experimental results on the ISCAS ‘89 benchmark circuits and an MPEG 2 decoder SoC show that the proposed compactionscheme is very efficient.     

Exploiting edge semantics in citation graphs using efficient, vertical ARM

Graphs are increasingly becoming a vital source of information within which a great deal of semantics is embedded. As the size of available graphs increases, our ability to arrive at the embedded semantics grows into a much more complicated task. One form of important hidden semantics is that which is embedded in the edges of directed graphs. Citation graphs serve as a good example in this context. This paper attempts to understand temporal aspects in publication trends through citation graphs, by identifying patterns in the subject matters of scientific publications using an efficient, vertical association rule mining model. Such patterns can (a) indicate subject-matter evolutionary history, (b) highlight subject-matter future extensions, and (c) give insights on the potential effects of current research on future research. We highlight our major differences with previous work in the areas of graph mining, citation mining, and Web-structure mining, propose an efficient vertical data representation model, introduce a new subjective interestingness measure for evaluating patterns with a special focus on those patterns that signify strong associations between properties of cited papers and citing papers, and present an efficient algorithm for the purpose of discovering rules of interest followed by a detailed experimental analysis. Imad Rahal is a newly appointed assistant professor in the Department of Computer Science at the College of Saint Benedict ∣ Saint John's University, Collegeville, MN, and a Ph.D. candidate at North Dakota State University, Fargo, ND. In August 2003, he earned his master's degree in computer science from North Dakota State University. Prior to that, he graduated summa cum laude from the Lebanese American University, Beirut, Lebanon, in February 2001 with a bachelor's degree in computer science. Currently, he is completing the final requirements for his Ph.D. degree in computer science on an NSF ND-EPSCoR doctoral dissertation assistantship with August of 2005 as a projected completion date. He is very active in research, proposal writing, and publications; his research interests are largely in the broad areas of data mining, machine learning, databases, artificial intelligence, and bioinformatics. Dongmei Ren is working for the Database Technology Institute for z/OS, IBM Silicon Valley Lab, San Jose, CA, as a staff software engineer. She holds a Ph.D. degree from North Dakota State University, Fargo, ND, and master's and bachelor's degrees from TianJin University, TianJin, China. She has been a software engineer at DaTang Telecommunications, Beijing, China. Her areas of expertise are outlier analysis, data mining and knowledge discovery, database systems, machine learning, intelligent systems, wireless networks and bioinformatics. She has been awarded the Siemens Scholarship research enhancement for excellent performance in study and research. She is a member of ACM, IEEE. Weihua Wu is a network monitoring & managed services analyst at Hewlett-Packard Co. in Canada. He holds a master's degree from North Dakota State University and a bachelor's degree from Nanjing University, both in computer science. His research areas of interest include data mining, knowledge discovery, data warehousing, information technology, network security, and bioinformatics. He has participated in various projects supported by NSF, DARPA, NASA, USDA, and GSA grants. Anne Denton is an assistant professor in computer science at North Dakota State University. Her research interests are in data mining, knowledge discovery in scientific data, and bioinformatics. Specific interests include data mining of diverse data, in which objects are characterized by a variety of properties such as numerical and categorical attributes, graphs, sequences, time-dependent attributes, and others. She received her Ph.D. in physics from the University of Mainz, Germany, and her M.S. in computer science from North Dakota State University, Fargo, ND. Christopher Besemann received his M.Sc. in computer science from North Dakota State University in Fargo, ND, 2005. Currently, he works in data mining research topics including association mining and relational data mining with recent work in model integration as a research assistant. He is accepted under a fellowship program for Ph.D. study at North Dakota State University. William Perrizo is a professor of computer science at North Dakota State University. He holds a Ph.D. degree from the University of Minnesota, a master's degree from the University of Wisconsin and a bachelor's degree from St. John's University. He has been a research scientist at the IBM Advanced Business Systems Division and the U.S. Air Force Electronic Systems Division. His areas of expertise are data mining, knowledge discovery, database systems, distributed database systems, high speed computer and communications networks, precision agriculture and bioinformatics. He is a member of ISCA, ACM, IEEE, IAAA, and AAAS.     

PRIME: A Mass Spectrum Data Mining Tool for <Emphasis Type="Italic">De Nova</Emphasis> Sequencing and PTMs Identification

De novo sequencing is one of the most promising proteomics techniques for identification of protein posttranslation modifications (PTMs) in studying protein regulations and functions. We have developed a computer tool PRIME for identification of b and y ions in tandem mass spectra, a key challenging problem in de novo sequencing. PRIME utilizes a feature that ions of the same and different types follow different mass-difference distributions to separate b from y ions correctly. We have formulated the problem as a graph partition problem. A linear integer-programming algorithm has been implemented to solve the graph partition problem rigorously and efficiently. The performance of PRIME has been demonstrated on a large amount of simulated tandem mass spectra derived from Yeast genome and its power of detecting PTMs has been tested on 216 simulated phosphopeptides.     

Variables Bounding Based Retiming Algorithm

Retiming is a technique for optimizing sequential circuits.In this paper,we discuss this problem and propose an improved retiming algorithm based on varialbes bounding.Through the computation of the lower and upper bounds on variables,the algorithm can significantly reduce the number of constratints and speed up the execution of retiming.Furthermore,the elements of matrixes D and W are computed in a demand-driven way,which can reduce the capacity of memory,It is shown through the experimental results on ISCAS89 benchmarks that our algorithm is very effective for large-scale seuqential circuits.     

Multisensor Demining Robot

The paper describes an advanced multisensor demining robot. The robot transport system is based on a simple structure using pneumatic drive elements. The robot has robust design and can carry demining equipment up to 100 kg over rough terrains. Due to the adaptive possibilities of pedipulators to obstacles, the robot can adjust the working position of the demining sensors while searching for mines. The detection block consists of a metal detector, an infrared detector, and a chemical explosive sensor. The robot is controlled by means of an on-board processor and by an operator remote station in an interactive mode. Experimental results of the transport, control, and detection systems of the robot are presented.Michael Yu. Rachkov is Professor of Automation at the Moscow State Industrial University. He graduated in Automatic Control Systems from Moscow Higher Technical School, 1979. He held academic posts at the Institute for Problems in Mechanics, Russian Academy of Sciences. In 1986 he completed his PhD in industrial robotics and received his DSc in mobile robotics in 1997. Professor Rachkov has been leading in several international projects like EUREKA and REMAPHOS. He has published over 170 papers and several books in the field of automation, robotics and optimal control. He is a member of Russian Cosmonautics Academy and International Informatization Academy.Lino Marques is a research engineer at the Institute of Systems and Robotics of the University of Coimbra. He received the Engineering and MsC. degrees in Electrical Engineering from the Faculty of Science and Technology of this University in 1992 and 1997 respectively. He is currently working toward the Ph.D. degree and teaching in the Electrical and Computer Engineering Department. His current research interests include sensors, mechatronics, mobile robotics and industrial automation.Anábal T. De Almeida graduated in Electrical Engineering, University of Porto, 1972, and received a Ph.D. in Electrical Engineering, from Imperial College, University of London, 1977. Currently he is a Professor in the Department of Electrical Engineering, University of Coimbra, and he is the Director of the Institute of Systems and Robotics since 1993. Professor De Almeida is a consultant of the European Commission Framework Programmes. He is the co-author of five books and more than one hundred papers in international journals, meetings and conferences. He has coordinated several European and national research projects.     

An enhanced force and contact position sensor for micro-manipulations

In micro-manipulations, force sensing devices play an important role in the control and the assembly of micro-objects. To protect these micro-objects from damage, we must have the ability to detect the value of the minute amount of interactive force (about a few μN) upon contact between the tip and the object. To detect this micro-force, we need an optimized design of force sensor to increase the strain values at the positions we place sensing components. Stress concentration can effectively amplify the strain values measured by the force sensors. This paper investigates the effect that the notches have on increasing the strain values at the positions we attach the sensing elements. In addition, the optimal design with a flexible structure improves the sensitivity of the sensor. An algorithm that can calculate both contact force and contact position on the sensor tip is also mentioned. Besides, an optimal location of strain gauges will ensure the accuracy and stability of the measurement. Finally, analysis and experiment are done to verify the proposed idea. Recommended by Editorial Board member Dong Hwan Kim under the direction of Editor Jae-Bok Song. This research was supported by the Ministry of Knowledge Economy and Korean Industrial Technology Foundation through the Human Resource Training Project for Strategic Technology. Tri Cong Phung received the B.S. degree in Mechanical Engineering from the HCM University of Technology, Vietnam in 2004 and the M.S. degree in Mechanical Engineering from Sungkyunkwan University in 2007. He is currently working toward a Ph.D. degree in Intelligent Robotics and Mechatronic System Laboratory (IRMS Lab), Mechanical Engineering from Sungkyunkwan University. His research interests include dexterous manipulation and touch sensors. Seung Hwa Ha received the B.S. degree in Korean University of Technology and Education, Korea in 2004. He received the M.S. degree in Mechanical Engineering from Sungkyunkwan University in 2008. He is currently working in Samsung Electronic Co. Ltd. His research interests are about strain gauge and high precision control. Yong Seok Ihn received the B.S. degree in School of Mechanical Engineering from the Sungkyunkwan University, Korea in 2006. He received the M.S. degree in Mechanical Engineering from the Sungkyunkwan University, in 2008. He is currently working toward a Ph. D. degree in the Computer Aided Modeling & Simulation Laboratory (CAMAS Lab), School of Mechanical Engineering at the Sungkyunkwan University in Korea. His research interests are precision mechatronics, dynamic system modeling, and control. Byung June Choi received the B.S. degree in School of Mechanical Engineering from the Sungkyunkwan University, Korea in 2002. He received the M.S. degree in Mechanical Engineer-ing from the Sungkyunkwan University, in 2005. He is currently working toward a Ph.D. degree in the Intelligent Robotics and Mechatronic System Laboratory (IRMS Lab), School of Mechanical Engineering at the Sungkyunkwan University in Korea. His research interests are mechanisms design, multi-robot system control, cooperation, path planning and task allocation algorithm. Sang Moo Lee was born in Seoul, Korea and educated in Seoul. He received the Ph.D. degree from the Seoul National University in Korea, in 1999. He is currently a Principal Researcher of Division for Applied Robot Technology at Korean Institute of Industrial Technology. His research interests include high-precision robot control, motion field network, and location system in outdoor environment for robots. Ja Choon Koo is an Associate Professor of School of Mechanical Engineering in Sungkyunkwan University in Korea. His major researches are in the field of design, analysis, and control of dynamics systems, especially micro precision mechatronic systems and energy transducers. He was an Advisory Engineer for IBM, San Jose, California, USA and a Staff Engineer for SISA, San Jose, CA, USA. He received the Ph.D. and M.S. degrees from the University of Texas at Austin and the B.S. from Hanyang University, Seoul, Korea. Hyouk Ryeol Choi received the B.S. degree from Seoul National University, Seoul, Korea, in 1984, the M.S. degree from Korea Advanced Institute of Science and Technology (KAIST), Daejon, Korea, in 1986, and the Ph.D. degree from Pohang University of Science and Technology (POSTECH), Pohang, Korea, in 1994, all in Mechanical Engineering. From 1986 to 1989, he was an Associate Engineer at LG Electronics Central Research Laboratory, Seoul. From 1993 to 1995, he was at Kyoto University, Kyoto, Japan, as a Grantee of scholarship from the Japanese Educational Ministry. From 2000 to 2001, he visited Advanced Institute of Industrial Science Technology (AIST), Tsukuba, Japan, as a Japan Society for the Promotion of Sciences (JSPS) Fellow. Since 1995, he has been with Sungkyunkwan University, Suwon, Korea, where he is currently a Professor in the School of Mechanical Engineering. He is an Associate Editor of the Journal of Intelligent Service Robotics and International Journal of Control, Automation and Systems (IJCAS), and IEEE Transactions on Robotics. His current research interests include dexterous mechanism, field application of robots, and artificial muscle actuators.     

Agent-based Drivers’ Information Assistance System

“Drivers’ Information Assistance System (DIA system)” is an ITS (Intelligent Transport Systems) application framework that provides agent-based information assistance to drivers through car navigation systems or on-board PCs. DIA system enables flexible information retrieval over the Internet using intelligent mobile agent, and incorporates a high-speed event delivery facility that makes real-time information service possible. The goal of the system is to provide up to the minute information and services related to driver needs, such as parking lot vacancy information. Crucial to making this a practical operation is the agent-based ability to access the network while the vehicle is in motion. Masanori Hattori: He is a research engineer in the Computer & Network Systems Laboratory, Corporate Research & Development Center, Toshiba Corporation. His research interests are network computing, human interface, and agent technologies especially in mobile agents, intelligent agents, and physical agents. He received the B.E. and M.E. from the Kyushu University. Naoki Kase: He received the M.S. in computer science from the Keio University, Japan. His research interests are mobile agent and its applications. He has developed an intelligent mobile agent system and its applications on ITS (Intelligent Transport Systems) field. Akihiko Ohsuga, Dr. Eng.: He is a senior research scientist at the Computer & Network Systems Laboratory in Toshiba Corporation. Dr. Ohsuga received a B.S. degree in mathematics from Sophia University in 1981 and a Dr. Eng. degree in electrical engineering from Waseda University in 1995. He joined Toshiba Corporation in 1981, worked with the ICOT (institute for New Generation Computer Technology) involved in the Fifth Generation Computer System project from 1985 to 1989. His research interests include agent technologies, formal specification & verification, and automated theorem proving. Shinichi Honiden, Dr.Eng.: He is a chief specialist of Government Division, Toshiba Corporation. He received the B.S., M.S., and Dr. Eng. degrees in electrical engineering from Waseda University, Tokyo, Japan, in 1976, 1978, and 1986, respectively. Since 1978, he has been with Toshiba Corporation. His research interests include software engineering and artificial intelligence. In these fields, he is the author or coauthor of ten textbooks and has published over 80 technical papers.     

A hierarchical pipelining architecture and FPGA implementation for lifting-based 2-D DWT

Numerous VLSI architectures for 2-D discrete wavelet transform (DWT) have been brought forward. While most of the designs displayed good performance through parallel processing, few of them addressed thoroughly how to sustain such high throughput computing which is crucial in real-time applications. Although the affordable data transfer bandwidth has been increased tremendously during the past decade, the pressure on data communication has not yet been relieved from stream-intensive applications. The design of 2-D DWT belongs to such cases. In this paper, we expose the performance gap between the computing core and the entire system, distinguishing them by quantitative approach with metrics of peak performance and mean-time performance. In order to narrow down the discrepancy without degrading either of the two criteria, on the one hand, we introduce a software-pipelining lifting-based computing kernel to remove data dependence for peak performance, on the other hand, we apply loop fusing technique and a hierarchical pipelining method to enhance data locality and boost the mean-time performance. The architecture has been implemented in Xilinx Virtex-II FPGA, taking advantage of Virtex-II’s embedded multipliers and block RAMs. We use Daubechies (9, 7) and LeGall (5, 3) filters (the default lossy and lossless filters in JPEG2000) for illustration whereas it is a general method for other DWT filters. The post-place and routing operation frequency for Daubechies (9, 7) is 138 MHz. Notably, the mean-time performance parameterized by image size and decomposition level achieves closely to peak performance.

---