## 4 Techniques of In-Network Join Processing
### Techniques with Filtering of Non-Joinable Tuples
The update of \(v\) is triggered whenever a tuple is sent from \(N\) to the base station (_i.e.,_ not filtered out). The new value is computed using a _linear regression model_ with \(k\) recent values received at the base station. According to the experiments in [24], this model works well with \(k=6\). This implies that _CJF_ can adapt to the trend of the sensor readings early enough. _CJF_ can be employed in the applications where an estimate of the sensor readings of each joining attribute could be provided, and also the sensor readings would not change much between successive samplings. _Progressive Energy-efficient Join Algorithm (PEJA)._ In [5], [PERSON] _et al_. proposed _PEJA_ to answer a continuous join query. It executes an inter-region equi-join \(R\bowtie_{A=B}S\). The join processing proceeds as follows: In region \(R\) (\(S\)), a routing tree is constructed. In \(R\) (\(S\)), the value range of \(A\) (\(B\)) is divided into subranges. Each node of \(R\) (\(S\)) counts the number of value occurrences in \(R\).\(A\) (\(S\).\(B\)) for each subrange, making the _node histogram_ which consists of a series of _(subrange, count)_ pairs for that node. The node histograms are gathered at the root through the routing tree, and the root merges them to generate the _region histogram_ which consists of a series of _(subrange, count)_ pairs for that region. The two region histograms are sent to the node \(c_{T}\), which is located at the midpoint between the two roots of the routing trees. In \(c_{T}\), for each matching subrange pair, joinability for the subrange is checked. For example, if the count of a subrange [\(v_{1}\), \(v_{2}\)] is not 0 in one region but that of the same subrange of the other region is 0, then there would be _no_ join result for the subrange [\(v_{1}\), \(v_{2}\)]. If both counts are non-zero, the join result is regarded to exist for [\(v_{1}\), \(v_{2}\)] though this judgment would turn out to be a _false hit_. For the non-joinable subranges, the corresponding tuples of \(R\) and \(S\) are filtered out. Because of the false hits, such reductions of \(R\) and \(S\) are only _partial_. For each pair of joinable subranges, a strategy of in-network join processing is set up depending on the two counts. For example, if one count is high but the other one is very low, then the probability of the join result to be produced in that subrange could be low. If both counts are high, the probability could be high. Based on such a heuristic, a proper join strategy is selected and executed as follows. The tuples of \(R\) that have survived are partitioned and replaced through geographic hashing. The region \(R\) is divided into _grids_ where a grid is a rectangular geographic region of the network that comprises a set of sensor nodes. A subrange of \(R\).\(A\) is mapped to the grids proportionally depending on the number of tuples in the subrange. For \(I\) which is a subrange of \(A\), those tuples of \(R\) whose \(R\).\(A\) belongs to \(I\) are sent to the grid \(g\) allocated for \(I\). The same partitioning and replacement is conducted in region \(S\) for \(B\) as well, and the matching grid \(g^{\prime}\)for \(I\) in \(S\) is called the _mirror grid_ of \(g\). Now the join tuple matching is carried out only between a grid and its mirror grid as in the conventional hash join. For each subrange \(I\), the grid with less number of tuples send their tuples to its mirror grid where the final join is conducted. The matched tuples are sent to the base station for the final result. Each node of a grid \(g\) maintains a join filter \(F_{J}\) that stores the joining attribute values in the mirror grid of \(g\). \(F_{J}\) is consulted in filtering out the non-joinable tuples in \(g\). The joinable tuples of \(g\) matched through \(F_{J}\) are sent to the base station, and \(F_{J}\) of \(g\)'s mirror grid is updated accordingly. _PEJA_ can be regarded as an adaptation of the conventional _sort-merge_ join, though _no_ physical sorting of the tuples on the joining attribute is carried out in the network.