Continuous multi-dimensional top-κ query processing in sensor networks

Hongbo Jiang, Jie Cheng, Dan Wang, Chonggang Wang, Guang Tan

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

33 Citations (Scopus)


Top-κ query has long been an important topic in many fields of computer science. Efficient implementation of the top-k queries is the key for information searching. With the new frontier such as the cyber-physical systems, where there can be a large number of users searching information directly into the physical world, many new challenges arise for top-k query processing. From the client's perspective, different users may request different set of information, with different priorities and at different times. Thus, the top-k search not only should be multi-dimensional, but also across time domain. From the system's perspective, the data collection is usually carried out by small sensing devices. Unlike the data centers used for searching in the cyber-space, these devices are often extremely resource-constrained and system efficiency is of paramount importance. In this paper, we develop a framework that can effectively satisfy the two ends. The sensor network maintains an efficient dominant graph data structure for data readings. A simple top-k extraction algorithm is used for the user query processing and two schemes are proposed to further reduce communication cost. Our proposed methods can be used for top-k query with any linear convex query function. To the best of our knowledge, this is the first work for continuous multi-dimensional top-k query processing in sensor networks; and our simulation results show that our schemes can reduce the total communication cost by up to 90%, compared with the centralized scheme or a straightforward extension from previous top-k algorithm on one-dimensional sensor data.
Original languageEnglish
Title of host publication2011 Proceedings IEEE INFOCOM
Number of pages9
Publication statusPublished - 2 Aug 2011
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: 10 Apr 201115 Apr 2011


ConferenceIEEE INFOCOM 2011

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Continuous multi-dimensional top-κ query processing in sensor networks'. Together they form a unique fingerprint.

Cite this