Exact Top-K Queries in Wireless Sensor Networks

In this paper, we consider the exact top-k query problem in wireless sensor networks, i.e., where one seeks to find the k highest reported values as well as the complete set of nodes that reported them. Our primary contribution in this context is EXTOK, a provably correct and topology-independent ne...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2011-10, Vol.23 (10), p.1513-1525
Main Authors: Malhotra, B., Nascimento, M. A., Nikolaidis, I.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Context
energy efficiency
Exact sciences and technology
in-network query processing
Information systems. Data bases
Memory organisation. Data processing
Network topology
Networks
Probes
Queries
Query processing
Sensors
Software
State of the art
Studies
Technical Activities Guide - TAG
top-k query processing
Topology
Trees
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider the exact top-k query problem in wireless sensor networks, i.e., where one seeks to find the k highest reported values as well as the complete set of nodes that reported them. Our primary contribution in this context is EXTOK, a provably correct and topology-independent new filtering-based algorithm for processing exact top-k queries. As a secondary contribution we confirm a previous result of ours by showing that the efficiency of top-k query processing algorithms, including EXTOK, can be further improved by simply choosing a proper underlying logical tree topology. We examine EXTOK's performance with respect to a number of parameters and different logical tree topologies while using both synthetic and real data sets. Our simulation reveal that EXTOK consistently outperforms the current state-of-the-art algorithm by a very significant margin and regardless of the underlying logical tree topology.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2010.186