Supporting asynchronous update for distributed data cubes

摘要

Fast and simultaneous retrieval of aggregate sums (or averages) from multiple regions in a wireless sensor network can be achieved by constructing a distributed data cube (DDC). However, the prior work focused on maintaining a DDC by a globally synchronous protocol, which is not flexible for a large-scale sensor network. In this paper, we propose a more general DDC (GDDC), which supports asynchronous DDC updates. By using the proposed GDDC, only O(n~(1/2)) nodes need to be visited to compute an aggregate sum (or average) query over a rectangular region with n nodes. First, we develop the fundamental semantics for aggregate queries in a system model without a synchronized clock. Second, we define the concept of consistency and derive a set of theorems to guarantee correct query results. Third, we design new distributed algorithms to implement a GDDC. Finally, we evaluate the proposed techniques by extensive experiments. Many interesting impact factors of query accuracy have also been analyzed.