SEMINAR / TUTORIAL

"Distributed Top-K Query Processing in Wireless Sensor Networks"

Demetrios Zeinalipour-Yazti (Open University of Cyprus)

Zografoula Vagena (Microsoft Research Cambridge)

The 9th International Conference on Mobile Data Management (MDM'08)

Beijing, China, April 27-30, 2008

Tutorial Homepage: http://is.ouc.ac.cy/mdm08seminar/

MDM Homepage: http://idke.ruc.edu.cn/mdm2008/seminars.htm

Abstract

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.

Target Audience

The goal of this tutorial is to convey basic and advanced distributed Top-K query processing techniques to its audience. The tutorial is targeted to scientists with a basic understanding of data management, but no knowledge of Top-K ranking algorithms is required. The relevant concepts from database and other middleware information systems will be reviewed in the tutorial. We shall explain the algorithms for conducting distributed Top-K query processing through many examples with animations making the concepts easily comprehendible to a wide range of researchers and practitioners. In particular, this tutorial addresses the following audience:
  1. Graduate and Undergraduate Students
  2. Mobile Data Management Researchers/Educators
  3. Industry Developers
This tutorial fills a big gap compared to previous tutorials on query rankings in databases because it addresses the state-of-the-art in distributed Top-K query processing. At the same time, it takes a holistic view on the theoretical and practical complexities that arise in such algorithms. The topics covered in this tutorial are related, but not limited, to the following tracks of MDM 2008:
  1. Query processing and optimization for mobile users
  2. Data stream processing in mobile/sensor networks
  3. Theoretical foundations of data-intensive mobile computing
  4. Data broadcasting/dissemination in mobile environments

Tutorial Material

Microsoft Powerpoint Slides (16 MB)   

Short Biographies

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/
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.

Contact Details

Demetrios Zeinalipour-Yazti Zografoula Vagena
School of Pure and Applied Sciences Systems and Networking Group
Open University of Cyprus Microsoft Research Cambridge
+357-22-411619 + 44-1223-479700
+357-22-411601 + 44-1223-479999
http://is.ouc.ac.cy/~zeinalipour/ http://research.microsoft.com/