Skip to main content

Operator placement for in-network stream query processing

Publication ,  Journal Article
Srivastaya, U; Munagala, K; Widom, J
Published in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
December 1, 2005

In sensor networks, data acquisition frequently takes place at low-capability devices. The acquired data is then transmitted through a hierarchy of nodes having progressively increasing network band-width and computational power. We consider the problem of executing queries over these data streams, posed at the root of the hierarchy. To minimize data transmission, it is desirable to perform "in-network" query processing: do some part of the work at intermediate nodes as the data travels to the root. Most previous work on in-network query processing has focused on aggregation and inexpensive filters. In this paper, we address in-network processing for queries involving possibly expensive conjunctive filters, and joins. We consider the problem of placing operators along the nodes of the hierarchy so that the overall cost of computation and data transmission is minimized. We show that the problem is tractable, give an optimal algorithm, and demonstrate that a simpler greedy operator placement algorithm can fail to find the optimal solution. Finally we define a number of interesting variations of the basic operator placement problem and demonstrate their hardness. Copyright 2005 ACM.

Duke Scholars

Published In

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Publication Date

December 1, 2005

Start / End Page

250 / 258
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Srivastaya, U., Munagala, K., & Widom, J. (2005). Operator placement for in-network stream query processing. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 250–258.
Srivastaya, U., K. Munagala, and J. Widom. “Operator placement for in-network stream query processing.” Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, December 1, 2005, 250–58.
Srivastaya U, Munagala K, Widom J. Operator placement for in-network stream query processing. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2005 Dec 1;250–8.
Srivastaya, U., et al. “Operator placement for in-network stream query processing.” Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Dec. 2005, pp. 250–58.
Srivastaya U, Munagala K, Widom J. Operator placement for in-network stream query processing. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2005 Dec 1;250–258.

Published In

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Publication Date

December 1, 2005

Start / End Page

250 / 258