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

27 Citations (Scopus)

Abstract

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
Pages793-801
Number of pages9
DOIs
Publication statusPublished - 2 Aug 2011
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: 10 Apr 201115 Apr 2011

Conference

ConferenceIEEE INFOCOM 2011
Country/TerritoryChina
CityShanghai
Period10/04/1115/04/11

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this