article · 2005

Operator placement for innetwork stream query processing

Utkarsh Srivastava, Kamesh Munagala, Jennifer Widom

Cited by 0Abstract and details only

Abstract

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 ex-ecuting 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 inter-mediate nodes as the data travels to the root. Most previous work on in-network query processing has focused on aggregation and inex-pensive 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 trans-mission is minimized. We show that the problem is tractable, give an optimal algorithm, and demonstrate that a simpler greedy op-erator 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. 1.

Cite this paper

APA 7

Srivastava, U., Munagala, K., & Widom, J. (2005). Operator placement for innetwork stream query processing.

MLA 9

Srivastava, Utkarsh, et al. “Operator placement for innetwork stream query processing.” 2005.

Chicago

Srivastava, Utkarsh, Kamesh Munagala, and Jennifer Widom. 2005. “Operator placement for innetwork stream query processing.”

Harvard

Srivastava, U., Munagala, K. and Widom, J. (2005) ‘Operator placement for innetwork stream query processing’.

BibTeX

@article{srivastava2005operator,
  title = {{Operator placement for innetwork stream query processing}},
  author = {Srivastava, Utkarsh and Munagala, Kamesh and Widom, Jennifer},
  year = {2005}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.