Anisotropic Curvature Motion for Structure Enhancing Smoothing of 3D MR Angiography Data

We propose a novel concept of shape prior for the processing of tubular structures in 3D images. It is based on the notion of an anisotropic area energy and the corresponding geometric gradient flow. The anisotropic area functional incorporates a locally adapted template as a shape prior for tubular vessel structures consisting of elongated, ellipsoidal shape models. The gradient flow for this functional leads to an anisotropic curvature motion model, where the evolution is driven locally in direction of the considered template. The problem is formulated in a level set framework, and a stable and robust method for the identification of the local prior is presented. The resulting algorithm is able to smooth the vessels, pushing solution toward elongated cylinders with round cross sections, while bridging gaps in the underlying raw data. The implementation includes a finite-element scheme for numerical accuracy and a narrow band strategy for computational efficiency. Oliver Nemitz received his Diploma in mathematics from the university of Duisburg, Germany in 2003. Then he started to work on his Ph.D. thesis in Duisburg. Since 2005 he is continuing the work on his Ph.D. project at the Institute for Numerical Simulation at Bonn University. His Ph.D. subject is fast algorithms for image manipulation in 3d, using PDE’s, variational methods, and level set methods. Martin Rumpf received his Ph.D. in mathematics from Bonn University in 1992. He held a postdoctoral research position at Freiburg University. Between 1996 and 2001, he was an associate professor at Bonn University and from 2001 until 2004 full professor at Duisburg University. Since 2004 he is now full professor for numerical mathematics and scientific computing at Bonn University. His research interests are in numerical methods for nonlinear partial differential equations, geometric evolution problems, calculus of variations, adaptive finite element methods, image and surface processing. Tolga Tasdizen received his B.S. degree in Electrical Engineering from Bogazici University, Istanbul in 1995. He received the M.S. and Ph.D. degrees in Engineering from Brown University in 1997 and 2001. From 2001 to 2004 he was a postdoctoral research associate with the Scientific Computing and Imaging Institute at the University of Utah. Since 2004 he has been with the School of Computing at the University of Utah as a research assistant professor. He also holds an adjunct assistant professor position with the Department of Neurology and the Center for Alzheimer’s Care, Imaging and Research, and a research scientist position with the Scientific Computing and Imaging Institute at the University of Utah. Ross Whitaker received his B.S. degree in Electrical Engineering and Computer Science from Princeton University in 1986, earning Summa Cum Laude. From 1986 to 1988 he worked for the Boston Consulting Group, entering the University of North Carolina at Chapel Hill in 1989. At UNC he received the Alumni Scholarship Award, and completed his Ph.D. in Computer Science in 1994. From 1994–1996 he worked at the European Computer-Industry Research Centre in Munich Germany as a research scientist in the User Interaction and Visualization Group. From 1996–2000 he was an Assistant Professor in the Department of Electrical Engineering at the University of Tennessee. He is now an Associate Professor at the University of Utah in the College of Computing and the Scientific Computing and Imaging Institute.     

Mining partial periodic correlations in time series

Recently, periodic pattern mining from time series data has been studied extensively. However, an interesting type of periodic pattern, called partial periodic (PP) correlation in this paper, has not been investigated. An example of PP correlation is that power consumption is high either on Monday or Tuesday but not on both days. In general, a PP correlation is a set of offsets within a particular period such that the data at these offsets are correlated with a certain user-desired strength. In the above example, the period is a week (7 days), and each day of the week is an offset of the period. PP correlations can provide insightful knowledge about the time series and can be used for predicting future values. This paper introduces an algorithm to mine time series for PP correlations based on the principal component analysis (PCA) method. Specifically, given a period, the algorithm maps the time series data to data points in a multidimensional space, where the dimensions correspond to the offsets within the period. A PP correlation is then equivalent to correlation of data when projected to a subset of the dimensions. The algorithm discovers, with one sequential scan of data, all those PP correlations (called minimum PP correlations) that are not unions of some other PP correlations. Experiments using both real and synthetic data sets show that the PCA-based algorithm is highly efficient and effective in finding the minimum PP correlations. Zhen He is a lecturer in the Department of Computer Science at La Trobe University. His main research areas are database systems optimization, time series mining, wireless sensor networks, and XML information retrieval. Prior to joining La Trobe University, he worked as a postdoctoral research associate in the University of Vermont. He holds Bachelors, Honors and Ph.D degrees in Computer Science from the Australian National University. X. Sean Wang received his Ph.D degree in Computer Science from the University of Southern California in 1992. He is currently the Dorothean Chair Professor in Computer Science at the University of Vermont. He has published widely in the general area of databases and information security, and was a recipient of the US National Science Foundation Research Initiation and CAREER awards. His research interests include database systems, information security, data mining, and sensor data processing. Byung Suk Lee is associate professor of Computer Science at the University of Vermont. His main research areas are database systems, data modeling, and information retrieval. He held positions in industry and academia: Gold Star Electric, Bell Communications Research, Datacom Global Communications, University of St. Thomas, and currently University of Vermont. He was also a visiting professor at Dartmouth College and a participating guest at Lawrence Livermore National Laboratory. He served on international conferences as a program committee member, a publicity chair, and a special session organizer, and also on US federal funding proposal review panel. He holds a BS degree from Seoul National University, MS from Korea Advanced Institute of Science and Technology, and Ph.D from Stanford University. Alan C. H. Ling is an assistant professor at Department of Computer Science in University of Vermont. His research interests include combinatorial design theory, coding theory, sequence designs, and applications of design theory.     

A logic-based integration of active and deductive databases

A logic-based approach to the specification of active database functionality is presented which not only endows active databases with a well-defined and well-understood formal semantics, but also tightly integrates them with deductive databases. The problem of endowing deductive databases with rule-based active behaviour has been addressed in different ways. Typical approaches include accounting for active behaviour by extending the operational semantics of deductive databases, or, conversely, accounting for deductive capabilities by constraining the operational semantics of active databases. The main contribution of the paper is an alternative approach in which a class of active databases is defined whose operational semantics is naturally integrated with the operational semantics of deductive databases without either of them strictly subsuming the other. The approach is demonstrated via the formalization of the syntax and semantics of an active-rule language that can be smoothly incorporated into existing deductive databases, due to the fact that the standard formalization of deductive databases is reused, rather than altered or extended. One distinctive feature of the paper is its use of ahistory, as defined in the Kowalski-Sergot event-calculus, to define event occurrences, database states and actions on these. This has proved to be a suitable foundation for a comprehensive logical account of the concept set underpinning active databases. The paper thus contributes a logical perspective to the ongoing task of developing a formal theory of active databases. Alvaro Adolfo Antunes Fernandes, Ph.D.: He received a B.Sc. in Economics (Rio de Janeiro, 1984), an M.Sc. in Knowledge-Based Systems (Edinburgh, 1990) and a Ph.D. in Computer Science (Heriot-Watt, 1995). He worked as a Research Associate at Heriot-Watt University from December 1990 until December 1995. In January 1996 he joined the Department of Mathematical and Computing Sciences at Goldsmiths College, University of London, as a Lecturer. His current research interests include advanced data- and knowledge-base technology, logic programming, and software engineering. M. Howard Williams, Ph.D., D.Sc.: He obtained his Ph.D. in ionospheric physics and recently a D.Sc. in Computer Science. He was appointed as the first lecturer in Computer Science at Rhodes University in 1970. During the following decade he rose to Professor of Computer Science and in 1980 was appointed as Professor of Computer Science at Heriot-Watt University. From 1980 to 1988 he served as Head of Department and then as director of research until 1992. He is now head of the Database Research Group at Heriot-Watt University. His current research interests include active databases, deductive objectoriented databases, spatial databases, parallel databases and telemedicine. Norman W. Paton, Ph.D.: He received a B.Sc. in Computing Science from the University of Aberdeen in 1986. From 1986 to 1989 he worked as a Research Assistant at the University of Aberdeen, receiving a Ph. D. in 1989. From 1989 to 1995 he was a Lecturer in Computer Science at Heriot-Watt University. Since July 1995, he has been a Senior Lecturer in Department of Computer Science at the University of Manchester. His current research interests include active databases, deductive object-oriented databases, spatial databases and database interfaces.     

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.     

A New Challenge for Applying Time Series Metrics Data to Software Quality Estimation

In typical software development, a software reliability growth model (SRGM) is applied in each testing activity to determine the time to finish the testing. However, there are some cases in which the SRGM does not work correctly. That is, the SRGM sometimes mistakes quality for poor quality products. In order to tackle this problem, we focussed on the trend of time series data of software defects among successive testing phases and tried to estimate software quality using the trend. First, we investigate the characteristics of the time series data on the detected faults by observing the change of the number of detected faults. Using the rank correlation coefficient, the data are classified into four kinds of trends. Next, with the intention of estimating software quality, we investigate the relationship between the trends of the time series data and software quality. Here, software quality is defined by the number of faults detected during six months after shipment. Finally, we find a relationship between the trends and metrics data collected in the software design phase. Using logistic regression, we statistically show that two review metrics in the design and coding phase can determine the trend. Sousuke Amasakireceived the B.E. degree in Information and Computer Sciences from Okayama Prefectural University, Japan, in 2000 and the M.E. degree in Information and Computer Sciences from Graduate School of Information Science and Technology, Osaka University, Japan, in 2003. He has been in Ph.D. course of Graduate School of Information Science and Technology at Osaka University. His interests include the software process and the software quality assurance technique. He is a student member of IEEE and ACM. Takashi Yoshitomireceived the B.E. degree in Information and Computer Sciences from Osaka University, Japan, in 2002. He has been working for Hitachi Software Engineering Co., Ltd. Osamu Mizunoreceived the B.E., M.E., and Ph.D. degrees in Information and Computer Sciences from Osaka University, Japan, in 1996, 1998, and 2001, respectively. He is an Assistant Professor of the Graduate School of Information Science and Technology at Osaka University. His research interests include the improvement technique of the software process and the software risk management technique. He is a member of IEEE. Yasunari Takagireceived the B.E. degree in Information and Computer Science, from Nagoya Institute of Technology, Japan, in 1985. He has been working for OMRON Corporation. He has been also in Ph.D. course of Graduate School of Information Science and Technology at Osaka University since 2002. Tohru Kikunoreceived the B.E., M.Sc., and Ph.D. degrees in Electrical Engineering from Osaka University, Japan, in 1970, 1972, and 1975, respectively. He joined Hiroshima University from 1975 to 1987. Since 1990, he has been a Professor of the Department of Information and Computer Sciences at Osaka University. His research interests include the analysis and design of fault-tolerant systems, the quantitative evaluation of software development processes, and the design of procedures for testing communication protocols. He is a member of IEEE and ACM.     

The Efficiency of Critical Slicing in Fault Localization

In software testing, developing effective debugging strategies is important to guarantee the reliability of software under testing. A heuristic technique is to cause failure and therefore expose faults. Based on this approach mutation testing has been found very useful technique in detecting faults. However, it suffers from two problems with successfully testing programs: (1) requires extensive computing resources and (2) puts heavy demand on human resources. Later, empirical observations suggest that critical slicing based on Statement Deletion (Sdl) mutation operator has been found the most effective technique in reducing effort and the required computing resources in locating the program faults. The second problem of mutation testing may be solved by automating the program testing with the help of software tools. Our study focuses on determining the effectiveness of the critical slicing technique with the help of the Mothra Mutation Testing System in detecting program faults. This paper presents the results showing the performance of Mothra Mutation Testing System through conducting critical slicing testing on a selected suite of programs. Zuhoor Abdullah Al-Khanjari is an assistant professor in the Computer Science Department at Sultan Qaboos University, Sultanate of Oman. She received her BSc in mathematics and computing from Sultan Qaboos University, MSc and PhD in Computer Science (Software Engineering) from the University of Liverpool, UK. Her research interests include software testing, database management, e-learning, human-computer interaction, programming languages, intelligent search engines, and web data mining and development. ~Currently, she is the coordinator of the software engineering research group in the Department of Computer Science, College of Science, Sultan Qaboos University. She is also coordinating a program to develop e-learning based undergraduate teaching in the Department of Computer Science. Currently she is holding the position of assistant dean for postgraduate studies and research in the College of Science, Sultan Qaboos University, Sultanate of Oman. Martin Woodward is a Senior Fellow in the Computer Science Department at the University of Liverpool in the UK. After obtaining BSc and Ph.D. degrees in mathematics from the University of Nottingham, he was employed by the University of Oxford as a Research Assistant on secondment to the UK Atomic Energy Authority at the Culham Laboratory. He has been at the University of Liverpool for many years and initially worked on the so-called ‘Testbed’ project, helping to develop automated tools for software testing which are now marketed successfully by a commercial organisation. His research interests include software testing techniques, the relationship between formal methods and testing, and software visualisation. He has served as Editor of the journal ‘Software Testing, Verification and Reliability’ for the past thirteen years. Haider Ramadhan is an associate professor in the Computer Science Department at Sultan Qaboos University. He received his BS and MS in Computer Science from University of North Carolina, and the PhD in Computer Science and AI from Sussex University. His research interests include visualization of software, systems, and process, system engineering, human-computer interaction, intelligent search engines, and Web data mining and development. Currently, he is the chairman of the Computer Science Department, College of Science, Sultan Qaboos University, Sultanate of Oman. Swamy Kutti (N. S. Kutti) is an associate professor in the Computer Science Department at Sultan Qaboos University. He received his B.E. in Electronics Engineering from the University of Madras, M.E. in Communication Engineering from Indian Institute of Science (Bangalore), and the MSc in Computer Science from Monash University (Australia) and PhD in Computer Science from Deakin University (Australia). His research interests include Real-Time Programming, Programming Languages, Program Testing and Verification, eLearning, and Distributed Operating Systems.     

Achieving dynamic, multi-commander, multi-mission planning and execution

The Multi-Agent Distributed Goal Satisfaction (MADGS) system facilitates distributed mission planning and execution in complex dynamic environments with a focus on distributed goal planning and satisfaction and mixed-initiative interactions with the human user. By understanding the fundamental technical challenges faced by our commanders on and off the battlefield, we can help ease the burden of decision-making. MADGS lays the foundations for retrieving, analyzing, synthesizing, and disseminating information to commanders. In this paper, we present an overview of the MADGS architecture and discuss the key components that formed our initial prototype and testbed. Eugene Santos, Jr. received the B.S. degree in mathematics and Computer science and the M.S. degree in mathematics (specializing in numerical analysis) from Youngstown State University, Youngstown, OH, in 1985 and 1986, respectively, and the Sc.M. and Ph.D. degrees in computer science from Brown University, Providence, RI, in 1988 and 1992, respectively. He is currently a Professor of Engineering at the Thayer School of Engineering, Dartmouth College, Hanover, NH, and Director of the Distributed Information and Intelligence Analysis Group (DI²AG). Previously, he was faculty at the Air Force Institute of Technology, Wright-Patterson AFB and the University of Connecticut, Storrs, CT. He has over 130 refereed technical publications and specializes in modern statistical and probabilistic methods with applications to intelligent systems, multi-agent systems, uncertain reasoning, planning and optimization, and decision science. Most recently, he has pioneered new research on user and adversarial behavioral modeling. He is an Associate Editor for the IEEE Transactions on Systems, Man, and Cybernetics: Part B and the International Journal of Image and Graphics. Scott DeLoach is currently an Associate Professor in the Department of Computing and Information Sciences at Kansas State University. His current research interests include autonomous cooperative robotics, adaptive multiagent systems, and agent-oriented software engineering. Prior to coming to Kansas State, Dr. DeLoach spent 20 years in the US Air Force, with his last assignment being as an Assistant Professor of Computer Science and Engineering at the Air Force Institute of Technology. Dr. DeLoach received his BS in Computer Engineering from Iowa State University in 1982 and his MS and PhD in Computer Engineering from the Air Force Institute of Technology in 1987 and 1996. Michael T. Cox is a senior scientist in the Intelligent Distributing Computing Department of BBN Technologies, Cambridge, MA. Previous to this position, Dr. Cox was an assistant professor in the Department of Computer Science & Engineering at Wright State University, Dayton, Ohio, where he was the director of Wright State’s Collaboration and Cognition Laboratory. He received his Ph.D. in Computer Science from the Georgia Institute of Technology, Atlanta, in 1996 and his undergraduate from the same in 1986. From 1996 to 1998, he was a postdoctoral fellow in the Computer Science Department at Carnegie Mellon University in Pittsburgh working on the PRODIGY project. His research interests include case-based reasoning, collaborative mixed-initiative planning, intelligent agents, understanding (situation assessment), introspection, and learning. More specifically, he is interested in how goals interact with and influence these broader cognitive processes. His approach to research follows both artificial intelligence and cognitive science directions.     

Atomicm-register operations

Summary We investigate systems where it is possible to access several shared registers in one atomic step. We characterize those systems in which the consensus problem can be solved in the presence of faults and give bounds on the space required. We also describe a fast solution to the mutual exclusion problem using atomicm-register operations. Michael Merritt received a B.S. degree in Philosophy and in Computer Science from Yale College in 1978, the M.S. and Ph. D. degrees in Information and Computer Science in 1980 and 1983, respectively, from the Georgia Institute of Technology. Since 1983 he has been a member of technical staff at AT&T Bell Laboratories, and has taught as an adjunct or visiting lecturer at Stevens Institute of Technology and Columbia University. In 1989 he was program chair for the ACM Symposium on Principles of Distributed Computing. His research interests include distributed and concurrent computation, both algorithms and formal methods for verifying their correctness, cryptography, and security. He is an editor for Distributed Computing and for Information and Computation, recently coauthored a book on database concurrency control algorithms, and is a member of the ACM and of Computer Professionals for Social Responsibility. Gadi Taubenfeld received the B.A., M.Sc. and Ph.D. degrees in Computer Science from the Technion (Israel Institute of Technology), in 1982, 1984 and 1988, respectively. From 1988 to 1990 he was a research scientist at Yale University. Since 1991 he has been a member of technical staff at AT&T Bell Laboratories. His primary research interests are in concurrent and distributed computing.A preliminary version of this workappeared in theProceedings of the Fifth International Workshop on Distributed Algorithms, Delphi, Greece, October 1991, pp 289–294     

Test minimization for human-computer interaction

This paper introduces a model-based approach for minimization of test sets to validate the interaction of human-computer systems. The novelty of the approach is twofold: (i) Test cases generated and selected holistically cover both the behavioral model and the complementary, fault model of the system under test (SUT). (ii) Methods known from state-based conformance testing and graph theory are extended to construct efficient, heuristic search-based algorithms for minimizing the test sets that are constructed in step (i), considering also structural features. Experience shows that the approach can help to considerably save test costs, up to 60% Fevzi Belli received the M.S., Ph.D., and Habilitation degrees in electrical engineering and computer science from the Berlin Technical University. He is presently a Professor of Software Engineering in the Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, Paderborn, Germany. Prior to this, he headed several projects at a software house in Munich, was a Professor of Computing Science at the Hochschule Bremerhaven and a faculty member of the University of Maryland, European Division. He chaired several international conferences, e.g., ISSRE 1998 and is author and co-author of more than 100 papers published in scientific journals and conference proceedings. His research interests are in testing/fault tolerance/reliability of software and programming techniques. Christof J. Budnik received the MS degree in electrical engineering and computer science in 2001 from the University of Paderborn. In 2002, he joined the Department of Computer Science, Electrical Engineering and Mathematics at the same University where he is currently a faculty member. His research interests are in the areas of software quality, testing of interactive systems and safety-critical user interfaces.     

Information access in multimedia databases based on feature models

With the increasing popularity of the WWW, the main challenge in computer science has become content-based retrieval of multimedia objects. Access to multimedia objects in databases has long been limited to the information provided in manually assigned keywords. Now, with the integration of feature-detection algorithms in database systems software, content-based retrieval can be fully integrated with query processing. We describe our experimentation platform under development, making database technology available to multimedia. Our approach is based on the new notion of feature databases. Its architecture fully integrates traditional query processing and content-based retrieval techniques. Arjen P. de Vries, Ph.D.: He received his Ph.D. in Computer Science from the University of Twente in 1999, on the integration of content management in database systems. He is especially interested in the new requirements on the design of database systems to support content-based retrieval in multimedia digital libraries. He has continued to work on multimedia database systems as a postdoc at the CWI in Amsterdam as well as University of Twente. Menzo Windhouwer: He received his MSc in Computer Science and Management from the University of Amsterdam in 1997. Currently he is working in the CWI Database Research Group on his Ph.D., which is concerned with multimedia indexing and retrieval using feature grammars. Peter M.G. Apers, Ph.D.: He is a full professor in the area of databases at the University of Twente, the Netherlands. He obtained his MSc and Ph.D. at the Free University, Amsterdam, and has been a visiting researcher at the University of California, Santa Cruz and Stanford University. His research interests are query optimization in parallel and distributed database systems to support new application domains, such as multimedia applications and WWW. He has served on the program committees of major database conferences: VLDB, SIGMOD, ICDE, EDBT. In 1996 he was the chairman of the EDBT PC. In 2001 he will, for the second time, be the chairman of the European PC of the VLDB. Currently he is coordinating Editor-in-Chief of the VLDB Journal, editor of Data & Knowledge Engineering, and editor of Distributed and Parallel Databases. Martin Kersten, Ph.D.: He received his PhD in Computer Science from the Vrije Universiteit in 1985 on research in database security, whereafter he moved to CWI to establish the Database Research Group. Since 1994 he is professor at the University of Amsterdam. Currently he is heading a department involving 60 researchers in areas covering BDMS architectures, datamining, multimedia information systems, and quantum computing. In 1995 he co-founded Data Distilleries, specialized in data mining technology, and became a non-executive board member of the software company Consultdata Nederland. He has published ca. 130 scientific papers and is member of the editorial board of VLDB journal and Parallel and Distributed Systems. He acts as a reviewer for ESPRIT projects and is a trustee of the VLDB Endowment board.     

Knowledge in shared memory systems

Summary We study the relation between knowledge and space. That is, we analyze how much shared memory space is needed in order to learn certain kinds of facts. Such results are useful tools for reasoning about shared memory systems. In addition we generalize a known impossibility result, and show that results about how knowledge can be gained and lost in message passing systems also hold for shared memory systems. Michael Merritt received a B.S. degree in Philosophy and in Computer Science from Yale College in 1978, the M.S. and Ph.D. degrees in Information and Computer Science in 1980 and 1983, respectively, from the Georgia Institute of Technology. Since 1983 he has been a member of technical staff at AT & T Bell Laboratories, and has taught as an adjunct or visiting lecturer at Stevens Institute of Technology, Massachusetts Institute of Technology, and Columbia University. In 1989 he was program chair for the ACM Symposium on Principles of Distributed Computing. His research interests include distributed and concurrent computation, both algorithms and formal methods for verifying their correctness, cryptography, and security. He is an editor for Distributed Computing and for Information and Computation, recently co-authored a book on database concurrency control algorithms, and is a member of the ACM and of Computer Professionals for Social Responsibility. Gadi Taubenfeld received the B.A., M.Sc. and Ph.D. degrees in Computer Science from the Technion (Israel Institute of Technology), in 1982, 1984 and 1988, respectively. From 1988 to 1990 he was a research scientist at Yale University. Since 1991 he has been a member of technical staff at AT & T Bell Laboratories. His primary research interests are in concurrent and distributed computing.A preliminary version of this work appeared in the Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, pages 189–200, Montreal, Canada, August 1991     

Dual-coding representations for robot vision programming in Tekkotsu

We describe complementary iconic and symbolic representations for parsing the visual world. The iconic pixmap representation is operated on by an extensible set of “visual routines” (Ullman, 1984; Forbus et al., 2001). A symbolic representation, in terms of lines, ellipses, blobs, etc., is extracted from the iconic encoding, manipulated algebraically, and re-rendered iconically. The two representations are therefore duals, and iconic operations can be freely intermixed with symbolic ones. The dual-coding approach offers robot programmers a versatile collection of primitives from which to construct application-specific vision software. We describe some sample applications implemented on the Sony AIBO. David S. Touretzky is a Research Professor in the Computer Science Department and the Center for the Neural Basis of Cognition at Carnegie Mellon University. He earned his B.A. in Computer Science from Rutgers University in 1978, and his M.S. (1979) and Ph.D. (1984) in Computer Science from Carnegie Mellon. Dr. Touretzky’s research interests are in computational neuroscience, particularly representations of space in the rodent hippocampus and related structures, and high level primitives for robot programming. He is presently developing an undergraduate curriculum in cognitive robotics based on the Tekkotsu software framework described in this article. Neil S. Halelamien earned a B.S. in Computer Science and a B.S. in Cognitive Science at Carnegie Mellon University in 2004, and is currently pursuing his Ph.D. in the Computation & Neural Systems program at the California Institute of Technology. His research interests are in studying vision from both a computational and biological perspective. He is currently using transcranial magnetic stimulation to study visual representations and information processing in visual cortex. Ethan J. Tira-Thompson is a graduate student in the Robotics Institute at Carnegie Mellon University. He earned a B.S. in Computer Science and a B.S. in Human-Computer Interaction in 2002, and an M.S. in Robotics in 2004, at Carnegie Mellon. He is interested in a wide variety of computer science topics, including machine learning, computer vision, software architecture, and interface design. Ethan’s research has revolved around the creation of the Tekkotsu framework to enable the rapid development of robotics software and its use in education. He intends to specialize in mobile manipulation and motion planning for the completion of his degree. Jordan J. Wales is completing a Master of Studies in Theology at the University of Notre Dame. He earned a B.S. in Engineering (Swarthmore College, 2001), an M.Sc. in Cognitive Science (Edinburgh, UK, 2002), and a Postgraduate Diploma in Theology (Oxford, UK, 2003). After a year as a graduate research assistant in Computer Science at Carnegie Mellon, he entered the master’s program in Theology at Notre Dame and is now applying to doctoral programs. His research focus in early and medieval Christianity is accompanied by an interest in medieval and modern philosophies of mind and their connections with modern cognitive science. Kei Usui is a masters student in the Robotics Institute at Carnegie Mellon University. He earned his B.S. in Physics from Carnegie Mellon University in 2005. His research interests are reinforcement learning, legged locomotion, and cognitive science. He is presently working on algorithms for humanoid robots to maintain balance against unexpected external forces.     

Finite-horizon scheduling of radar dwells with online template construction

Timing constraints for radar tasks are usually specified in terms of the minimum and maximum temporal distance between successive radar dwells. We utilize the idea of feasible intervals for dealing with the temporal distance constraints. In order to increase the freedom that the scheduler can offer a high-level resource manager, we introduce a technique for nesting and interleaving dwells online while accounting for the energy constraint that radar systems need to satisfy. Further, in radar systems, the task set changes frequently and we advocate the use of finite horizon scheduling in order to avoid the pessimism inherent in schedulers that assume a task will execute forever. The combination of feasible intervals and online dwell packing allows modular schedule updates whereby portions of a schedule can be altered without affecting the entire schedule, hence reducing the complexity of the scheduler. Through extensive simulations we validate our claims of providing greater scheduling flexibility without compromising on performance when compared with earlier work based on templates constructed offline. We also evaluate the impact of two parameters in our scheduling approach: the template length (or the extent of dwell nesting and interleaving) and the length of the finite horizon. Sathish Gopalakrishnan is a visting scholar in the Department of Computer Science, University of Illinois at Urbana-Champaign, where he defended his Ph.D. thesis in December 2005. He received an M.S. in Applied Mathematics from the University of Illinois in 2004 and a B.E. in Computer Science and Engineering from the University of Madras in 1999. Sathish’s research interests concern real-time and embedded systems, and the design of large-scale reliable systems. He received the best student paper award for his work on radar dwell scheduling at the Real-Time Systems Symposium 2004. Marco Caccamo graduated in computer engineering from the University of Pisa in 1997 and received the Ph.D. degree in computer engineering from the Scuola Superiore S. Anna in 2002. He is an Assistant Professor of the Department of Computer Science at the University of Illinois. His research interests include real-time operating systems, real-time scheduling and resource management, wireless sensor networks, and quality of service control in next generation digital infrastructures. He is recipient of the NSF CAREER Award (2003). He is a member of ACM and IEEE. Chi-Sheng Shih is currently an assistant professor at the Graduate Institute of Networking and Multimedia and Department of Computer Science and Information Engineering at National Taiwan University since February 2004. He received the B.S. in Engineering Science and M.S. in Computer Science from National Cheng Kung University in 1993 and 1995, respectively. In 2003, he received his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign. His main research interests are embedded systems, hardware/software codesign, real-time systems, and database systems. Specifically, his main research interests focus on real-time operating systems, real-time scheduling theory, embedded software, and software/hardware co-design for system-on-a-chip. Chang-Gun Lee received the B.S., M.S. and Ph.D. degrees in computer engineering from Seoul National University, Korea, in 1991, 1993 and 1998, respectively. He is currently an Assistant Professor in the Department of Electrical Engineering, Ohio State University, Columbus. Previously, he was a Research Scientist in the Department of Computer Science, University of Illinois at Urbana-Champaign from March 2000 to July 2002 and a Research Engineer in the Advanced Telecomm. Research Lab., LG Information & Communications, Ltd. from March 1998 to February 2000. His current research interests include real-time systems, complex embedded systems, QoS management, and wireless ad-hoc networks. Chang-Gun Lee is a member of the IEEE Computer Society. Lui Sha graduated with the Ph.D. degree from Carnegie-Mellon University in 1985. He was a Member and then a Senior Member of Technical Staff at Software Engineering Institute (SEI) from 1986 to 1998. Since Fall 1998, he has been a Professor of Computer Science at the University of Illinois at Urbana Champaign, and a Visiting Scientist of the SEI. He was the Chair of IEEE Real Time Systems Technical Committee from 1999 to 2000, and has served on its Executive Committee since 2001. He was a member of National Academy of Science’s study group on Software Dependability and Certification from 2004 to 2005, and is an IEEE Distinguished Visitor (2005 to 2007). Lui Sha is a Fellow of the IEEE and the ACM.     

Applying and combining three different aspect Mining Techniques

Understanding a software system at source-code level requires understanding the different concerns that it addresses, which in turn requires a way to identify these concerns in the source code. Whereas some concerns are explicitly represented by program entities (like classes, methods and variables) and thus are easy to identify, crosscutting concerns are not captured by a single program entity but are scattered over many program entities and are tangled with the other concerns. Because of their crosscutting nature, such crosscutting concerns are difficult to identify, and reduce the understandability of the system as a whole. In this paper, we report on a combined experiment in which we try to identify crosscutting concerns in the JHotDraw framework automatically. We first apply three independently developed aspect mining techniques to JHotDraw and evaluate and compare their results. Based on this analysis, we present three interesting combinations of these three techniques, and show how these combinations provide a more complete coverage of the detected concerns as compared to the original techniques individually. Our results are a first step towards improving the understandability of a system that contains crosscutting concerns, and can be used as a basis for refactoring the identified crosscutting concerns into aspects. M. Ceccato is a PhD student in ITC-irst in Trento, Italy. He received his degree in Software Engineering from the University of Padova, Italy, in 2003. The master thesis concerned the Re-engineering of an existing big-sized data warehouse application. The project was developed in the Information Technology department in Alcoa Servizi. His research interests are on source code analysis and manipulation, especially for the the migration of object-oriented code to aspect-oriented programming. He collaborates with King’s College London and Loyola College in Maryland on the automatic support for this migration process. He has been involved in the organization and in the program committee of a number of AOP-related events, such as Late Workshop, in Chicago (2005) and in Bonn, Germany (2006), held within the major Aspect Oriented Programming conference (AOSD) and 3rd European Workshop on Aspects in Software (EWAS’06) in Enschede, The Netherlands. Marius Marin is a Ph.D. researcher in the Software Evolution Reseach Laboratory at Delft University of Technology, the Netherlands. He was granted an engineering degree by the Technical University of Civil Engineering, Bucharest, in 2000, and Licentiate in Economic Computer Science from the Academy of Economic Studies, Bucharest, in 2002. Before starting his Ph.D. studies, he worked as a software engineer in industry. His main research interests are in the area of reverse engineering, software modularization and modeling, and aspect-oriented software development. He is the main author of the publicly available aspect mining tool FINT and he publishes at international conferences in the aforementioned topics. He has been involved in program- and organizing committees of several workshops related to aspect mining. Kim Mens obtained his Ph.D. in Computer Science at the Vrije Universiteit Brussel, on “architectural conformance checking,” for which he used a declarative meta-programming approach. After his Ph.D. he became a full-time professor (chargé de cours) at the Université catholique de Louvain-la-Neuve (UCL). In addition to his current interest in logic meta-programming and intensional views, Kim Mens is one of the originators of the reuse contracts technique for automatically detecting conflicts in evolving software. He has been formally involved in several research networks related to software evolution. He has a strong interest in object-oriented and aspect-oriented software development and has actively participated in the organization of several workshops and conferences on those topics. He combines all these different research interests under the common denominator of co-evolution (between source code and earlier life-cycle software artifacts). Other research topics that fit this common theme and in which he is interested are software architecture, software maintenance, reverse engineering, software transformation, software restructuring and renovation, aspect mining and evolution of aspect programs. L. Moonen is an assistant professor in the Software Evolution Research Lab at Delft University of Technology and a researcher at the Centre for Mathematics and Computer Science (CWI), the Netherlands. His research interests are the design and development of advanced program analysis tools and techniques that support development, maintenance and evolution of large software systems. Concrete topics include the reverse engineering and exploration of views on software systems and their use for understanding and assessing software quality attributes such as evolvability, reliability and security. Dr. Moonen received an MSc (cum laude, Computer Science, 1996) and PhD (Computer Science, 2002) from the University of Amsterdam. He is one of the founders of the Software Improvement Group, a company that specializes in tools and consultancy to help organizations solve their legacy problems. He publishes regularly at, and serves on organizing-, steering- and program committees of, international workshops and conferences on reverse engineering (WCRE), source code analysis (SCAM), software maintenance (ICSM), program understanding (ICPC), reengineering (CSMR), aspect mining (Dagstuhl 06302, TEAM) and software security (CoBaSSA). Paolo Tonella is a senior researcher at ITC-irst, Trento, Italy. He received his laurea degree cum laude in Electronic Engineering from the University of Padova, Italy, in 1992, and his Ph.D. degree in Software Engineering from the same University, in 1999, with the thesis “Code Analysis in Support to Software Maintenance.” Since 1994 he has been a full time researcher of the Software Engineering group at ITC-irst. He participated in several industrial and European Community projects on software analysis and testing. He is the author of “Reverse Engineering of Object Oriented Code,” Springer, 2005. His current research interests include reverse engineering, aspect oriented programming, empirical studies, Web applications and testing. Tom Tourwé obtained the degree of Licentiate in Computer Science in 1997 and Ph.D. in Science in 2002 at the Vrije Universiteit Brussel. He is currently associated to the Centrum voor Wiskunde en Informatica, based in Amsterdam, The Netherlands, where he works as a post- doctoral researcher in the Ideals project. His main research interests lie in the broad area of software engineering, and include aspect-oriented software evolution and re-engineering in particular. He published several peer-reviewed articles on these topics in international journals and conferences, and organised a number of workshops on those themes.     

A fast,scalable mutual exclusion algorithm

Summary This paper is concerned with synchornization under read/write atomicity in shared memory multi-processors. We present a new algorithm forN-process mutual exclusion that requires only read and write operations and that hasO(logN) time complexity, where time is measured by counting remote memory references. The time complexity of this algorithm is better than that of all prior solutions to the mutual exclusion problem that are based upon atomic read and write instructions; in fact, the time complexity of most prior solutions is unbounded. Performance studies are presented that show that our mutual exclusion algorithm exhibits scalable performance under heavy contention. In fact, its performance rivals that of the fastest queue-based spin locks based on strong primitives such as compare-and-swap and fetch-and-add. We also present a modified version of our algorithm that generates onlyO(1) memory references in the absence of contention. Jae-Heon Yang received the B.S. and M. S. degrees in Computer Engineering from Seoul National University in 1985 and 1987, respectively, and the Ph.D. degree in Computer Science from the University of Maryland at College Park in 1994. Since June 1994, he has been an Assistant Professor of Computer Science at Mills College in Oakland, California. From 1987 to 1989, he was a junior researcher at the Korea Telecommunication Authority Research Center. His research interests include distributed computing and operating systems. James H. Anderson received the M. S. degree in Computer Science from Michigan State University in 1982, the M.S. degree in Computer Science from Purdue University in 1983, and the Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. Since August 1993, he has been an Assistant Professor of Computer Science at the University of North Carolina at Chapel Hill. Prior to joining the University of North Carolina, he was an Assistant Professor of Computer Science for three years at the University of Maryland at College Park Professor Anderson's main research interests are within the area of coneurrent and distributed computing. His current interests include wait-free algorithms, scalabde synchronization mechanisms for shared-memory systems, and object-sharing strategies for hard real-time applications.Preliminary version was presented at the Twelfth Annual ACM Symposium on Principles of Distributed Computing Ithaca, New York, August 1993 [15]. Work supported, in part, by NSF Contracts CCR-9109497 and CCR-9216421 and by the Center for Excellence in Space Data and Information Sciences (CESDIS)     

Design and analysis of the Dual-Torus Network

In this paper, we propose a new topology called theDual Torus Network (DTN) which is constructed by adding interleaved edges to a torus. The DTN has many advantages over meshes and tori such as better extendibility, smaller diameter, higher bisection width, and robust link connectivity. The most important property of the DTN is that it can be partitioned into sub-tori of different sizes. This is not possible for mesh and torus-based systems. The DTN is investigated with respect to allocation, embedding, and fault-tolerant embedding. It is shown that the sub-torus allocation problem in the DTN reduces to the sub-mesh allocation problem in the torus. With respect to embedding, it is shown that a topology that can be embedded into a mesh with dilation δ can also be embedded into the DTN with less dilation. In fault-tolerant embedding, a fault-tolerant embedding method based on rotation, column insertion, and column skip is proposed. This method can embed any rectangular grid into its optimal square DTN when the number of faulty nodes is fewer than the number of unused nodes. In conclusion, the DTN is a scalable topology well-suited for massively parallel computation. Sang-Ho Chae, M.S.: He received the B.S. in the Computer Science and Engineering from the Pohang University of Science and Technology (POSTECH) in 1994, and the M.E. in 1996. Since 1996, he works as an Associate Research Engineer in the Central R&D Center of the SK Telecom Co. Ltd. He took part in developing SK Telecom Short Message Server whose subscribers are now over 3.5 million and Advanced Paging System in which he designed and implemented high availability concepts. His research interests are the Fault Tolerance, Parallel Processing, and Parallel Topolgies. Jong Kim, Ph.D.: He received the B.S. degree in Electronic Engineering from Hanyang University, Seoul, Korea, in 1981, the M.S. degree in Computer Science from the Korea Advanced Institute of Science and Technology, Seoul, Korea, in 1983, and the Ph.D. degree in Computer Engineering from Pennsylvania State University, U.S.A., in 1991. He is currently an Associate Professor in the Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Korea. Prior to this appointment, he was a research fellow in the Real-Time Computing Laboratory of the Department of Electrical Engineering and Computer Science at the University of Michigan from 1991 to 1992. From 1983 to 1986, he was a System Engineer in the Korea Securities Computer Corporation, Seoul, Korea. His major areas of interest are Fault-Tolerant Computing, Performance Evaluation, and Parallel and Distributed Computing. Sung Je Hong, Ph.D.: He received the B.S. degree in Electronics Engineering from Seoul National University, Korea, in 1973, the M.S. degree in Computer Science from Iowa State University, Ames, U.S.A., in 1979, and the Ph.D. degree in Computer Science from the University of Illinois, Urbana, U.S.A., in 1983. He is currently a Professor in the Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Korea. From 1983 to 1989, he was a staff member of Corporate Research and Development, General Electric Company, Schenectady, NY, U.S.A. From 1975 to 1976, he was with Oriental Computer Engineering, Korea, as a Logic Design Engineer. His current research interest includes VLSI Design, CAD Algorithms, Testing, and Parallel Processing. Sunggu Lee, Ph.D.: He received the B.S.E.E. degree with highest distinction from the University of Kansas, Lawrence, in 1985 and the M.S.E. and Ph.D. degrees from the University of Michigan, Ann Arbor, in 1987 and 1990, respectively. He is currently an Associate Professor in the Department of Electronic and Electrical Engineering at the Pohang University of Science and Technology (POSTECH), Pohang, Korea. Prior to this appointment, he was an Associate Professor in the Department of Electrical Engineering at the University of Delaware in Newark, Delaware, U.S.A. From June 1997 to July 1998, he spent one year as a Visiting Scientist at the IBM T. J. Watson Research Center. His research interests are in Parallel, Distributed, and Fault-Tolerant Computing. Currently, his main research focus is on the high-level and low-level aspects of Inter-Processor Communications for Parallel Computers.     

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.     

Discovering user profiles for Web personalized recommendation

With the growing popularity of the World Wide Web, large volume of user access data has been gathered automatically by Web servers and stored in Web logs. Discovering and understanding user behavior patterns from log files can provide Web personalized recommendation services. In this paper, a novel clustering method is presented for log files called Clustering large Weblog based on Key Path Model (CWKPM), which is based on user browsing key path model, to get user behavior profiles. Compared with the previous Boolean model, key path model considers the major features of users‘ accessing to the Web: ordinal, contiguous and duplicate. Moreover, for clustering, it has fewer dimensions. The analysis and experiments show that CWKPM is an efficient and effective approach for clustering large and high-dimension Web logs.     

Static extensivity analysis for λ-definable functions over lattices

We employ a static analysis to examine the extensivity (∀x:x≤f(x)) of functions defined over lattices in a λ-calculus augmented with lattice operations. The need for such a verification procedure has arisen in our work on a generator system (called Zoo) of static program-analyzers. The input to Zoo is a static analysis specification that consists of lattice definitions and function definitions over the lattices. Once the extensivity of the functions is ascertained, the generated analyzer is guaranteed to terminate when the lattices have finite-heights. The extensivity analysis consists of a sound syntax-driven deductive rules whose satisfiability check is done by a constraint solving procedure. Hyunjun Eo: He is a Ph.D. candidate of Computer Science Dept. at KAIST (Korea Advanced Institute of Science and Technology). He received his B.S. and M.S. in Computer Science from KAIST in 1996 and 1998, respectively. For 1998–2003, he was a research assistant of the National Creative Research Initiative Center for Research On Program Analysis System. His research interest has been on static program analysis, program logics, and higher-order and typed languages. He is currently working on developing a tool for automatic generation of program analyzers. Kwangkeun Yi, Ph.D.: His research interest has been on semantic-based program analysis and systems application of language technologies. After his Ph.D. from University of Illinois at Urbana-Champaign he joined the Software Principles Research Department at Bell Laboratories, where he worked on various static analysis approaches for higher-order and typed programming languages. For 1995–2003, he was a faculty member in the Department of Computer Science, Korea Advanced Institute of Science and Technology. Since Fall 2003, he has been a faculty member in the School of Computer Science and Engineering, Seoul National University. Kwang-Moo Choe, Ph.D.: He is a professor of Computer Science at Korea Advanced Institute of Science and Technology. He received his B.S. from Seoul National University in 1976, and his M.S. and Ph.D. from Korea Advanced Institute of Science and Technology in 1978 and 1984, respectively. For 1985–1986, he was a technical staff of AT&T Bell Labs at Murray Hill. His research interest is formal language theory, parallel evaluation of logic programs, and optimizing compilers.     

Method of direct texture synthesis on arbitrary surfaces

A direct texture synthesis method on arbitrary surfaces is proposed in this paper. The idea is to recursively map triangles on surface to texture space until the surface is completely mapped. First, the surface is simplified and a tangential vector field is created over the simplified mesh. Then, mapping process searches for the most optimal texture coordinates in texture sample for each triangle, and the textures of neighboring triangles are blended on the mesh. All synthesized texture triangles are compressed to an atlas. Finally, the simplified mesh is subdivided to approach the initial surface. The algorithm has several advantages over former methods: it synthesizes texture on surface without local parameterization; it does not need partitioning surface to patches; and it does not need a particular texture sample. The results demonstrate that the new algorithm is applicable to a wide variety of texture samples and any triangulated surfaces.