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     

Automatically and Accurately Conflating Raster Maps with Orthoimagery

Recent growth of geospatial information online has made it possible to access various maps and orthoimagery. Conflating these maps and imagery can create images that combine the visual appeal of imagery with the attribution information from maps. The existing systems require human intervention to conflate maps with imagery. We present a novel approach that utilizes vector datasets as “glue” to automatically conflate street maps with imagery. First, our approach extracts road intersections from imagery and maps as control points. Then, it aligns the two point sets by computing the matched point pattern. Finally, it aligns maps with imagery based on the matched pattern. The experiments show that our approach can conflate various maps with imagery, such that in our experiments on TIGER-maps covering part of St. Louis county, MO, 85.2% of the conflated map roads are within 10.8 m from the actual roads compared to 51.7% for the original and georeferenced TIGER-map roads.

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.     

Adaptive receiver-driven streaming from multiple senders

This paper presents the design and evaluation of an adaptive streaming mechanism from multiple senders to a single receiver in Peer-to-Peer (P2P) networks, called P2P Adaptive Layered Streaming, or PALS. PALS is a receiver-driven mechanism. It enables a receiver peer to orchestrate quality adaptive streaming of a single, layer-encoded video stream from multiple congestion-controlled senders, and is able to support a spectrum of noninteractive streaming applications. The primary challenge in the design of a streaming mechanism from multiple senders is that available bandwidth from individual peers is not known a priori, and could significantly change during delivery. In PALS, the receiver periodically performs quality adaptation based on the aggregate bandwidth from all senders to determine: (i) the overall quality (i.e number of layers) that can be collectively delivered by all senders, and more importantly (ii) the specific subset of packets that should be delivered by individual senders in order to gracefully cope with any sudden change in their bandwidth. Our detailed simulation-based evaluations illustrate that PALS can effectively cope with several angles of dynamics in the system including: bandwidth variations, peer participation, and partially available content at different peers. We also demonstrate the importance of coordination among senders and examine key design tradeoffs for the PALS mechanism. Nazanin Magharei is currently a PhD student in the Computer Science Department at the University of Oregon. She received her BSc degree in Electrical Engineering from Sharif University of Technology, Iran in 2002. Her research interests include Peer-to-Peer streaming and multimedia caching. Reza Rejaie is currently an Assistant Professor at the Department of Computer and Information Science at the University of Oregon. From October 1999 to March 2002, he was a Senior Technical Staff member at AT&T Labs-Research in Menlo Park, California. He received a NSF CAREER Award for his work on P2P streaming in 2005. Reza has served on the editorial board of IEEE Communications Surveys & Tutorials, as well as the program committee of major networking conferences including INFOCOM, ICNP, Global Internet, ACM Multimedia, IEEE Multimedia, NOSSDAV, ICDCS, and MMCN. Reza received his MS and PhD degrees in Computer Science from the University of Southern California (USC) in 1996 and 1999, and his BS degree in Electrical Engineering from the Sharif University of Technology (Tehran, Iran) in 1991, respectively. Reza has been a member of both the ACM and IEEE since 1997.     

Processing Optimal Sequenced Route Queries Using Voronoi Diagrams

The Optimal Sequenced Route (OSR) query strives to find a route of minimum length starting from a given source location and passing through a number of typed locations in a specific sequence imposed on the types of the locations. In this paper, we propose a pre-computation approach to OSR query in both vector and metric spaces. We exploit the geometric properties of the solution space and theoretically prove its relation to additively weighted Voronoi diagrams. Our approach recursively accesses these diagrams to incrementally build the OSR. Introducing the analogous diagrams for the space of road networks, we show that our approach is also efficiently applicable to this metric space. Our experimental results verify that our pre-computation approach outperforms the previous index-based approaches in terms of query response time. This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC), IIS-0238560 (PECASE), IIS-0324955 (ITR), IIS-0534761, and unrestricted cash gifts from Google and Microsoft. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the NSF.

---

A QoS-Enabled Transmission Scheme for MPEG Video Streaming

While MPEG is the de facto encoding standard for video services, online video streaming service is becoming popular over the open network such as the Internet. As the performance of open network is non-predictable and uncontrollable, the tuning of the quality of service (QoS) for on-line video streaming services is difficult. In order to provide better QoS for the delivery of videos, there are proposals of new encoding formats or new transmission protocols for on-line video streaming. However, these results are not compatible with popular video players or network protocols and hence these approaches are so far not very successful. We use another approach which tries to by-pass these problems. We designed a QoS Tuning Scheme and a QoS-Enabled Transmission Scheme for transmitting MPEG videos from video servers to clients. According to the traffic characteristics between the video server and each individual client, the QoS Tuning Scheme tunes the QoS to be delivered to each individual client on the fly. Furthermore, our QoS-Enabled Transmission Scheme can be applied over any protocol, such as HTTP which is the most popular protocol over the open network. With our transmission scheme, bandwidth can be better utilized by reducing transmitted frames which would have missed their deadlines and would eventually be discarded by the clients. This is achieved by sending frames according to their impact on the QoS in the playback under the allowed throughput. With these schemes, users can enjoy video streaming through their favorite video players and with the best possible QoS. In order to facilitate the real time QoS tuning, a metric, QoS-GFS, is developed. This QoS-GFS is extended from the QoS-Index, another metric which has taken human perspective in the measurement of video quality. Hence QoS-GFS is better than the common metrics which measures QoS by means of rate of transmission of bytes or MPEG frames. We designed and implemented a middleware to perform empirical tests of the proposed transmission scheme and QoS tuning scheme. Experiment results show that our schemes can effectively enhance the QoS for online MPEG video streaming services. The work reported in this paper was supported in part by the RGC Earmarked Research Grant under RGC HKBU 2074/01E, and by the FRG under FRG 00-01/I. Joseph Kee-Yin Ng received a B.Sc. in Mathematics and Computer Science, a M.Sc. in Computer Science, and a Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in the years 1986, 1988, and 1993, respectively. Dr. Ng is currently an associate professor in the Department of Computer Science at Hong Kong Baptist University. His current research interests includes Real-Time Networks, Multimedia Communications, Ubiquitous/Pervasive Computing, Mobile and Location-aware Computing, Performance Evaluation, Parallel and Distributed Computing. Dr. Ng is the Technical Program Chair for TENCON 2006, General Chair for The 11th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2005), Program Vice Chair for The 11th International Conference on Parallel and Distributed Systems (ICPADS 2005), Program Area-Chair for The 18th & 19th International Conference on Advanced Information Networking and Applications (AINA 2004 & AINA 2005) and he had served as the General Co-Chair for The International Computer Congress 1999 & 2001 (ICC'99 & ICC'01), the Program Co-Chair for The Sixth International Conference on Real-Time Computing Systems and Applications (RTCSA'99) and the General Co-Chair for The 1999 and 2001 International Computer Science Conference (ICSC'99 & ICSC'01). Dr. Ng is a member of the Editorial Board of Journal of Pervasive Computing and Communications, Associate Editor of Real-Time Systems Journal and Journal of Mobile Multimedia. He is a guest editor of International Journal of Wireless and Mobile Computing for a special issue on Applications, Services, and Infrastructures for Wireless and Mobile Computing. Dr. Ng is currently the Region 10 Coordinator for the Chapter Activities Board of the IEEE Computer Society, and is the Coordinator of the IEEE Computer Society Distinguished Visitors Program (Asia/Pacific). He is a senior member of the IEEE and has been a member of the IEEE Computer Society since 1991. Dr. Ng has been an exco-member (1993–95), General Secretary (1995–1997), Vice-Chair (1997–1999), Chair (1999–2001) and is the immediate past Chairman of the IEEE, Hong Kong Section, Computer Chapter. Dr. Ng received the Certificate of Appreciation for Leadership and Service (2000–2001) from IEEE Region 10 and the IEEE Meritorious Service Award from IEEE Computer Society at 2004. He is also a member of the IEEE Communication Society, and ACM. Karl R.P.H. Leung received his Ph.D. from The University of Hong Kong. He is currently a Principal Lecturer in the Department of Information and Communications Technology at the Hong Kong Institute of Vocational Education (IVE). He is the founder of the Compuware Software Testing Laboratory in the IVE with a donation from the Compuware Asia Pacific Co. Ltd. His research areas include: domain modeling, mission critical software engineering methodology, secure workflow systems, GSM-based location estimation, and QoS of MPEG streaming. He is a Senior Member of the IEEE and IEEE Computer Society, and has held major office of the IEEE Hong Kong Section Computer Chapter. While he was the chairman in 1998, the Chapter won the IEEE Most Outstanding Computer Society Chapter Award. He is also a Chartered Engineer of Engineering Council (UK), a Chartered Information Systems Engineer of British Computer Society (UK), an Engineer of Hong Kong Institution of Engineers, Registered Professional Engineer (Information) of Hong Kong Engineers Registration Board, and a member of ACM, BCS, ACS, HKIE and HKCS. Calvin Kin Cheung Hui received a B.Sc. (First Class Honours) in Computer Science, and a M.Phil. degree in Computer Science from Hong Kong Baptist University in the years 1999, and 2002, respectively. Mr. Hui's research interests includes Real-Time Networks, VoD Systems, Video Streaming, Multimedia Communication, and Distributed Systems Performance Evaluation.     

Scheduling real-time requests in on-demand data broadcast environments

On-demand broadcast is an attractive data dissemination method for mobile and wireless computing. In this paper, we propose a new online preemptive scheduling algorithm, called PRDS that incorporates urgency, data size and number of pending requests for real-time on-demand broadcast system. Furthermore, we use pyramid preemption to optimize performance and reduce overhead. A series of simulation experiments have been performed to evaluate the real-time performance of our algorithm as compared with other previously proposed methods. The experimental results show that our algorithm substantially outperforms other algorithms over a wide range of workloads and parameter settings. The work described in this paper was partially supported by grants from CityU (Project No. 7001841) and RGC CERG Grant No. HKBU 2174/03E. This paper is an extended version of the paper “A preemptive scheduling algorithm for wireless real-time on-demand data broadcast” that appeared in the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Victor C. S. Lee received his Ph.D. degree in Computer Science from the City University of Hong Kong in 1997. He is now an Assistant Professor in the Department of Computer Science of the City University of Hong Kong. Dr. Lee is a member of the ACM, the IEEE and the IEEE Computer Society. He is currently the Chairman of the IEEE, Hong Kong Section, Computer Chapter. His research interests include real-time data management, mobile computing, and transaction processing. Xiao Wu received the B.Eng. and M.S. degrees in computer science from Yunnan University, Kunming, China, in 1999 and 2002, respectively. He is currently a Ph.D. candidate in the Department of Computer Science at the City University of Hong Kong. He was with the Institute of Software, Chinese Academy of Sciences, Beijing, China, between January 2001 and July 2002. From 2003 to 2004, he was with the Department of Computer Science of the City University of Hong Kong, Hong Kong, as a Research Assistant. His research interests include multimedia information retrieval, video computing and mobile computing. Joseph Kee-Yin NG received a B.Sc. in Mathematics and Computer Science, a M.Sc. in Computer Science, and a Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in the years 1986, 1988, and 1993, respectively. Prof. Ng is currently a professor in the Department of Computer Science at Hong Kong Baptist University. His current research interests include Real-Time Networks, Multimedia Communications, Ubiquitous/Pervasive Computing, Mobile and Location- aware Computing, Performance Evaluation, Parallel and Distributed Computing. Prof. Ng is the Technical Program Chair for TENCON 2006, General Co-Chair for The 11th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2005), Program Vice Chair for The 11th International Conference on Parallel and Distributed Systems (ICPADS 2005), Program Area-Chair for The 18th & 19th International Conference on Advanced Information Networking and Applications (AINA 2004 & AINA 2005), General Co-Chair for The International Computer Congress 1999 & 2001 (ICC’99 & ICC’01), Program Co-Chair for The Sixth International Conference on Real-Time Computing Systems and Applications (RTCSA’99) and General Co-Chair for The 1999 and 2001 International Computer Science Conference (ICSC’99 & ICSC’01). Prof. Ng is a member of the Editorial Board of Journal of Pervasive Computing and Communications, Journal of Ubiquitous Computing and Intelligence, Journal of Embedded Computing, and Journal of Microprocessors and Microsystems. He is the Associate Editor of Real-Time Systems Journal and Journal of Mobile Multimedia. He is also a guest editor of International Journal of Wireless and Mobile Computing for a special issue on Applications, Services, and Infrastructures for Wireless and Mobile Computing. Prof. Ng is currently the Region 10 Coordinator for the Chapter Activities Board of the IEEE Computer Society, and is the Coordinator of the IEEE Computer Society Distinguished Visitors Program (Asia/Pacific). He is a senior member of the IEEE and has been a member of the IEEE Computer Society since 1991. Prof. Ng has been an Exco-member (1993–95), General Secretary (1995–1997), Vice-Chair (1997–1999), Chair (1999–2001) and the Past Chair of the IEEE, Hong Kong Section, Computer Chapter. Prof. Ng received the Certificate of Appreciation for Services and Contribution (2004) from IEEE Hong Kong Section, the Certificate of Appreciation for Leadership and Service (2000–2001) from IEEE Region 10 and the IEEE Meritorious Service Award from IEEE Computer Society at 2004. He is also a member of the IEEE Communication Society, ACM and the Founding Member for the Internet Society (ISOC)-Hong Kong Chapter.     

An Integrated Framework for Semantic Annotation and Adaptation

Tools for the interpretation of significant events from video and video clip adaptation can effectively support automatic extraction and distribution of relevant content from video streams. In fact, adaptation can adjust meaningful content, previously detected and extracted, to the user/client capabilities and requirements. The integration of these two functions is increasingly important, due to the growing demand of multimedia data from remote clients with limited resources (PDAs, HCCs, Smart phones). In this paper we propose an unified framework for event-based and object-based semantic extraction from video and semantic on-line adaptation. Two cases of application, highlight detection and recognition from soccer videos and people behavior detection in domotic^* applications, are analyzed and discussed.Domotics is a neologism coming from the Latin word domus (home) and informatics.Marco Bertini has a research grant and carries out his research activity at the Department of Systems and Informatics at the University of Florence, Italy. He received a M.S. in electronic engineering from the University of Florence in 1999, and Ph.D. in 2004. His main research interest is content-based indexing and retrieval of videos. He is author of more than 25 papers in international conference proceedings and journals, and is a reviewer for international journals on multimedia and pattern recognition.Rita Cucchiara (Laurea Ingegneria Elettronica, 1989; Ph.D. in Computer Engineering, University of Bologna, Italy 1993). She is currently Full Professor in Computer Engineering at the University of Modena and Reggio Emilia (Italy). She was formerly Assistant Professor (‘93–‘98) at the University of Ferrara, Italy and Associate Professor (‘98–‘04) at the University of Modena and Reggio Emilia, Italy. She is currently in the Faculty staff of Computer Engenering where has in charges the courses of Computer Architectures and Computer Vision.Her current interests include pattern recognition, video analysis and computer vision for video surveillance, domotics, medical imaging, and computer architecture for managing image and multimedia data.Rita Cucchiara is author and co-author of more than 100 papers in international journals, and conference proceedings. She currently serves as reviewer for many international journals in computer vision and computer architecture (e.g. IEEE Trans. on PAMI, IEEE Trans. on Circuit and Systems, Trans. on SMC, Trans. on Vehicular Technology, Trans. on Medical Imaging, Image and Vision Computing, Journal of System architecture, IEEE Concurrency). She participated at scientific committees of the outstanding international conferences in computer vision and multimedia (CVPR, ICME, ICPR, ...) and symposia and organized special tracks in computer architecture for vision and image processing for traffic control. She is in the editorial board of Multimedia Tools and Applications journal. She is member of GIRPR (Italian chapter of Int. Assoc. of Pattern Recognition), AixIA (Ital. Assoc. Of Artificial Intelligence), ACM and IEEE Computer Society.Alberto Del Bimbo is Full Professor of Computer Engineering at the Università di Firenze, Italy. Since 1998 he is the Director of the Master in Multimedia of the Università di Firenze. At the present time, he is Deputy Rector of the Università di Firenze, in charge of Research and Innovation Transfer. His scientific interests are Pattern Recognition, Image Databases, Multimedia and Human Computer Interaction. Prof. Del Bimbo is the author of over 170 publications in the most distinguished international journals and conference proceedings. He is the author of the “Visual Information Retrieval” monography on content-based retrieval from image and video databases edited by Morgan Kaufman. He is Member of IEEE (Institute of Electrical and Electronic Engineers) and Fellow of IAPR (International Association for Pattern Recognition). He is presently Associate Editor of Pattern Recognition, Journal of Visual Languages and Computing, Multimedia Tools and Applications Journal, Pattern Analysis and Applications, IEEE Transactions on Multimedia, and IEEE Transactions on Pattern Analysis and Machine Intelligence. He was the Guest Editor of several special issues on Image databases in highly respected journals.Andrea Prati (Laurea in Computer Engineering, 1998; PhD in Computer Engineering, University of Modena and Reggio Emilia, 2002). He is currently an assistant professor at the University of Modena and Reggio Emilia (Italy), Faculty of Engineering, Dipartimento di Scienze e Metodi dell’Ingegneria, Reggio Emilia. During last year of his PhD studies, he has spent six months as visiting scholar at the Computer Vision and Robotics Research (CVRR) lab at University of California, San Diego (UCSD), USA, working on a research project for traffic monitoring and management through computer vision. His research interests are mainly on motion detection and analysis, shadow removal techniques, video transcoding and analysis, computer architecture for multimedia and high performance video servers, video-surveillance and domotics. He is author of more than 60 papers in international and national conference proceedings and leading journals and he serves as reviewer for many international journals in computer vision and computer architecture. He is a member of IEEE, ACM and IAPR.     

Web data retrieval: solving spatial range queries using k-nearest neighbor searches

As Geographic Information Systems (GIS) technologies have evolved, more and more GIS applications and geospatial data are available on the web. Spatial objects in a given query range can be retrieved using spatial range query − one of the most widely used query types in GIS and spatial databases. However, it can be challenging to retrieve these data from various web applications where access to the data is only possible through restrictive web interfaces that support certain types of queries. A typical scenario is the existence of numerous business web sites that provide their branch locations through a limited “nearest location” web interface. For example, a chain restaurant’s web site such as McDonalds can be queried to find some of the closest locations of its branches to the user’s home address. However, even though the site has the location data of all restaurants in, for example, the state of California, it is difficult to retrieve the entire data set efficiently due to its restrictive web interface. Considering that k-Nearest Neighbor (k-NN) search is one of the most popular web interfaces in accessing spatial data on the web, this paper investigates the problem of retrieving geospatial data from the web for a given spatial range query using only k-NN searches. Based on the classification of k-NN interfaces on the web, we propose a set of range query algorithms to completely cover the rectangular shape of the query range (completeness) while minimizing the number of k-NN searches as possible (efficiency). We evaluated the efficiency of the proposed algorithms through statistical analysis and empirical experiments using both synthetic and real data sets.

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.     

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.     

One-bit algorithms

Many algorithms in distributed systems assume that the size of a single message depends on the number of processors. In this paper, we assume in contrast that messages consist of a single bit. Our main goal is to explore how the one-bit translation of unbounded message algorithms can be sped up by pipelining. We consider two problems. The first is routing between two processors in an arbitrary network and in some special networks (ring, grid, hypercube). The second problem is coloring a synchronous ring with three colors. The routing problem is a very basic subroutine in many distributed algorithms; the three coloring problem demonstrates that pipelining is not always useful. Amotz Bar-Noy received his B.Sc. degree in Mathematics and Computer Science in 1981, and his Ph.D. degree in Computer Science in 1987, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1989 he was a post-doctoral fellow in the Department of Computer Science at Stanford University. He is currently a visiting scientist at the IBM Thomas J. Watson Research Center. His current research interests include the theoretical aspects of distributed and parallel computing, computational complexity and combinatorial optimization. Joseph (Seffi) Naor received his B.A. degree in Computer Science in 1981 from the Technion, Israel Institute of Technology. He received his M.Sc. in 1983 and Ph.D. in 1987 in Computer Science, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1988 he was a post-doctoral fellow at the University of Southern California, Los Angeles, CA. Since 1988 he has been a post-doctoral fellow in the Department of Computer Science at Stanford University. His research interests include combinatorial optimization, randomized algorithms, computational complexity and the theoretical aspects of parallel and distributed computing. Moni Naor received his B.A. in Computer Science from the Technion, Israel Institute of Technology, in 1985, and his Ph.D. in Computer Science from the University of California at Berkeley in 1989. He is currently a visiting scientist at the IBM Almaden Research Center. His research interests include computational complexity, data structures, cryptography, and parallel and distributed computation.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731Supported by contract ONR N00014-88-K-0166 and by a grant from Stanford's Center for Integrated Systems. This work was done while the author was a post-doctoral fellow at the University of Southern California, Los Angeles, CAThis work was done while the author was with the Computer Science Division, University of California at Berkeley, and Supported by NSF grant DCR 85-13926     

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.     

Zikimi: A Case Study in Micro Kernel Design for Multimedia Applications

Due to recent rapid deployment of Internet Appliances and PostPC products, the importance of developing lightweight embedded operating system is being emphasized more. In this article, we like to present the details of design and implementation experience of low cost embedded system, Zikimi, for multimedia data processing. We use the skeleton of existing Linux operating system and develop a micro-kernel to perform a number of specific tasks efficiently and effectively. Internet Appliances and PostPC products usually have very limited amount of hardware resources to execute very specific tasks. We carefully analyze the system requirement of multimedia processing device. Weremove the unnecessary features, e.g. virtual memory, multitasking, a number of different file systems, and etc. The salient features of Zikimi micro kernel are (i) linear memory system and (ii) user level control of I/O device. The result of performance experiment shows that LMS (linear memory system) of Zikimi micro kernel achieves significant performance improvement on memory allocationagainst legacy virtual memory management system of Linux. By exploiting the computational capability of graphics processor and its local memory, we achieve 2.5 times increase in video processing speed. Supported by KOSEF through Statistical Research Center for Complex Systems at Seoul National University. Funded by Faculty Research Institute Program 2001, Sahmyook University, Korea. Sang-Yeob Lee received his B.S. and M.S degree from Hanyang University, seoul, Korea in 1995. He is currently working towards the Ph.D. degree in Devision of Electrical and Computer Engineering, Hanyang University, Seoul, Korea. Since 1998, he has been on the faculty of Information Management System at Sahmyook university, Seoul, Korea. His research interests include robot vision systems, pattern recognition, Multimedia systems. He is a member of IEEE. Youjip Won received the B.S and M.S degree in Computer Science from the Department of Computer Science, Seoul National University, Seoul, Korea in 1990 and 1992, respectively and the Ph.D. in Computer Science from the University of Minnesota, Minneapolis in 1997. After finishing his Ph.D., He worked as Server Performance Analysts at Server Architecture Lab., Intel Corp. Since 1999, he has been on the board of faculty members in Division of Electrical and Computer Engineering, Hanyang University, Seoul, Korea. His current research interests include Multimedia Systems, Internet Technology, Database and Performance Modeling and Analysis. He is a member of ACM and IEEE. Whoi-Yul Kim received his B.S. degree in Electronic Engineering from Hanyang University, Seoul, Korea in 1980. He received his M.S. from Pennsylvania State University, University Park, in 1983 and his Ph.D. from Purdue University, West Lafayette, in 1989, both in Electrical Engineering. From 1989 to 1994, he was with the Erick Jonsson School of Engineering and Computer Science at the University of Texas at Dallas. Since 1994, he has been on the faculty of Electronic Engineering at Hanyang University, Seoul, Korea. He has been involved with research development of various range sensors and their use in robot vision systems. Recently, his work has focused on content-based image retrieval system. He is a member of IEEE.     

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.     

Privacy preservation for data cubes

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