A study of the model and algorithms for handling location-dependent continuous queries

Advances in wireless and mobile computing environments allow a mobile user to access a wide range of applications. For example, mobile users may want to retrieve data about unfamiliar places or local life styles related to their location. These queries are called location-dependent queries. Furthermore, a mobile user may be interested in getting the query results repeatedly, which is called location-dependent continuous querying. This continuous query emanating from a mobile user may retrieve information from a single-zone (single-ZQ) or from multiple neighbouring zones (multiple-ZQ). We consider the problem of handling location-dependent continuous queries with the main emphasis on reducing communication costs and making sure that the user gets correct current-query result. The key contributions of this paper include: (1) Proposing a hierarchical database framework (tree architecture and supporting continuous query algorithm) for handling location-dependent continuous queries. (2) Analysing the flexibility of this framework for handling queries related to single-ZQ or multiple-ZQ and propose intelligent selective placement of location-dependent databases. (3) Proposing an intelligent selective replication algorithm to facilitate time- and space-efficient processing of location-dependent continuous queries retrieving single-ZQ information. (4) Demonstrating, using simulation, the significance of our intelligent selective placement and selective replication model in terms of communication cost and storage constraints, considering various types of queries. Manish Gupta received his B.E. degree in Electrical Engineering from Govindram Sakseria Institute of Technology & Sciences, India, in 1997 and his M.S. degree in Computer Science from University of Texas at Dallas in 2002. He is currently working toward his Ph.D. degree in the Department of Computer Science at University of Texas at Dallas. His current research focuses on AI-based software synthesis and testing. His other research interests include mobile computing, aspect-oriented programming and model checking. Manghui Tu received a Bachelor degree of Science from Wuhan University, P.R. China, in 1996, and a Master's Degree in Computer Science from the University of Texas at Dallas 2001. He is currently working toward the Ph.D. degree in the Department of Computer Science at the University of Texas at Dallas. Mr. Tu's research interests include distributed systems, wireless communications, mobile computing, and reliability and performance analysis. His Ph.D. research work focuses on the dependent and secure data replication and placement issues in network-centric systems. Latifur R. Khan has been an Assistant Professor of Computer Science department at University of Texas at Dallas since September 2000. He received his Ph.D. and M.S. degrees in Computer Science from University of Southern California (USC) in August 2000 and December 1996, respectively. He obtained his B.Sc. degree in Computer Science and Engineering from Bangladesh University of Engineering and Technology, Dhaka, Bangladesh, in November of 1993. Professor Khan is currently supported by grants from the National Science Foundation (NSF), Texas Instruments, Alcatel, USA, and has been awarded the Sun Equipment Grant. Dr. Khan has more than 50 articles, book chapters and conference papers focusing in the areas of database systems, multimedia information management and data mining in bio-informatics and intrusion detection. Professor Khan has also served as a referee for database journals, conferences (e.g. IEEE TKDE, KAIS, ADL, VLDB) and he is currently serving as a program committee member for the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD2005), ACM 14th Conference on Information and Knowledge Management (CIKM 2005), International Conference on Database and Expert Systems Applications DEXA 2005 and International Conference on Cooperative Information Systems (CoopIS 2005), and is program chair of ACM SIGKDD International Workshop on Multimedia Data Mining, 2004. Farokh Bastani received the B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, and the M.S. and Ph.D. degrees in Computer Science from the University of California, Berkeley. He is currently a Professor of Computer Science at the University of Texas at Dallas. Dr. Bastani's research interests include various aspects of the ultrahigh dependable systems, especially automated software synthesis and testing, embedded real-time process-control and telecommunications systems and high-assurance systems engineering. Dr. Bastani was the Editor-in-Chief of the IEEE Transactions on Knowledge and Data Engineering (IEEE-TKDE). He is currently an emeritus EIC of IEEE-TKDE and is on the editorial board of the International Journal of Artificial Intelligence Tools, the International Journal of Knowledge and Information Systems and the Springer-Verlag series on Knowledge and Information Management. He was the program cochair of the 1997 IEEE Symposium on Reliable Distributed Systems, 1998 IEEE International Symposium on Software Reliability Engineering, 1999 IEEE Knowledge and Data Engineering Workshop, 1999 International Symposium on Autonomous Decentralised Systems, and the program chair of the 1995 IEEE International Conference on Tools with Artificial Intelligence. He has been on the program and steering committees of several conferences and workshops and on the editorial boards of the IEEE Transactions on Software Engineering, IEEE Transactions on Knowledge and Data Engineering and the Oxford University Press High Integrity Systems Journal. I-Ling Yen received her B.S. degree from Tsing-Hua University, Taiwan, and her M.S. and Ph.D. degrees in Computer Science from the University of Houston. She is currently an Associate Professor of Computer Science at University of Texas at Dallas. Dr. Yen's research interests include fault-tolerant computing, security systems and algorithms, distributed systems, Internet technologies, E-commerce and self-stabilising systems. She has published over 100 technical papers in these research areas and received many research awards from NSF, DOD, NASA and several industry companies. She has served as Program Committee member for many conferences and Program Chair/Cochair for the IEEE Symposium on Application-Specific Software and System Engineering & Technology, IEEE High Assurance Systems Engineering Symposium, IEEE International Computer Software and Applications Conference, and IEEE International Symposium on Autonomous Decentralized Systems. She has also served as a guest editor for a theme issue of IEEE Computer devoted to high-assurance systems.     

Resource access control for dynamic priority distributed real-time systems

Many of today’s complex computer applications are being modeled and constructed using the principles inherent to real-time distributed object systems. In response to this demand, the Object Management Group’s (OMG) Real-Time Special Interest Group (RT SIG) has worked to extend the Common Object Request Broker Architecture (CORBA) standard to include real-time specifications. This group’s most recent efforts focus on the requirements of dynamic distributed real-time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that meet the requirements of dynamic distributed real-time systems as specified by Dynamic Scheduling Real-Time CORBA 2.0 (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. These protocols are based on (i) distributed resource preclaiming that allocates resources in the message-based distributed system for deadlock prevention, (ii) distributed priority inheritance that bounds local and remote priority inversion, and (iii) distributed preemption ceilings that delimit the priority inversion time further. Chen Zhang is an Assistant Professor of Computer Information Systems at Bryant University. He received his M.S. and Ph.D. in Computer Science from the University of Alabama in 2000 and 2002, a B.S. from Tsinghua University, Beijing, China. Dr. Zhang’s primary research interests fall into the areas of distributed systems and telecommunications. He is a member of ACM, IEEE and DSI. David Cordes is a Professor of Computer Science at the University of Alabama; he has also served as Department Head since 1997. He received his Ph.D. in Computer Science from Louisiana State University in 1988, an M.S. in Computer Science from Purdue University in 1984, and a B.S. in Computer Science from the University of Arkansas in 1982. Dr. Cordes’s primary research interests fall into the areas of software engineering and systems. He is a member of ACM and a Senior Member of IEEE.     

A multi-threshold online smoothing technique for variable rate multimedia streams

Variable bit rate (VBR) compression for media streams allocates more bits to complex scenes and fewer bits to simple scenes. This results in a higher and more uniform visual and aural quality. The disadvantage of the VBR technique is that it results in bursty network traffic and uneven resource utilization when streaming media. In this study we propose an online media transmission smoothing technique that requires no a priori knowledge of the actual bit rate. It utilizes multi-level buffer thresholds at the client side that trigger feedback information sent to the server. This technique can be applied to both live captured streams and stored streams without requiring any server side pre-processing. We have implemented this scheme in our continuous media server and verified its operation across real world LAN and WAN connections. The results show smoother transmission schedules than any other previously proposed online technique. This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC), and IIS-0082826, DARPA and USAF under agreement nr. F30602-99-1-0524, and unrestricted cash/equipment gifts from NCR, IBM, Intel and SUN. Roger Zimmermann is currently a Research Assistant Professor with the Computer Science Department and a Research Area Director with the Integrated Media Systems Center (IMSC) at the University of Southern California. His research activities focus on streaming media architectures, peer-to-peer systems, immersive environments, and multimodal databases. He has made significant contributions in the areas of interactive and high quality video streaming, collaborative large-scale group communications, and mobile location-based services. Dr. Zimmermann has co-authored a book, a patent and more than seventy conference publications, journal articles and book chapters in the areas of multimedia and databases. He was the co-chair of the ACM NRBC 2004 workshop, the Open Source Software Competition of the ACM Multimedia 2004 conference, the short paper program systems track of ACM Multimedia 2005 and will be the proceedings chair of ACM Multimedia 2006. He is on the editorial board of SIGMOD DiSC, the ACM Computers in Entertainment magazine and the International Journal of Multimedia Tools and Applications. He has served on many conference program committees such as ACM Multimedia, SPIE MMCN and IEEE ICME. Cyrus Shahabi is currently an Associate Professor and the Director of the Information Laboratory (InfoLAB) at the Computer Science Department and also a Research Area Director at the NSF's Integrated Media Systems Center (IMSC) at the University of Southern California. He received his M.S. and Ph.D. degrees in Computer Science from the University of Southern California in May 1993 and August 1996, respectively. His B.S. degree is in Computer Engineering from Sharif University of Technology, Iran. He has two books and more than hundred articles, book chapters, and conference papers in the areas of databases and multimedia. Dr. Shahabi's current research interests include Peer-to-Peer Systems, Streaming Architectures, Geospatial Data Integration and Multidimensional Data Analysis. He is currently an associate editor of the IEEE Transactions on Parallel and Distributed Systems (TPDS) and on the editorial board of ACM Computers in Entertainment magazine. He is also the program committee chair of ICDE NetDB 2005 and ACM GIS 2005. He serves on many conference program committees such as IEEE ICDE 2006, ACM CIKM 2005, SSTD 2005 and ACM SIGMOD 2004. Dr. Shahabi is the recipient of the 2002 National Science Foundation CAREER Award and 2003 Presidential Early Career Awards for Scientists and Engineers (PECASE). In 2001, he also received an award from the Okawa Foundations. Kun Fu is currently a Ph.D candidate in computer science from the University of Southern California. He did research at the Data Communication Technology Research Institute and National Data Communication Engineering Center in China prior to coming to the United States and is currently working on large scale data stream recording architectures at the NSF's Integrated Media System Center (IMSC) and Data Management Research Laboratory (DMRL) at the Computer Science Department at USC. He received an MS in engineering science from the University of Toledo. He is a member of the IEEE. His research interests are in the area of scalable streaming architectures, distributed real-time systems, and multimedia computing and networking. Mehrdad Jahangiri was born in Tehran, Iran. He received the B.S. degree in Civil Engineering from University of Tehran at Tehran, in 1999. He is currently working towards the Ph.D. degree in Computer Science at the University of Southern California. He is currently a research assistant working on multidimensional data analysis at Integrated Media Systems Center (IMSC)—Information Laboratory (InfoLAB) at the Computer Science Department of the University of Southern California.     

Granularity and disaggregation in compositional modelling with applications to ecological systems

In the past decade, compositional modelling (CM) has established itself as the predominant knowledge-based approach to construct mathematical (simulation) models automatically. Although it is mainly applied to physical systems, there is a growing interest in applying CM to other domains, such as ecological and socio-economic systems. Inspired by this observation, this paper presents a method for extending the conventional CM techniques to suit systems that are fundamentally presented by interacting populations of individuals instead of physical components or processes. The work supports building model repositories for such systems, especially in addressing the most critical outstanding issues of granularity and disaggregation in ecological systems modelling. Jeroen Keppens is a lecturer in the Department of Computer Science at King’s College London, working in the Software Engineering Group. His research interests include Approximate and Qualitative Reasoning, Model Based Reasoning, Automated Model Construction and Applications of Artificial Intelligence in Law and Ecological Modelling. Dr. Keppens has published around 25 peer reviewed publications in these areas. Qiang Shen is a Professor and the Director of Research with the Department of Computer Science at the University of Wales, Aberystwyth, UK. He is also an Honorary Fellow at the University of Edinburgh, UK. His research interests include fuzzy systems, knowledge modelling, qualitative reasoning, and pattern recognition. Prof. Shen serves as an associate editor or editorial board member of a number of world leading journals, including the IEEE Transactions on Systems, Man, and Cybernetics (Part B), the IEEE Transactions on Fuzzy Systems, and Fuzzy Sets and Systems. He has acted as a Chair or Co-chair at a good number of major conferences in the field of Computational Intelligence. He has published a book and over 170 peer-refereed articles in international journals and conferences in Artificial Intelligence and related areas.     

On High Dimensional Projected Clustering of Data Streams

The data stream problem has been studied extensively in recent years, because of the great ease in collection of stream data. The nature of stream data makes it essential to use algorithms which require only one pass over the data. Recently, single-scan, stream analysis methods have been proposed in this context. However, a lot of stream data is high-dimensional in nature. High-dimensional data is inherently more complex in clustering, classification, and similarity search. Recent research discusses methods for projected clustering over high-dimensional data sets. This method is however difficult to generalize to data streams because of the complexity of the method and the large volume of the data streams.In this paper, we propose a new, high-dimensional, projected data stream clustering method, called HPStream. The method incorporates a fading cluster structure, and the projection based clustering methodology. It is incrementally updatable and is highly scalable on both the number of dimensions and the size of the data streams, and it achieves better clustering quality in comparison with the previous stream clustering methods. Our performance study with both real and synthetic data sets demonstrates the efficiency and effectiveness of our proposed framework and implementation methods.Charu C. Aggarwal received his B.Tech. degree in Computer Science from the Indian Institute of Technology (1993) and his Ph.D. degree in Operations Research from the Massachusetts Institute of Technology (1996). He has been a Research Staff Member at the IBM T. J. Watson Research Center since June 1996. He has applied for or been granted over 50 US patents, and has published over 75 papers in numerous international conferences and journals. He has twice been designated Master Inventor at IBM Research in 2000 and 2003 for the commercial value of his patents. His contributions to the Epispire project on real time attack detection were awarded the IBM Corporate Award for Environmental Excellence in 2003. He has been a program chair of the DMKD 2003, chair for all workshops organized in conjunction with ACM KDD 2003, and is also an associate editor of the IEEE Transactions on Knowledge and Data Engineering Journal. His current research interests include algorithms, data mining, privacy, and information retrieval.Jiawei Han is a Professor in the Department of Computer Science at the University of Illinois at Urbana–Champaign. He has been working on research into data mining, data warehousing, stream and RFID data mining, spatiotemporal and multimedia data mining, biological data mining, social network analysis, text and Web mining, and software bug mining, with over 300 conference and journal publications. He has chaired or served in many program committees of international conferences and workshops, including ACM SIGKDD Conferences (2001 best paper award chair, 1996 PC co-chair), SIAM-Data Mining Conferences (2001 and 2002 PC co-chair), ACM SIGMOD Conferences (2000 exhibit program chair), International Conferences on Data Engineering (2004 and 2002 PC vice-chair), and International Conferences on Data Mining (2005 PC co-chair). He also served or is serving on the editorial boards for Data Mining and Knowledge Discovery, IEEE Transactions on Knowledge and Data Engineering, Journal of Computer Science and Technology, and Journal of Intelligent Information Systems. He is currently serving on the Board of Directors for the Executive Committee of ACM Special Interest Group on Knowledge Discovery and Data Mining (SIGKDD). Jiawei has received three IBM Faculty Awards, the Outstanding Contribution Award at the 2002 International Conference on Data Mining, ACM Service Award (1999) and ACM SIGKDD Innovation Award (2004). He is an ACM Fellow (since 2003). He is the first author of the textbook “Data Mining: Concepts and Techniques” (Morgan Kaufmann, 2001).Jianyong Wang received the Ph.D. degree in computer science in 1999 from the Institute of Computing Technology, the Chinese Academy of Sciences. Since then, he ever worked as an assistant professor in the Department of Computer Science and Technology, Peking (Beijing) University in the areas of distributed systems and Web search engines (May 1999–May 2001), and visited the School of Computing Science at Simon Fraser University (June 2001–December 2001), the Department of Computer Science at the University of Illinois at Urbana-Champaign (December 2001–July 2003), and the Digital Technology Center and Department of Computer Science and Engineering at the University of Minnesota (July 2003–November 2004), mainly working in the area of data mining. He is currently an associate professor in the Department of Computer Science and Technology, Tsinghua University, Beijing, China.Philip S. Yuis the manager of the Software Tools and Techniques group at the IBM Thomas J. Watson Research Center. The current focuses of the project include the development of advanced algorithms and optimization techniques for data mining, anomaly detection and personalization, and the enabling of Web technologies to facilitate E-commerce and pervasive computing. Dr. Yu,s research interests include data mining, Internet applications and technologies, database systems, multimedia systems, parallel and distributed processing, disk arrays, computer architecture, performance modeling and workload analysis. Dr. Yu has published more than 340 papers in refereed journals and conferences. He holds or has applied for more than 200 US patents. Dr. Yu is an IBM Master Inventor.Dr. Yu is a Fellow of the ACM and a Fellow of the IEEE. He will become the Editor-in-Chief of IEEE Transactions on Knowledge and Data Engineering on Jan. 2001. He is an associate editor of ACM Transactions of the Internet Technology and also Knowledge and Information Systems Journal. He is a member of the IEEE Data Engineering steering committee. He also serves on the steering committee of IEEE Intl. Conference on Data Mining. He received an IEEE Region 1 Award for “promoting and perpetuating numerous new electrical engineering concepts”. Philip S. Yu received the B.S. Degree in E.E. from National Taiwan University, Taipei, Taiwan, the M.S. and Ph.D. degrees in E.E. from Stanford University, and the M.B.A. degree from New York University.     

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.     

Mining frequent patterns with the pattern tree

Mining frequent patterns with a frequent pattern tree (FP-tree in short) avoids costly candidate generation and repeatedly occurrence frequency checking against the support threshold. It therefore achieves much better performance and efficiency than Apriori-like algorithms. However, the database still needs to be scanned twice to get the FP-tree. This can be very time-consuming when new data is added to an existing database because two scans may be needed for not only the new data but also the existing data. In this research we propose a new data structure, the pattern tree (P-tree in short), and a new technique, which can get the P-tree through only one scan of the database and can obtain the corresponding FP-tree with a specified support threshold. Updating a P-tree with new data needs one scan of the new data only, and the existing data does not need to be re-scanned. Our experiments show that the P-tree method outperforms the FP-tree method by a factor up to an order of magnitude in large datasets. A preliminary version of this paper has been published in theProceedings of the 2002 IEEE International Conference on Data Mining (ICDM ’02), 629–632. Hao Huang: He is pursuing his Ph.D. degree in the Department of Computer Science at the University of Virginia. His research interests are Gird Computing, Data Mining and their applications in Bioinformatics. He received his M.S. in Computer Science from Colorado School of Mines in 2001. Xindong Wu, Ph.D.: He is Professor and Chair of the Department of Computer Science at the University of Vermont, USA. He holds a Ph.D. in Artificial Intelligence from the University of Edinburgh, Britain. His research interests include data mining, knowledge-based systems, and Web information exploration. He has published extensively in these areas in various journals and conferences, including IEEE TKDE, TPAMI, ACM TOIS, IJCAI, AAAI, ICML, KDD, ICDM, and WWW. Dr. Wu is the Executive Editor (January 1, 1999-December 31, 2004) and an Honorary Editor-in-Chief (starting January 1, 2005) of Knowledge and Information Systems (a peer-reviewed archival journal published by Springer), the founder and current Steering Committee Chair of the IEEE International Conference on Data Mining (ICDM), a Series Editor of the Springer Book Series on Advanced Information and Knowledge Processing (AI&KP), and the Chair of the IEEE Computer Society Technical Committee on Computational Intelligence (TCCI). He served as an Associate Editor for the IEEE Transactions on Knowledge and Data Engineering (TKDE) between January 1, 2000 and December 31, 2003, and is the Editor-in-Chief of TKDE since January 1, 2005. He is the winner of the 2004 ACM SIGKDD Service Award. Richard Relue, Ph.D.: He received his Ph.D. in Computer Science from the Colorado School of Mines in 2003. His research interests include association rules in data mining, neural networks for automated classification, and artificial intelligence for robot navigation. He has been an Information Technology consultant since 1992, working with Ball Aerospace and Technology, Rational Software, Natural Fuels Corporation, and Western Interstate Commission for Higher Education (WICHE).     

Real-time classification of variable length multi-attribute motions

Multi-attribute motion data can be generated in many applications/ devices, such as motion capture devices and animations. It can have dozens of attributes, thousands of rows, and even similar motions can have different durations and different speeds at corresponding parts. There are no row-to-row correspondences between data matrices of two motions. To be classified and recognized, multi-attribute motion data of different lengths are reduced to feature vectors by using the properties of singular value decomposition (SVD) of motion data. The reduced feature vectors of similar motions are close to each other, while reduced feature vectors are different from each other if their motions are different. By applying support vector machines (SVM) to the feature vectors, we efficiently classify and recognize real-world multi-attribute motion data. With our data set of more than 300 motions with different lengths and variations, SVM outperforms classification by related similarity measures, in terms of accuracy and CPU time. The performance of our approach shows its feasibility of real-time applications to real-world data. Chuanjun Li is a Ph.D. candidate in Computer Science at the University of Texas at Dallas. His Ph.D. research works primarily on efficient segmentation and recognition of human motion streams, and development of indexing and clustering techniques for the multi-attribute motion data as well as classification of motion data. Dr. Latifur R. Khan has been an Assistant Professor of Computer Science Department at University of Texas at Dallas since September, 2000. He received his Ph.D. and M.S. degree in Computer Science from University of Southern California (USC) in August 2000 and December 1996, respectively. He obtained his B.Sc. degree in Computer Science and Engineering from Bangladesh University of Engineering and Technology, Dhaka, Bangladesh in November 1993. Professor Khan is currently supported by grants from the National Science Foundation (NSF), Texas Instruments, NOKIA, Alcatel, USA and has been awarded the Sun Equipment Grant. Dr. Khan has more than 50 articles, book chapters, and conference papers focusing in the areas of: database systems, multimedia information management, and data mining in bio-informatics and intrusion detection. Professor Khan has also served as a referee for database journals, conferences (e.g., IEEE TKDE, KAIS, ADL, VLDB) and he is currently serving as a program committee member for Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD2005), ACM Fourteenth Conference on Information and Knowledge Management (CIKM 2005), International Conference on Database and Expert Systems Applications DEXA 2005, and International Conference on Cooperative Information Systems (CoopIS 2005), and program chair of ACM SIGKDD International Workshop on Multimedia Data Mining, 2004. Dr. Balakrishnan Prabhakaran is currently with the Department of Computer Science, University of Texas at Dallas. Dr. B. Prabhakaran has been working in the area of multimedia systems: multimedia databases, authoring & presentation, resource management, and scalable web-based multimedia presentation servers. He has published several research papers in prestigious conferences and journals in this area.Dr. Prabhakaran received the NSF CAREER Award FY 2003 for his proposal on Animation Databases. Dr. Prabhakaran has served as an Associate Chair of the ACM Multimedia’2003 (November 2003, California), ACM MM 2000 (November 2000, Los Angeles), and ACM Multimedia’99 conference (Florida, November 1999). He has served as guest-editor (special issue on Multimedia Authoring and Presentation) for ACM Multimedia Systems journal. He is also serving on the editorial board of Multimedia Tools and Applications Journal, Kluwer Academic Publishers. He has also served as program committee member on several multimedia conferences and workshops. Dr. Prabhakaran has presented tutorials in several conferences on topics such as network resource management, adaptive multimedia presentations, and scalable multimedia servers.B. Prabhakaran has served as a visiting research faculty with the Department of Computer Science, University of Maryland, College Park. He also served as a faculty in the Department of Computer Science, National University of Singapore as well as in the Indian Institute of Technology, Madras, India     

Data-driven fuzzy rule generation and its application for student academic performance evaluation

Several approaches using fuzzy techniques have been proposed to provide a practical method for evaluating student academic performance. However, these approaches are largely based on expert opinions and are difficult to explore and utilize valuable information embedded in collected data. This paper proposes a new method for evaluating student academic performance based on data-driven fuzzy rule induction. A suitable fuzzy inference mechanism and associated Rule Induction Algorithm is given. The new method has been applied to perform Criterion-Referenced Evaluation (CRE) and comparisons are made with typical existing methods, revealing significant advantages of the present work. The new method has also been applied to perform Norm-Referenced Evaluation (NRE), demonstrating its potential as an extended method of evaluation that can produce new and informative scores based on information gathered from data. Khairul Rasmani is a lecturer at the Faculty of Information Technology and Quantitative Sciences, Universiti Teknologi MARA, Malaysia. He received his Masters Degree in Mathematical Education from University of Leeds, UK in 1997 and his Ph.D. degree from University of Wales, Aberystwyth, UK in December 2005. His research interests include fuzzy approximate reasoning, fuzzy rule-based systems and fuzzy classification systems. Qiang Shen is a Professor and the Director of Research with the Department of Computer Science at the University of Wales, Aberystwyth, UK. He is also an Honorary Fellow at the University of Edinburgh, UK. His research interests include fuzzy systems, knowledge modelling, qualitative reasoning, and pattern recognition. Prof. Shen serves as an associate editor or editorial board member of a number of world leading journals, including the IEEE Transactions on Systems, Man, and Cybernetics (Part B), the IEEE Transactions on Fuzzy Systems, and Fuzzy Sets and Systems. He has acted as a Chair or Co-chair at a good number of major conferences in the field of Computational Intelligence. He has published a book and over 170 peer-refereed articles in international journals and conferences in Artificial Intelligence and related areas.     

Effective classification of noisy data streams with attribute-oriented dynamic classifier selection

Recently, mining from data streams has become an important and challenging task for many real-world applications such as credit card fraud protection and sensor networking. One popular solution is to separate stream data into chunks, learn a base classifier from each chunk, and then integrate all base classifiers for effective classification. In this paper, we propose a new dynamic classifier selection (DCS) mechanism to integrate base classifiers for effective mining from data streams. The proposed algorithm dynamically selects a single “best” classifier to classify each test instance at run time. Our scheme uses statistical information from attribute values, and uses each attribute to partition the evaluation set into disjoint subsets, followed by a procedure that evaluates the classification accuracy of each base classifier on these subsets. Given a test instance, its attribute values determine the subsets that the similar instances in the evaluation set have constructed, and the classifier with the highest classification accuracy on those subsets is selected to classify the test instance. Experimental results and comparative studies demonstrate the efficiency and efficacy of our method. Such a DCS scheme appears to be promising in mining data streams with dramatic concept drifting or with a significant amount of noise, where the base classifiers are likely conflictive or have low confidence. A preliminary version of this paper was published in the Proceedings of the 4th IEEE International Conference on Data Mining, pp 305–312, Brighton, UK Xingquan Zhu received his Ph.D. degree in Computer Science from Fudan University, Shanghai, China, in 2001. He spent four months with Microsoft Research Asia, Beijing, China, where he was working on content-based image retrieval with relevance feedback. From 2001 to 2002, he was a Postdoctoral Associate in the Department of Computer Science, Purdue University, West Lafayette, IN. He is currently a Research Assistant Professor in the Department of Computer Science, University of Vermont, Burlington, VT. His research interests include Data mining, machine learning, data quality, multimedia computing, and information retrieval. Since 2000, Dr. Zhu has published extensively, including over 40 refereed papers in various journals and conference proceedings. Xindong Wu is a Professor and the Chair of the Department of Computer Science at the University of Vermont. He holds a Ph.D. in Artificial Intelligence from the University of Edinburgh, Britain. His research interests include data mining, knowledge-based systems, and Web information exploration. He has published extensively in these areas in various journals and conferences, including IEEE TKDE, TPAMI, ACM TOIS, IJCAI, ICML, KDD, ICDM, and WWW, as well as 11 books and conference proceedings. Dr. Wu is the Editor-in-Chief of the IEEE Transactions on Knowledge and Data Engineering (by the IEEE Computer Society), the founder and current Steering Committee Chair of the IEEE International Conference on Data Mining (ICDM), an Honorary Editor-in-Chief of Knowledge and Information Systems (by Springer), and a Series Editor of the Springer Book Series on Advanced Information and Knowledge Processing (AI&KP). He is the 2004 ACM SIGKDD Service Award winner. Ying Yang received her Ph.D. in Computer Science from Monash University, Australia in 2003. Following academic appointments at the University of Vermont, USA, she currently holds a Research Fellow at Monash University, Australia. Dr. Yang is recognized for contributions in the fields of machine learning and data mining. She has published many scientific papers and book chapters on adaptive learning, proactive mining, noise cleansing and discretization. Contact her at yyang@mail.csse.monash.edu.au.     

A Sampling-Based Motion Planning Approach to Maintain Visibility of Unpredictable Targets

This paper deals with the surveillance problem of computing the motions of one or more robot observers in order to maintain visibility of one or several moving targets. The targets are assumed to move unpredictably, and the distribution of obstacles in the workspace is assumed to be known in advance. Our algorithm computes a motion strategy by maximizing the shortest distance to escape—the shortest distance the target must move to escape an observer's visibility region. Since this optimization problem is intractable, we use randomized methods to generate candidate surveillance paths for the observers. We have implemented our algorithms, and we provide experimental results using real mobile robots for the single target case, and simulation results for the case of two targets-two observers. Rafael Murrieta-Cid received the B.S degree in Physics Engineering (1990), and the M.Sc. degree in Automatic Manufacturing Systems (1993), both from “Instituto Tecnológico y de Estudios Superiores de Monterrey” (ITESM) Campus Monterrey. He received his Ph.D. from the “Institut National Polytechnique” (INP) of Toulouse, France (1998). His Ph.D research was done in the Robotics and Artificial Intelligence group of the LAAS/CNRS. In 1998–1999, he was a postdoctoral researcher in the Computer Science Department at Stanford University. From January 2000 to July 2002 he was an assistant professor in the Electrical Engineering Department at ITESM Campus México City, México. In 2002–2004, he was working as a postdoctoral research associate in the Beckman Institute and Department of Electrical and Computer Engineering of the University of Illinois at Urbana-Champaign. Since August 2004, he is director of the Mechatronics Research Center in the ITESM Campus Estado de México, México. He is mainly interested in sensor-based robotics motion planning and computer vision. Benjamin Tovar received the B.S degree in electrical engineering from ITESM at Mexico City, Mexico, in 2000, and the M.S. in electrical engineering from University of Illinois, Urbana-Champaign, USA, in 2004. Currently (2005) he is pursuing the Ph.D degree in Computer Science at the University of Illinois. Prior to M.S. studies he worked as a research assistant at Mobile Robotics Laboratory at ITESM Mexico City. He is mainly interested in motion planning, visibility-based tasks, and minimal sensing for robotics. Seth Hutchinson received his Ph. D. from Purdue University in West Lafayette, Indiana in 1988. He spent 1989 as a Visiting Assistant Professor of Electrical Engineering at Purdue University. In 1990 Dr. Hutchinson joined the faculty at the University of Illinois in Urbana-Champaign, where he is currently a Professor in the Department of Electrical and Computer Engineering, the Coordinated Science Laboratory, and the Beckman Institute for Advanced Science and Technology. Dr. Hutchinson is currently a senior editor of the IEEE Transactions on Robotics and Automation. In 1996 he was a guest editor for a special section of the Transactions devoted to the topic of visual servo control, and in 1994 he was co-chair of an IEEE Workshop on Visual Servoing. In 1996 and 1998 he co-authored papers that were finalists for the King-Sun Fu Memorial Best Transactions Paper Award. He was co-chair of IEEE Robotics and Automation Society Technical Committee on Computer and Robot Vision from 1992 to 1996, and has served on the program committees for more than thirty conferences related to robotics and computer vision. He has published more than 100 papers on the topics of robotics and computer vision.     

Preference update for e-commerce applications: Model,language, and processing

It is likely that customers issue requests based on out-of-date information in e-commerce application systems. Hence, the transaction failure rates would increase greatly. In this paper, we present a preference update model to address this problem. A preference update is an extended SQL update statement where a user can request the desired number of target data items by specifying multiple preferences. Moreover, the preference update allows easy extraction of criteria from a set of concurrent requests and, hence, optimal decisions for the data assignments can be made. We propose a group evaluation strategy for preference update processing in a multidatabase environment. The experimental results show that the group evaluation can effectively increase the customer satisfaction level with acceptable cost. Peng Li is the Chief Software Architect of didiom LLC. Before that, he was a visiting assistant professor of computer science department in Western Kentucky University. He received his Ph.D. degree of computer science from the University of Texas at Dallas. He also holds a B.Sc. and M.S. in Computer Science from the Renmin University of China. His research interests include database systems, database security, transaction processing, distributed and Internet computer and E-commerce. Manghui Tu received a Bachelor degree of Science from Wuhan University, P.R. China in 1996, and a Master Degree in Computer Science from the University of Texas at Dallas 2001. He is currently working toward the PhD degree in the Department of Computer Science at the University of Texas at Dallas. Mr. Tu’s research interests include distributed systems, grid computing, information security, mobile computing, and scientific computing. His PhD research work focus on the data management in secure and high performance data grid. He is a student member of the IEEE. I-Ling Yen received her BS degree from Tsing-Hua University, Taiwan, and her MS and PhD degrees in Computer Science from the University of Houston. She is currently an Associate Professor of Computer Science at the University of Texas at Dallas. Dr. Yen’s research interests include fault-tolerant computing, security systems and algorithms, distributed systems, Internet technologies, E-commerce, and self-stabilizing systems. She had published over 100 technical papers in these research areas and received many research awards from NSF, DOD, NASA, and several industry companies. She has served as Program Committee member for many conferences and Program Chair/Co-Chair for the IEEE Symposium on Application-Specific Software and System Engineering & Technology, IEEE High Assurance Systems Engineering Symposium, IEEE International Computer Software and Applications Conference, and IEEE International Symposium on Autonomous Decentralized Systems. She is a member of the IEEE. Zhonghang Xia received the B.S. degree in applied mathematics from Dalian University of Technology in 1990, the M.S. degree in Operations Research from Qufu Normal University in 1993, and the Ph.D. degree in computer science from the University of Texas at Dallas in 2004. He is now an assistant professor in the Department of Computer Science, Western Kentucky University, Bowling Green, KY. His research interests are in the area of multimedia computing and networking, distributed systems, and data mining.     

Probabilistic verification of communication protocols

Complete behavior of a communication protocol can be very large. It is worth investigating whether partial exploration of the behavior generates reasonable results. We present such a procedure which performs partial exploration using most-probable-first search. Some of the ideas used in this procedure are based on a convolutional decoding procedure due to Jelinek and a performance evaluation procedure due to Rudin. Multiple trees of protocol behavior are constructed. Some results on estimating the probability of encountering an unexplored state in a finite run of a protocol are also presented. Nicholas F. Maxemchuk received the B.S.E.E. degree from the City College of New York, NY, and the M.S.E.E. and Ph.D. degrees from the University of Pennsylvania, Philadelphia. He is the Head of the Distributed Systems Research Department at AT & T Bell Laboratories, Murray Hill, NJ, and has been at AT & T Bell Laboratories since 1976. Prior to joining Bell Laboratories he was at the RCA David Sarnoff Research Center in Princeton, NJ for eight years. Dr. Maxemchuk has been on the adjunct faculties of Columbia University and the University of Pennsylvania. He has been an advisor to the United Nations on data networking and has been on networking panels for the US Air Force and DARPA. He has served as the Editor for Data Communications for the IEEE Transactions on Communications, as a Guest Editor for the IEEE Journal on Selected Areas in Communications, and has been on the program committee for numerous conferences and workshops. He was awarded the RCA Laboratories Outstanding Achievement Award, the Bell Laboratories Distinguished Technical Staff Award, and the IEEE's 1985 and 1987 Leonard G. Abraham Prize Paper Award. Krishan Sabnani received a BSEE degree from Indian Institute of Technology, New Delhi, India and a PhD degree from Columbia University, New York, NY. In 1981, he joined AT & T Bell Laboratories after graduating from Columbia University. He is currently working in the Distributed Systems Research Department of AT & T Bell Laboratories. His major area of interest is communication protocols. Dr. Sabnani was a co-chairman of the Eighth International Symposium on Protocol Specification, Testing, and Verification held in Atlantic City, NJ during June 1988. He is currently an editor of the IEEE Transactions on Communications and of the IEEE Transactions on Computers. He has served on the program committees of several conferences. He is also a guest editor of two special issues of the Journal on Selected Areas in Communications (JSAC) and the Computer Networks and ISDN Systems Journal, respectively.     

Catch the moment: maintaining closed frequent itemsets over a data stream sliding window

This paper considers the problem of mining closed frequent itemsets over a data stream sliding window using limited memory space. We design a synopsis data structure to monitor transactions in the sliding window so that we can output the current closed frequent itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot monitor all possible itemsets. However, monitoring only frequent itemsets will make it impossible to detect new itemsets when they become frequent. In this paper, we introduce a compact data structure, the closed enumeration tree (CET), to maintain a dynamically selected set of itemsets over a sliding window. The selected itemsets contain a boundary between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data stream are reflected by boundary movements in the CET. In other words, a status change of any itemset (e.g., from non-frequent to frequent) must occur through the boundary. Because the boundary is relatively stable, the cost of mining closed frequent itemsets over a sliding window is dramatically reduced to that of mining transactions that can possibly cause boundary movements in the CET. Our experiments show that our algorithm performs much better than representative algorithms for the sate-of-the-art approaches. Yun Chi is currently a Ph.D. student at the Department of Computer Science, UCLA. His main areas of research include database systems, data mining, and bioinformatics. For data mining, he is interested in mining labeled trees and graphs, mining data streams, and mining data with uncertainty. Haixun Wang is currently a research staff member at IBM T. J. Watson Research Center. He received the B.S. and the M.S. degree, both in computer science, from Shanghai Jiao Tong University in 1994 and 1996. He received the Ph.D. degree in computer science from the University of California, Los Angeles in 2000. He has published more than 60 research papers in referred international journals and conference proceedings. He is a member of the ACM, the ACM SIGMOD, the ACM SIGKDD, and the IEEE Computer Society. He has served in program committees of international conferences and workshops, and has been a reviewer for some leading academic journals in the database field. Philip S. Yureceived the B.S. Degree in electrical engineering from National Taiwan University, the M.S. and Ph.D. degrees in electrical engineering from Stanford University, and the M.B.A. degree from New York University. He is with the IBM Thomas J. Watson Research Center and currently manager of the Software Tools and Techniques group. His research interests include data mining, Internet applications and technologies, database systems, multimedia systems, parallel and distributed processing, and performance modeling. Dr. Yu has published more than 430 papers in refereed journals and conferences. He holds or has applied for more than 250 US patents.Dr. Yu is a Fellow of the ACM and a Fellow of the IEEE. He is associate editors of ACM Transactions on the Internet Technology and ACM Transactions on Knowledge Discovery in Data. He is a member of the IEEE Data Engineering steering committee and is also on the steering committee of IEEE Conference on Data Mining. He was the Editor-in-Chief of IEEE Transactions on Knowledge and Data Engineering (2001–2004), an editor, advisory board member and also a guest co-editor of the special issue on mining of databases. He had also served as an associate editor of Knowledge and Information Systems. In addition to serving as program committee member on various conferences, he will be serving as the general chairman of 2006 ACM Conference on Information and Knowledge Management and the program chairman of the 2006 joint conferences of the 8th IEEE Conference on E-Commerce Technology (CEC' 06) and the 3rd IEEE Conference on Enterprise Computing, E-Commerce and E-Services (EEE' 06). He was the program chairman or co-chairs of the 11th IEEE International Conference on Data Engineering, the 6th Pacific Area Conference on Knowledge Discovery and Data Mining, the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, the 2nd IEEE International Workshop on Research Issues on Data Engineering:Transaction and Query Processing, the PAKDD Workshop on Knowledge Discovery from Advanced Databases, and the 2nd IEEE International Workshop on Advanced Issues of E-Commerce and Web-based Information Systems. He served as the general chairman of the 14th IEEE International Conference on Data Engineering and the general co-chairman of the 2nd IEEE International Conference on Data Mining. He has received several IBM honors including 2 IBM Outstanding Innovation Awards, an Outstanding Technical Achievement Award, 2 Research Division Awards and the 84th plateau of Invention Achievement Awards. He received an Outstanding Contributions Award from IEEE International Conference on Data Mining in 2003 and also an IEEE Region 1 Award for “promoting and perpetuating numerous new electrical engineering concepts" in 1999. Dr. Yu is an IBM Master Inventor. Richard R. Muntz is a Professor and past chairman of the Computer Science Department, School of Engineering and Applied Science, UCLA. His current research interests are sensor rich environments, multimedia storage servers and database systems, distributed and parallel database systems, spatial and scientific database systems, data mining, and computer performance evaluation. He is the author of over one hundred and fifty research papers.Dr. Muntz received the BEE from Pratt Institute in 1963, the MEE from New York University in 1966, and the Ph.D. in Electrical Engineering from Princeton University in 1969. He is a member of the Board of Directors for SIGMETRICS and past chairman of IFIP WG7.3 on performance evaluation. He was a member of the Corporate Technology Advisory Board at NCR/Teradata, a member of the Science Advisory Board of NASA's Center of Excellence in Space Data Information Systems, and a member of the Goddard Space Flight Center Visiting Committee on Information Technology. He recently chaired a National Research Council study on “The Intersection of Geospatial Information and IT” which was published in 2003. He was an associate editor for the Journal of the ACM from 1975 to 1980 and the Editor-in-Chief of ACM Computing Surveys from 1992 to 1995. He is a Fellow of the ACM and a Fellow of the IEEE.     

Improving WCET by applying worst-case path optimizations

It is advantageous to perform compiler optimizations that attempt to lower the worst-case execution time (WCET) of an embedded application since tasks with lower WCETs are easier to schedule and more likely to meet their deadlines. Compiler writers in recent years have used profile information to detect the frequently executed paths in a program and there has been considerable effort to develop compiler optimizations to improve these paths in order to reduce the average-case execution time (ACET). In this paper, we describe an approach to reduce the WCET by adapting and applying optimizations designed for frequent paths to the worst-case (WC) paths in an application. Instead of profiling to find the frequent paths, our WCET path optimization uses feedback from a timing analyzer to detect the WC paths in a function. Since these path-based optimizations may increase code size, the subsequent effects on the WCET due to these optimizations are measured to ensure that the worst-case path optimizations actually improve the WCET before committing to a code size increase. We evaluate these WC path optimizations and present results showing the decrease in WCET versus the increase in code size. A preliminary version of this paper entitled “Improving WCET by optimizing worst-case paths” appeared in the 2005 Real-Time and Embedded Technology and Applications Symposium. Wankang Zhao received his PhD in Computer Science from Florida State University in 2005. He was an associate professor in Nanjin University of Post and Telecommunications. He is currently working for Datamaxx Corporation. William Kreahling received his PhD in Computer Science from Florida State University in 2005. He is currently an assistant professor in the Math and Computer Science department at Western Carolina University. His research interests include compilers, computer architecture and parallel computing. David Whalley received his PhD in CS from the University of Virginia in 1990. He is currently the E.P. Miles professor and chair of the Computer Science department at Florida State University. His research interests include low-level compiler optimizations, tools for supporting the development and maintenance of compilers, program performance evaluation tools, predicting execution time, computer architecture, and embedded systems. Some of the techniques that he developed for new compiler optimizations and diagnostic tools are currently being applied in industrial and academic compilers. His research is currently supported by the National Science Foundation. More information about his background and research can be found on his home page, http://www.cs.fsu.edu/∼whalley. Dr. Whalley is a member of the IEEE Computer Society and the Association for Computing Machinery. Chris Healy earned a PhD in computer science from Florida State University in 1999, and is currently an associate professor of computer science at Furman University. His research interests include static and parametric timing analysis, real-time and embedded systems, compilers and computer architecture. He is committed to research experiences for undergraduate students, and his work has been supported by funding from the National Science Foundation. He is a member of ACM and the IEEE Computer Society. Frank Mueller is an Associate Professor in Computer Science and a member of the Centers for Embedded Systems Research (CESR) and High Performance Simulations (CHiPS) at North Carolina State University. Previously, he held positions at Lawrence Livermore National Laboratory and Humboldt University Berlin, Germany. He received his Ph.D. from Florida State University in 1994. He has published papers in the areas of embedded and real-time systems, compilers and parallel and distributed systems. He is a founding member of the ACM SIGBED board and the steering committee chair of the ACM SIGPLAN LCTES conference. He is a member of the ACM, ACM SIGPLAN, ACM SIGBED and the IEEE Computer Society. He is a recipient of an NSF Career Award.     

Geo-located image categorization and location recognition

Image categorization is undoubtedly one of the most recent and challenging problems faced in Computer Vision. The scientific literature is plenty of methods more or less efficient and dedicated to a specific class of images; further, commercial systems are also going to be advertised in the market. Nowadays, additional data can also be attached to the images, enriching its semantic interpretation beyond the pure appearance. This is the case of geo-location data that contain information about the geographical place where an image has been acquired. This data allow, if not require, a different management of the images, for instance, to the purpose of easy retrieval from a repository, or of identifying the geographical place of an unknown picture, given a geo-referenced image repository. This paper constitutes a first step in this sense, presenting a method for geo-referenced image categorization, and for the recognition of the geographical location of an image without such information available. The solutions presented are based on robust pattern recognition techniques, such as the probabilistic Latent Semantic Analysis, the Mean Shift clustering and the Support Vector Machines. Experiments have been carried out on a couple of geographical image databases: results are actually very promising, opening new interesting challenges and applications in this research field. The article is published in the original. Marco Cristani received the Laurea degree in 2002 and the Ph.D. degree in 2006, both in Computer Science from the University of Verona, Verona, Italy. He was a visiting Ph.D. student at the Computer Vision Lab, Institute for Robotics and Intelligent Systems School of Engineering (IRIS), University of Southern California, Los Angeles, in 2004–2005. He is now an Assistant Professor with the Department of Computer Science, University of Verona, working with the Vision, Image Processing and Sounds (VIPS) Lab. His main research interests include statistical pattern recognition, generative modeling via graphical models, and non-parametric data fusion techniques, with applications on surveillance, segmentation and image and video retrieval. He is the author of several papers in the above subjects and a reviewer for several international conferences and journals. Alessandro Perina received the BD and MS degrees in Information Technologies and Intelligent and Multimedia Systems from the University of Verona, Verona, Italy, in 2004 and 2006, respectively. He is currently a Ph.D. candidate in the Computer Science Department at the University of Verona. His research interests include computer vision, machine learning and pattern recognition. He is a student member of the IEEE. Umberto Castellani is Ricercatore (i.e., Research Assistant) of Department of Computer Science at University of Verona. He received his Dottorato di Ricerca (Ph.D.) in Computer Science from the University of Verona in 2003 working on 3D data modelling and reconstruction. During his Ph.D., he had been Visiting Research Fellow at the Machine Vision Unit of the Edinburgh University, in 2001. In 2007 he has been an Invited Professor for two months at the LASMEA laboratory in Clermont-Ferrand, France. In 2008, he has been Visiting Researcher for two months at the PRIP laboratory of the Michigan State University (USA). His main research interests concern the processing of 3D data coming from different acquisition systems such as 3D models from 3D scanners, acoustic images for the vision in underwater environment, and MRI scans for biomedical applications. The addressed methodologies are focused on the intersections among Machine Learning, Computer Vision and Computer Graphics. Vittorio Murino received the Laurea degree in electronic engineering in 1989 and the Ph.D. degree in electronic engineering and computer science in 1993, both from the University of Genoa, Genoa, Italy. He is a Full Professor with the Department of Computer Science, University of Verona. From 1993 to 1995, he was a Postdoctoral Fellow in the Signal Processing and Understanding Group, Department of Biophysical and electronic Engineering, University of Genoa, where he supervised of research activities on image processing for object recognition and pattern classification in underwater environments. From 1995 to 1998, he was an Assistant Professor of the Department of Mathematics and Computer Science, University of Udine, Udine, Italy. Since 1998, he has been with the University of Verona, where he founded and is responsible for the Vision, Image processing, and Sound (VIPS) Laboratory. He is scientifically responsible for several national and European projects and is an Evaluator for the European Commission of research project proposals related to different scientific programmes and frameworks. His main research interests include computer vision and pattern recognition, probabilistic techniques for image and video processing, and methods for integrating graphics and vision. He is author or co-author of more than 150 papers published in refereed journals and international conferences. Dr. Murino is a referee for several international journals, a member of the technical committees for several conferences (ECCV, ICPR, ICIP), and a member of the editorial board of Pattern Recognition, IEEE Transactions on Systems, Man, and Cybernetics, Pattern Analysis and Applications and Electronic Letters on Computer Vision and Image Analysis (ELCVIA). He was the promotor and Guest Editor off our special issues of Pattern Recognition and is a Fellow of the IAPR.     

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.     

Efficient string matching with wildcards and length constraints

This paper defines a challenging problem of pattern matching between a pattern P and a text T, with wildcards and length constraints, and designs an efficient algorithm to return each pattern occurrence in an online manner. In this pattern matching problem, the user can specify the constraints on the number of wildcards between each two consecutive letters of P and the constraints on the length of each matching substring in T. We design a complete algorithm, SAIL that returns each matching substring of P in T as soon as it appears in T in an O(n+klmg) time with an O(lm) space overhead, where n is the length of T, k is the frequency of P's last letter occurring in T, l is the user-specified maximum length for each matching substring, m is the length of P, and g is the maximum difference between the user-specified maximum and minimum numbers of wildcards allowed between two consecutive letters in P.SAIL stands for string matching with wildcards and length constraints. Gong Chen received the B.Eng. degree from the Beijing University of Technology, China, and the M.Sc. degree from the University of Vermont, USA, both in computer science. He is currently a graduate student in the Department of Statistics at the University of California, Los Angeles, USA. His research interests include data mining, statistical learning, machine learning, algorithm analysis and design, and database management. Xindong Wu is a professor and the chair of the Department of Computer Science at the University of Vermont. He holds a Ph.D. in Artificial Intelligence from the University of Edinburgh, Britain. His research interests include data mining, knowledge-based systems, and Web information exploration. He has published extensively in these areas in various journals and conferences, including IEEE TKDE, TPAMI, ACM TOIS, IJCAI, AAAI, ICML, KDD, ICDM and WWW, as well as 12 books and conference proceedings. Dr. Wu is the Editor-in-Chief of the IEEE Transactions on Knowledge and Data Engineering (by the IEEE Computer Society), the founder and current Steering Committee Chair of the IEEE International Conference on Data Mining (ICDM),an Honorary Editor-in-Chief of Knowledge and Information Systems (by Springer), and a Series Editor of the Springer Book Series on Advanced Information and Knowledge Processing (AI&KP). He is the 2004 ACM SIGKDD Service Award winner. Xingquan Zhu received his Ph.D degree in Computer Science from Fudan University, Shanghai, China, in 2001. He spent 4 months with Microsoft Research Asia, Beijing, China, where he was working on content-based image retrieval with relevance feedback. From 2001 to 2002, he was a postdoctoral associate in the Department of Computer Science at Purdue University, West Lafayette, IN. He is currently a research assistant professor in the Department of Computer Science, the University of Vermont, Burlington, VT. His research interests include data mining, machine learning, data quality, multimedia computing, and information retrieval. Since 2000, Dr. Zhu has published extensively, including over 50 refereed papers in various journals and conference proceedings. Abdullah N. Arslan got his Ph.D. degree in Computer Science in 2002 from the University of California at Santa Barbara. Upon his graduation he joined the Department of Computer Science at the University of Vermont as an assistant professor. He has been with the computer science faculty there since then. Dr. Arslan's main research interests are on algorithms on strings, computational biology and bioinformatics. Dr. Arslan earned his Master's degree in Computer Science in 1996 from the University of North Texas, Denton, Texas and his Bachelor's degree in Computer Engineering in 1990 from the Middle East Technical University, Ankara, Turkey. He worked as a programmer for the Central Bank of Turkey between 1991 and 1994. Yu He received her B.E. degree in Information Engineering from Zhejiang University, China, in 2001. She is currently a graduate student in the Department of Computer Science at the University of Vermont. Her research interests include data mining, bioinformatics and pattern recognition.