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.     

Practical load balancing for content requests in peer-to-peer networks

This paper studies the problem of balancing the demand for content in a peer-to-peer network across heterogeneous peer nodes that hold replicas of the content. Previous decentralized load balancing techniques in distributed systems base their decisions on periodic updates containing information about load or available capacity observed at the serving entities. We show that these techniques do not work well in the peer-to-peer context; either they do not address peer node heterogeneity, or they suffer from significant load oscillations which result in unutilized capacity. We propose a new decentralized algorithm, Max-Cap, based on the maximum inherent capacities of the replica nodes. We show that unlike previous algorithms, it is not tied to the timeliness or frequency of updates, and consequently requires significantly less update overhead. Yet, Max-Cap can handle the heterogeneity of a peer-to-peer environment without suffering from load oscillations. Mema Roussopoulos is an Assistant Professor of Computer Science on the Gordon McKay Endowment at Harvard University. Before joining Harvard, she was a Postdoctoral Fellow in the Computer Science Department at Stanford University. She received her PhD and Master’s degrees in Computer Science from Stanford, and her Bachelor’s degree in Computer Science from the University of Maryland at College Park. Her interests are in the areas of distributed systems, networking, and mobile and wireless computing. Mary Baker is a Senior Research Scientist at HP Labs. Her research interests include distributed systems, networks, mobile systems, security, and digital preservation. Before joining HP Labs she was on the faculty of the computer science department at Stanford University where she ran the MosquitoNet project. She received her PhD from the University of California at Berkeley.     

Call classification using recurrent neural networks, support vector machines and finite state automata

Our objective is spoken-language classification for helpdesk call routing using a scanning understanding and intelligent-system techniques. In particular, we examine simple recurrent networks, support-vector machines and finite-state transducers for their potential in this spoken-language-classification task and we describe an approach to classification of recorded operator-assistance telephone utterances. The main contribution of the paper is a comparison of a variety of techniques in the domain of call routing. Support-vector machines and transducers are shown to have some potential for spoken-language classification, but the performance of the neural networks indicates that a simple recurrent network performs best for helpdesk call routing. Sheila Garfield received a BSc (Hons) in computing from the University of Sunderland in 2000 where, as part of her programme of study, she completed a project associated with aphasic language processing. She received her PhD from the same university, in 2004, for a programme of work connected with hybrid intelligent systems and spoken-language processing. In her PhD thesis, she collaborated with British Telecom and suggested a novel hybrid system for call routing. Her research interests are natural language processing, hybrid systems, intelligent systems. Stefan Wermter holds the Chair in Intelligent Systems and is leading the Intelligent Systems Division at the University of Sunderland, UK. His research interests are intelligent systems, neural networks, cognitive neuroscience, hybrid systems, language processing and learning robots. He has a diploma from the University of Dortmund, Germany, an MSc from the University of Massachusetts, USA, and a PhD in habilitation from the University of Hamburg, Germany, all in Computer Science. He was a Research Scientist at Berkeley, CA, before joining the University of Sunderland. Professor Wermter has written edited, or contributed to 8 books and published about 80 articles on this research area.     

Adaptive component composition and load balancing for distributed stream processing applications

Providing real-time and QoS support to stream processing applications running on top of large-scale overlays is challenging due to the inherent heterogeneity and resource limitations of the nodes and the multiple QoS demands of the applications that must concurrently be met. In this paper we propose an integrated adaptive component composition and load balancing mechanism that (1) allows the composition of distributed stream processing applications on the fly across a large-scale system, while satisfying their QoS demands and distributing the load fairly on the resources, and (2) adapts dynamically to changes in the resource utilization or the QoS requirements of the applications. Our extensive experimental results using both simulations as well as a prototype deployment illustrate the efficiency, performance and scalability of our approach.

A metamodel for modeling system features and their refinement, constraint and interaction relationships

This paper presents a metamodel for modeling system features and relationships between features. The underlying idea of this metamodel is to employ features as first-class entities in the problem space of software and to improve the customization of software by explicitly specifying both static and dynamic dependencies between system features. In this metamodel, features are organized as hierarchy structures by the refinement relationships, static dependencies between features are specified by the constraint relationships, and dynamic dependencies between features are captured by the interaction relationships. A first-order logic based method is proposed to formalize constraints and to verify constraints and customization. This paper also presents a framework for interaction classification, and an informal mapping between interactions and constraints through constraint semantics. Hong Mei received the BSc and MSc degrees in computer science from the Nanjing University of Aeronautics and Astronautics (NUAA), China, in 1984 and 1987, respectively, and the PhD degree in computer science from the Shanghai Jiao Tong University in 1992. He is currently a professor of Computer Science at the Peking University, China. His current research interests include Software Engineering and Software Engineering Environment, Software Reuse and Software Component Technology, Distributed Object Technology, and Programming Language. He has published more than 100 technical papers. Wei Zhang received the BSc in Engineering Thermophysics and the MSc in Computer Science from the Nanjing University of Aeronautics and Astronautics (NUAA), China, in 1999 and 2002, respectively. He is currently a PhD student at the School of Electronics Engineering and Computer Science of the Peking University, China. His research interests include feature-oriented requirements modeling, feature-driven software architecture design and feature-oriented software reuse. Haiyan Zhao received both the BSc and the MSc degree in Computer Science from the Peking Univeristy, China, and the Ph.D degree in Information Engineering from the University of Tokyo, Japan. She is currently an associate professor of Computer Science at the Peking University, China. Her research interests include Software Reuse, Domain Engineering, Domain Specific Languange and Program Transformation.     

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.     

The Pneumatic Biped “Lucy” Actuated with Pleated Pneumatic Artificial Muscles

This paper reports on the bipedal robot Lucy which is actuated by pleated pneumatic artificial muscles. This novel actuator is very suitable to be used in machines which move by means of legs. Besides its high power to weight ratio the actuator has an adaptable passive behavior, meaning the stiffness of the actuator can be changed on-line. This allows to change the natural frequency of the system while controlling angular joint positions. The main control concept intended for Lucy is joint trajectory control while selecting appropriate actuator compliance characteristics in order to reduce control efforts and energy consumption which is of great importance towards the autonomy of legged robots. Presently Lucy has made her first steps with the implementation of basic control strategies.The pleated pneumatic artificial muscle and its characteristics will be discussed briefly and the design of Lucy which is made modular on mechanical as well as electronic hardware level will be described in detail. To pressurize the muscles, a lightweight valve system has been developed which will be presented together with the fundamental control aspects of a joint actuated with two antagonistically setup artificial muscles. Additionally the first experimental results will be shown and briefly discussed.Björn Verrelst (1972) Study of Mechanical Engineering at the Vrije Universiteit Brussel, graduated in 1996. Since 1998 researcher and teaching assistant at the Vrije Universiteit Brussel. The focus of his research is the use of pneumatic artificial muscles in the walking biped Lucy for dynamically balanced walking.Ronald Van Ham (1976) Study of Electro-Mechanical Engineering at the Vrije Universiteit Brussel, graduated in 1999. Since 1999 researcher and teaching assistant at the Vrije Universiteit Brussel. The focus of his research is the use of adaptable compliance of pneumatic artificial muscles in the walking biped Lucy.Bram Vanderborght (1980) Study of Mechanical Engineeringat the Vrije Universiteit Brussel, graduated in 2003. Since 2003 researcher at the Vrije Universiteit Brussel, supported by the Fund for Scientific Research Flanders (Belgium). The focus of his research is the use of adaptable compliance of pneumatic artificial muscles in the dynamically balanced biped Lucy.Frank Daerden (1966) Study of Mechanical Engineering at the Vrije Universiteit Brussel. Ph.D. in Applied Sciences, Vrije Universiteit Brussel, 1999. Research and teaching assistant at the Vrije Universiteit Brussel, 1991–1999. Doctor-Assistant at the dept. of Mechanical Engineering, Vrije Universiteit Brussel since 1999, visiting Professor since 2003.Dirk Lefeber (1956) Study of Civil Engineering at the Vrije Universiteit Brussel. Ph.D. in Applied Sciences, Vrije Universiteit Brussel, 1986. Professor at the dept. of Mechanical Engineering, head of the Multibody Mechanics Research Group, Vrije Universiteit Brussel.Jimmy Vermeulen (1973) Study of Mechanical Engineering at the Vrije Universiteit Brussel. Ph.D. in Applied Sciences, Vrije Universiteit Brussel, 2004. Research and teaching assistant at the Vrije Universiteit Brussel, 1996–2004. Post-Doctoral researcher at the dept. of Mechanical Engineering, Vrije Universiteit Brussel since 2004. The focus of his research is trajectory generation and control of dynamically balanced legged robots.     

An industrial case study in reconstructing requirements views

Requirements views, such as coverage and status views, are an important asset for monitoring and managing software development projects. We have developed a method that automates the process of reconstructing these views, and we have built a tool, ReqAnalyst, that supports this method. This paper presents an investigation as to which extent requirements views can be automatically generated in order to monitor requirements in industrial practice. The paper focuses on monitoring the requirements in test categories and test cases. In order to retrieve the necessary data, an information retrieval technique, called Latent Semantic Indexing, was used. The method was applied in an industrial study. A number of requirements views were defined and experiments were carried out with different reconstruction settings for generating these views. Finally, we explored how these views can help the developers during the software development process.

Block cipher based on reversible cellular automata

We propose a new encryption algorithm relying on reversible cellular automata (CA). The behavior complexity of CA and their parallel nature makes them interesting candidates for cryptography. The proposed algorithm belongs to the class of symmetric key systems. Marcin Seredynski: He is a Ph.D. student at University of Luxembourg and Polish Academy of Sciences. He received his M.S. in 2004 from Faculty of Electronics and Information Technology in Warsaw University of Technology. His research interests include cryptography, cellular automata, nature inspired algorithms and network security. Currently he is working on intrusion detection algorithms for ad-hoc networks. Pascal Bouvry, Ph.D.: He earned his undergraduate degree in Economical & Social Sciences and his Master degree in Computer Science with distinction (’91) from the University of Namur, Belgium. He went on to obtain his Ph.D. degree (’94) in Computer Science with great distinction at the University of Grenoble (INPG), France. His research at the IMAG laboratory focussed on Mapping and scheduling task graphs onto Distributed Memory Parallel Computers. Next, he performed post-doctoral researches on coordination languages and multi-agent evolutionary computing at CWI in Amsterdam. He gained industrial experience as manager of the technology consultant team for FICS in the banking sector (Brussels, Belgium). Next, he worked as CEO and CTO of SDC (Ho Chi Minh city, Vietnam) in the telecom, semi-conductor and space industry. After that, He moved to Montreal Canada as VP Production of Lat45 and Development Director for MetaSolv Software in the telecom industry. He is currently serving as Professor in the group of Computer Science and Communications (CSC) of the Faculty of Sciences, Technology and Communications of Luxembourg University and he is heading the Intelligent & Adaptive Systems lab. His current research interests include: ad-hoc networks & grid-computing, evolutionary algorithms and multi-agent systems.     

Capabilities of outlier detection schemes in large datasets,framework and methodologies

Outlier detection is concerned with discovering exceptional behaviors of objects. Its theoretical principle and practical implementation lay a foundation for some important applications such as credit card fraud detection, discovering criminal behaviors in e-commerce, discovering computer intrusion, etc. In this paper, we first present a unified model for several existing outlier detection schemes, and propose a compatibility theory, which establishes a framework for describing the capabilities for various outlier formulation schemes in terms of matching users'intuitions. Under this framework, we show that the density-based scheme is more powerful than the distance-based scheme when a dataset contains patterns with diverse characteristics. The density-based scheme, however, is less effective when the patterns are of comparable densities with the outliers. We then introduce a connectivity-based scheme that improves the effectiveness of the density-based scheme when a pattern itself is of similar density as an outlier. We compare density-based and connectivity-based schemes in terms of their strengths and weaknesses, and demonstrate applications with different features where each of them is more effective than the other. Finally, connectivity-based and density-based schemes are comparatively evaluated on both real-life and synthetic datasets in terms of recall, precision, rank power and implementation-free metrics. Jian Tang received an MS degree from the University of Iowa in 1983, and PhD from the Pennsylvania State University in 1988, both from the Department of Computer Science. He joined the Department of Computer Science, Memorial University of Newfoundland, Canada, in 1988, where he is currently a professor. He has visited a number of research institutions to conduct researches ranging over a variety of topics relating to theories and practices for database management and systems. His current research interests include data mining, e-commerce, XML and bioinformatics. Zhixiang Chen is an associate professor in the Computer Science Department, University of Texas-Pan American. He received his PhD in computer science from Boston University in January 1996, BS and MS degrees in software engineering from Huazhong University of Science and Technology. He also studied at the University of Illinois at Chicago. He taught at Southwest State University from Fall 1995 to September 1997, and Huazhong University of Science and Technology from 1982 to 1990. His research interests include computational learning theory, algorithms and complexity, intelligent Web search, informational retrieval, and data mining. Ada Waichee Fu received her BSc degree in computer science in the Chinese University of Hong Kong in 1983, and both MSc and PhD degrees in computer science in Simon Fraser University of Canada in 1986, 1990, respectively; worked at Bell Northern Research in Ottawa, Canada, from 1989 to 1993 on a wide-area distributed database project; joined the Chinese University of Hong Kong in 1993. Her research interests are XML data, time series databases, data mining, content-based retrieval in multimedia databases, parallel, and distributed systems. David Wai-lok Cheung received the MSc and PhD degrees in computer science from Simon Fraser University, Canada, in 1985 and 1989, respectively. He also received the BSc degree in mathematics from the Chinese University of Hong Kong. From 1989 to 1993, he was a member of Scientific Staff at Bell Northern Research, Canada. Since 1994, he has been a faculty member of the Department of Computer Science in the University of Hong Kong. He is also the Director of the Center for E-Commerce Infrastructure Development. His research interests include data mining, data warehouse, XML technology for e-commerce and bioinformatics. Dr. Cheung was the Program Committee Chairman of the Fifth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2001), Program Co-Chair of the Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2005). Dr. Cheung is a member of the ACM and the IEEE Computer Society.     

A note on consistency in asynchronous multicaches

Summary This note examines and contrasts the choice of finite versus infinite histories as the framework for analysing the behaviour of an asynchronous multicache scheme. Mike Livesey is currently a Lecturer in Computer Science at the University of St. Andrews, Scotland. His research interests are centred on distributed systems, particularly the specification and verification of distributed protocols. Dr. Livesey received a BA in mathematics from Cambridge University in 1970, an MSc in computer science from Essex University in 1973 and a PhD in computer science form St. Andrews University in 1987. He has also taught at other universities in Britain and New Zealand, and been employed by Marconi-Elliott Computer Systems Ltd.     

Interactive online learning

This paper describes a system for visual object recognition based on mobile augmented reality gear. The user can train the system to the recognition of objects online using advanced methods of interaction with mobile systems: Hand gestures and speech input control “virtual menus,” which are displayed as overlays within the camera image. Here we focus on the underlying neural recognition system, which implements the key requirement of an online trainable system—fast adaptation to novel object data. The neural three-stage architecture can be adapted in two modes: In a fast training mode (FT), only the last stage is adapted, whereas complete training (CT) rebuilds the system from scratch. Using FT, online acquired views can be added at once to the classifier, the system being operational after a delay of less than a second, though still with reduced classification performance. In parallel, a new classifier is trained (CT) and loaded to the system when ready. The text was submitted by the authors in English. Gunther Heidemann was born in 1966. He studied physics at the Universities of Karlsruhe and Münster and received his PhD (Eng.) from Bielefeld University in 1998. He is currently working within the collaborative research project “Hybrid Knowledge Representation” of the SFB 360 at Bielefeld University. His fields of research are mainly computer vision, robotics, neural networks, data mining, bonification, and hybrid systems. Holger Bekel was born in 1970. He received his BS degree from the University of Bielefeld, Germany, in 1997. In 2002 he received a diploma in Computer Science from the University of Bielefeld. He is currently pursuing a PhD program in Computer Science at the University of Bielefeld, working within the Neuroinformatics Group (AG Neuroinformatik) in the project VAMPIRE (Visual Active Memory Processes and Interactive Retrieval). His fields of research are active vision and data mining. Ingo Bax was born in 1976. He received a diploma in Computer Science from the University of Bielefeld in 2002. He is currently pursuing a PhD program in Computer Science at the Neuroinformatics Group of the University of Bielefeld, working within the VAMPIRE project. His fields of interest are cognitive computer vision and pattern recognition. Helge J. Ritter was born 1958. He studied physics and mathematics at the Universities of Bayreuth, Heidelberg and Munich. After a PhD in physics at Technical University of Munich in 1988, he visited the Laboratory of Computer Science at Helsinki University of Technology and the Beckman Institute for Advanced Science and Technology at the University of Illinois at Urbana-Champaign. Since 1990 he has headed the Neuroinformatics Group at the Faculty of Technology, Bielefeld University. His main interests are principles of neural computation and their application to building intelligent systems. In 1999, she was awarded the SEL Alcatel Research Prize, and in 2001, the Leibniz Prize of the German Research Foundation DFG.     

Efficient detection of a class of stable properties

Summary We present a general protocol for detecting whether a property holds in a distributed system, where the property is a member of a class of stable properties we call thelocally stable properties. Our protocol is based on a decentralized method for constructing a maximal subset of the local states that are mutually consistent, which in turn is based on a weakened version of vector time stamps. The structure of our protocol lends itself to refinement, and we demonstrate its utility by deriving some specialized property-detection protocols, including two previously-known protocols that are known to be efficient. Laura Sabel received the BSE degree from Princeton University in 1989 and the MS degree in Computer Science from Cornell University in 1992. She is currently a PhD student in the Department of Computer Science at Cornell University. Her research interests include fault-tolerance and distributed systems. she is the recipient of an AT&T PhD Scholarship. Keith Marzullo received his Ph.D. degree in electrical engineering from Stanford University in 1984. He is an associate professor in the Computer Science and Engineering Department at the University of California, San Diego. His research interests are in the area of fault-tolerance in both asynchronous and real-time distributed systems. He has consulted on several projects including the IBM Air Traffic Control System, and is an associate editor for IEEE Transactions on Software Engineering.This work was supported by the Defense Advanced Research Projects Agency (DoD) under NASA Ames grant number NAG 2-593, and by grants from IBM and Siemens. The views, opinions, and findings contained in this report are those of the authors and should not be construed as an official Department of Defense position, policy, or decision. An earlier version of this paper appears in theProceedings of the 5th International Workshop on Distributed Systems, October 1991, Springer-Verlag LNCS Vol. 579This author is also supported by an AT&T PhD Scholarship     

Dealing with network partitions in structured overlay networks

Structured overlay networks form a major class of peer-to-peer systems, which are touted for their abilities to scale, tolerate failures, and self-manage. Any long-lived Internet-scale distributed system is destined to face network partitions. Although the problem of network partitions and mergers is highly related to fault-tolerance and self-management in large-scale systems, it has hardly been studied in the context of structured peer-to-peer systems. These systems have mainly been studied under churn (frequent joins/failures), which as a side effect solves the problem of network partitions, as it is similar to massive node failures. Yet, the crucial aspect of network mergers has been ignored. In fact, it has been claimed that ring-based structured overlay networks, which constitute the majority of the structured overlays, are intrinsically ill-suited for merging rings. In this paper, we present an algorithm for merging multiple similar ring-based overlays when the underlying network merges. We examine the solution in dynamic conditions, showing how our solution is resilient to churn during the merger, something widely believed to be difficult or impossible. We evaluate the algorithm for various scenarios and show that even when falsely detecting a merger, the algorithm quickly terminates and does not clutter the network with many messages. The algorithm is flexible as the tradeoff between message complexity and time complexity can be adjusted by a parameter.     

Estimating the number of clusters using a windowing technique

Clustering is the process of partitioning a set of patterns into disjoint and homogeneous meaningful groups (clusters). A fundamental and unresolved issue in cluster analysis is to determine how many clusters are present in a given set of patterns. In this paper, we present the z-windows clustering algorithm, which aims to address this problem using a windowing technique. Extensive empirical tests that illustrate the efficiency and the accuracy of the propsoed method are presented. The text was submitted by the authors in English. Basilis Boutsinas. Received his diploma in Computer Engineering and Informatics in 1991 from the University of Patras, Greece. He also conducted studies in Electronics Engineering at the Technical Education Institute of Piraeus, Greece, and Pedagogics at the Pedagogical Academy of Lamia, Greece. He received his PhD on Knowledge Representation from the University of Patras in 1997. He has been an assistant professor in the Department of Business Administration at the University of Patras since 2001. His primary research interests include data mining, business intelligence, knowledge representation techniques, nonmonotonic reasoning, and parallel AI. Dimitris K. Tasoulis received his diploma in Mathematics from the University of Patras, Greece, in 2000. He attained his MSc degree in 2004 from the postgraduate course “Mathematics of Computers and Decision Making” from which he was awarded a postgraduate fellowship. Currently, he is a PhD candidate in the same course. His research activities focus on data mining, clustering, neural networks, parallel algorithms, and evolutionary computation. He is coauthor of more than ten publications. Michael N. Vrahatis is with the Department of Mathematics at the University of Patras, Greece. He received the diploma and PhD degree in Mathematics from the University of Patras in 1978 and 1982, respectively. He was a visiting research fellow at the Department of Mathematics, Cornell University (1987–1988) and a visiting professor to the INFN (Istituto Nazionale di Fisica Nucleare), Bologna, Italy (1992, 1994, and 1998); the Department of Computer Science, Katholieke Universiteit Leuven, Belgium (1999); the Department of Ocean Engineering, Design Laboratory, MIT, Cambridge, MA, USA (2000); and the Collaborative Research Center “Computational Intelligence” (SFB 531) at the Department of Computer Science, University of Dortmund, Germany (2001). He was a visiting researcher at CERN (European Organization of Nuclear Research), Geneva, Switzerland (1992) and at INRIA (Institut National de Recherche en Informatique et en Automatique), France (1998, 2003, and 2004). He is the author of more than 250 publications (more than 110 of which are published in international journals) in his research areas, including computational mathematics, optimization, neural networks, evolutionary algorithms, and artificial intelligence. His research publications have received more than 600 citations. He has been a principal investigator of several research grants from the European Union, the Hellenic Ministry of Education and Religious Affairs, and the Hellenic Ministry of Industry, Energy, and Technology. He is among the founders of the “University of Patras Artificial Intelligence Research Center” (UPAIRC), established in 1997, where currently he serves as director. He is the founder of the Computational Intelligence Laboratory (CI Lab), established in 2004 at the Department of Mathematics of University of Patras, where currently he serves as director.     

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.     

Singular value decomposition based data distortion strategy for privacy protection

Privacy-preserving is a major concern in the application of data mining techniques to datasets containing personal, sensitive, or confidential information. Data distortion is a critical component to preserve privacy in security-related data mining applications, such as in data mining-based terrorist analysis systems. We propose a sparsified Singular Value Decomposition (SVD) method for data distortion. We also put forth a few metrics to measure the difference between the distorted dataset and the original dataset and the degree of the privacy protection. Our experimental results using synthetic and real world datasets show that the sparsified SVD method works well in preserving privacy as well as maintaining utility of the datasets. Shuting Xu received her PhD in Computer Science from the University of Kentucky in 2005. Dr. Xu is presently an Assistant Professor in the Department of Computer Information Systems at the Virginia State University. Her research interests include data mining and information retrieval, database systems, parallel, and distributed computing. Jun Zhang received a PhD from The George Washington University in 1997. He is an Associate Professor of Computer Science and Director of the Laboratory for High Performance Scientific Computing & Computer Simulation and Laboratory for Computational Medical Imaging & Data Analysis at the University of Kentucky. His research interests include computational neuroinformatics, data miningand information retrieval, large scale parallel and scientific computing, numerical simulation, iterative and preconditioning techniques for large scale matrix computation. Dr. Zhang is associate editor and on the editorial boards of four international journals in computer simulation andcomputational mathematics, and is on the program committees of a few international conferences. His research work has been funded by the U.S. National Science Foundation and the Department of Energy. He is recipient of the U.S. National Science Foundation CAREER Award and several other awards. Dianwei Han received an M.E. degree from Beijing Institute of Technology, Beijing, China, in 1995. From 1995to 1998, he worked in a Hitachi company(BHH) in Beijing, China. He received an MS degree from Lamar University, USA, in 2003. He is currently a PhD student in the Department of Computer Science, University of Kentucky, USA. His research interests include data mining and information retrieval, computational medical imaging analysis, and artificial intelligence. Jie Wang received the masters degree in Industrial Automation from Beijing University of Chemical Technology in 1996. She is currently a PhD student and a member of the Laboratory for High Performance Computing and Computer Simulation in the Department of Computer Science at the University of Kentucky, USA. Her research interests include data mining and knowledge discovery, information filtering and retrieval, inter-organizational collaboration mechanism, and intelligent e-Technology.     

Ontological Semantics for Distributing Contextual Knowledge in Highly Distributed Autonomic Systems

Much recent research has focused on applying Autonomic Computing principles to achieve constrained self-management in adaptive systems, through self-monitoring and analysis, strategy planning, and self adjustment. However, in a highly distributed system, just monitoring current operation and context is a complex and largely unsolved problem domain. This difficulty is particularly evident in the areas of network management, pervasive computing, and autonomic communications. This paper presents a model for the filtered dissemination of semantically enriched knowledge over a large loosely coupled network of distributed heterogeneous autonomic agents, removing the need to bind explicitly to all of the potential sources of that knowledge. This paper presents an implementation of such a knowledge delivery service, which enables the efficient routing of distributed heterogeneous knowledge to, and only to, nodes that have expressed an interest in that knowledge. This gathered knowledge can then be used as the operational or context information needed to analyze to the system's behavior as part of an autonomic control loop. As a case study this paper focuses on contextual knowledge distribution for autonomic network management. A comparative evaluation of the performance of the knowledge delivery service is also provided. John Keeney holds a BAI degree in Computer Engineering and a PhD in Computer Science from Trinity College Dublin. His primary interests are in controlling autonomic adaptable systems, particularly when those systems are distributed. David Lewis graduated in Electronics Engineering from the University of Southampton and gained his PhD in Computer Science from University College London. His areas of interest include integrated network and service management, distributed system engineering, adaptive and autonomic systems, semantic services and pervasive computing. Declan O’Sullivan was awarded his primary degree, MSc and PhD in Computer Science from Trinity College Dublin. He has a particular interest in the issues of semantic interoperability and heterogeneous information querying within a range of areas, primarily network and service management, autonomic management, and pervasive computing.     

Adaptive neighborhood selection in peer-to-peer networks based on content similarity and reputation

To address the two most critical issues in P2P file-sharing systems: efficient information discovery and authentic data acquisition, we propose a Gnutella-like file-sharing protocol termed Adaptive Gnutella Protocol (AGP) that not only improves the querying efficiency in a P2P network but also enhances the quality of search results at the same time. The reputation scheme in the proposed AGP evaluates the credibility of peers based on their contributions to P2P services and subsequently clusters nodes together according to their reputation and shared content, essentially transforming the P2P overlay network into a topology with collaborative and reputed nodes as its core. By detecting malicious peers as well as free-riders and eventually pushing them to the edge of the overlay network, our AGP propagates search queries mainly within the core of the topology, accelerating the information discovery process. Furthermore, the clustering of nodes based on authentic and similar content in our AGP also improves the quality of search results. We have implemented the AGP with the PeerSim simulation engine and conducted thorough experiments on diverse network topologies and various mixtures of honest/dishonest nodes to demonstrate improvements in topology transformation, query efficiency, and search quality by our AGP.