Distributed Top-K Query Processing in Wireless Sensor Networks

Demetrios Zeinalipour-Yazti (Open University of Cyprus)
and Zografoula Vagena (Microsoft Research Cambridge)

Wireless Sensor Networks create an innovative technology that enables users to monitor and study the physical world at an extremely high resolution. Query processing in such ad-hoc environments is a challenging task due to the complexities imposed by the inherent energy and communication constraints. To this end, the research community has proposed to take into account user-defined parameters in order to derive the K most relevant (or Top-K) answers quickly and efficiently. A Top-K query returns the subset of most relevant answers, in place of all answers, for two reasons: i) to minimize the cost metric that is associated with the retrieval of all answers; and ii) to improve the recall and the precision of the answer set, such that the user is not overwhelmed with irrelevant results.

This tutorial presents the fundamental concepts behind distributed Top-K query processing and the adaptations of these algorithms to distributed and wireless sensor networks. It additionally provides a gentle overview of rudimentary and advanced techniques covering a significant body of research in this domain. The tutorial will start out with an overview of the most influential centralized and middleware Top-K query processing algorithms and then proceed with an elaborate description of distributed Top-K ranking algorithms for One-time Top-K Queries, Continuous Top-K Queries and Approximate Top-K Queries. Finally, it will provide an outlook to compelling future applications that can be constructed on the foundation of these algorithms. Although the tutorial is specifically geared towards Wireless Sensor Networks, many of the presented ideas find extensions in other mobile environments such as Adhoc Networks, Vehicular Networks and the Mobile Web.

Dr Demetrios Zeinalipour-Yazti (PhD, University of California, Riverside, 2005) is a Lecturer of Computer Science at the Open University of Cyprus. Before that he was a Visiting Lecturer at the University of Cyprus. He has also spent a research internship at Akamai Technologies (MA, USA). His primary research interests include Distributed Query Processing, Storage and Retrieval Methods for Sensor and Peer-to-Peer Systems and Network Data Management. He is a member of ACM, IEEE and USENIX. For more information, please visit: http://is.ouc.ac.cy/~zeinalipour/

Dr Zografoula Vagena (PhD, University of California, Riverside, 2005) recently joined the Systems and Networking Group of Microsoft Research in Cambridge, UK. Before that she was a Postdoctoral Research Associate at the IBM Almaden Research Center (CA, USA). She has also spent research internships at IBM Almaden Research (CA, USA), AT&T Labs (NJ, USA) and Microsoft Research Redmond (WA, USA). Her primary research interests include Query Processing and Optimization, Text Indexing and Retrieval and XML Data Management. She is a member of ACM.

Economic-based Incentive Schemes for Dynamic Data Management in Mobile P2P Computing

Sanjay Kumar Madria (University of Missouri-Rolla, USA)
and Anirban Mondal (University of Tokyo, Japan)

Data Management in Mobile Peer to Peer (M-P2P) systems needs dynamic data management due to mobility and fragile wireless connection connecting resource constraint devices. Traditional methods of data management and services in mobile P2P environment generally assume all peers to cooperate. Since peer activities in M-P2P are not generally monitored, users assume that they are free to use the resources anyway they like. Under this feeling of freedom, a subset of users (free riders) begins to consume much more resources available on M-P2P than they wish to contribute. In addition, due to the dynamic nature of moving hosts, topology changes very often and traditional schemes fall short in providing reasonable data availability. This becomes much more important in M-P2P where the network communication is generally multi-hop and intermediate peers have to render relay services other than data providers to improve the connectivity. Economic-based incentive schemes have been proposed which may play a better role in inciting free riders to collaborate. The data and service availability can be increased by associating a price with data items and services. In such schemes, peers can bid for better services, intermediate peers can earn incentives by providing relay services and in fact, outgoing peers can lease data items to others to still earn incentives while disconnected. New peers can become data providers by providing hosting services to earn incentives. This tutorial will explore issues involved in managing resources using Economic incentives.

Sanjay Kumar Madria received his Ph.D. in Computer Science from Indian Institute of Technology, Delhi, India in 1995. He is an Associate Professor, Department of Computer Science at the University of Missouri-Rolla, USA. Earlier he was Visiting Assistant Professor in the Department of Computer Science, Purdue University, West Lafayette, USA. He has published more than 120 Journal and conference papers in the areas of mobile and sensor data management. He has organized International conferences, workshops and presented tutorials in the areas of mobile computing. He has given invited talks and served as panelists in National Science Foundation, USA and Swedish Research Council. His research is supported by NSF, DOE, UMRB and industrial grants for over $1.2M. He was awarded JSPS fellowship in 2006 and University of Missouri-Rolla's Faculty Excellence award in 2007. He is IEEE Senior Member.

Anirban Mondal received his Ph.D.degree in 2002 from the National University of Singapore. He is currently doing research at the Center for Information Fusion, University of Tokyo, Japan . He has publications in several international conferences and workshops. He has participated in the program committee of several international conferences and acted as a reviewer for journals such as IEEE TKDE. His research interests include spatial databases, clusters, spatial indexing, peer-to-peer computing, GRID computing, load-balancing in distributed systems, and mobile computing.