## 4 Techniques of In-Network Join Processing
### Summary and Assessment  
Table 2 compares the techniques surveyed in Sections 4.2 and 4.3 where each row can be referred to as a summary of the corresponding technique. In Section 3.1, we have described the requirements and challenges in in-network join processing in WSNs. In the following, we assess the surveyed techniques in Table 2 in terms of those requirements and challenges. The major requirements include stream processing, distributed processing, protocol-oriented implementation, and fault-tolerance. **Stream processing. ** Among others, two important challenges are faced in meeting this requirement. One is to process a stream join with limited resources of the sensor nodes, and the other is to collect the statistics on the sensor readings for cost-based optimization. The state-of-the-art techniques have well met the first challenge: Most of the techniques can process stream joins [5; 6; 8; 11; 22; 23]; The periodic executions of a join query can be regarded as a form of stream join [11; 21; 24]; Even the techniques that focus on a one-shot join over static join operand relations could be tailored to support a continuous join over streaming relations [2; 3; 4; 7; 12]. However, only a limited solution to the second challenge has been devised in the state-of-the-art. Most techniques do not employ a cost-based optimization based on the statistics. As for those employing cost formulas, the statistics are assumed to be collected through a learning phase in the processing of a long-running query [4; 11; 21; 22]. **Distributed processing. ** A difficult challenge is to generate an efficient distributed join strategy when each sensor node has limited knowledge of other nodes and the network connectivity. For inter-region joins, the join region is arranged around the center location of the triangle formed by the two regions and the query sink [3; 4; 5; 8; 11; 21]. These techniques could be efficient when joining the sensor readings produced from two small regions of the network that are not overlapping. Other techniques employ the base station as a coordinator of join processing [6; 7; 24]. When all or a majority of the nodes participate in the query, these techniques could be more efficient than those of pure in-network processing because the base station is not resource-constrained. However, it might incur much communication when only small regions of the network distant from the base station participate in the query. The techniques that use geographic hashing distribute query operators over the network [8; 2]. The communication costs of these techniques depend on the hash functions and the distribution of the values to be hashed. The join initiation in [22; 23] is carried out in a distributed way using multiple routing trees. However, it is costly and could be amortized only for a long-running query. \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline
**Techniques** & **Join Pred. ** & **Query Type Supported 1** & **Join Operand** & **Non-Joinable** & **Involvement of** & **Adapted Join** & **Routing** & **Optimization and** \\  & **Pred. ** & **Supported 1** & **Relations 2** & **Tuple Filtering 3** & **Base Station 4** & **Implementation** & **Protocol** & **Other Features** \\ \hline _Distribute-Broadcast Join_ & theta & C, P, L & static, stream & NO & NO & nested-loop join & GPSR, & \begin{tabular}{c} cost-based selection \\ of optimal join \\ region \\ \end{tabular}  \\ \(\begin{array}{c}\text{\small{}}\text{\small{}}\text{\small{}}\text{\small{}} \text