BF-k: a Near-optimal Operator Placement Algorithm for In-network Query Processing
For a query committed on a node on ad-hoc networks, the data and the relational operations related to the query are distributed widely around the autonomous nodes in the underlying network. Under that condition, in-network query processing is most efficient query evaluation strategy which actually places a tree of relational operators such as filters (joins) and aggregations onto nodes so as to minimize the amount of data transmitted in the network for the query evaluation. Thus the challenge of performing in-network query processing goes to the resolution of the operator placement problem, this paper proposes a kind of decentralized and adaptive operator placement algorithm BF-k, which reduces greatly the time complexity of a near-optimal placement of a large number of relational operators for an in-network query processing. The performance of BF-k is also explored in this paper.