A general framework for efficient continuous multidimensional top-κ query processing in sensor networks

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)

Abstract

Top-κ query has long been a crucial problem in multiple fields of computer science, such as data processing and information retrieval. In emerging 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-κ query processing. From the client's perspective, users may request different sets of information, with different priorities and at different times. Thus, top-κ search should not only be multidimensional, but also be across time domain. From the system's perspective, 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 demands from the two aspects. The sensor network maintains an efficient dominant graph data structure for data readings. A simple top-κ extraction algorithm is used for user query processing and two schemes are proposed to further reduce communication cost. Our methods can be used for top-κ query with any linear convex query function. The framework is adaptive enough to incorporate some advanced features; for example, we show how approximate queries and data aging can be applied. To the best of our knowledge, this is the first work for continuous multidimensional top-κ query processing in sensor networks. Simulation results show that our schemes can reduce the total communication cost by up to 90 percent, compared with a centralized scheme or a straightforward extension from previous top-κ algorithm on 1D sensor data.
Original languageEnglish
Article number6152096
Pages (from-to)1668-1680
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume23
Issue number9
DOIs
Publication statusPublished - 4 Jun 2012

Keywords

  • algorithm/protocol design
  • Sensor networks
  • top-κ extraction

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this