## 4 Techniques of In-Network Join Processing
### Techniques with Filtering of Non-Joinable Tuples
In each execution, the final join result is computed at the base station. The _ideal_ scenario is that each node of \(R\) and \(S\) sends its tuple \(t\) to the base station if \(t\) is joinable and does not send \(t\) if \(t\) is not. Then, the base station computes the join result with the received tuples. The goal of _CJF_ is to get close to such an ideal scenario as follows:  
At each node, a _join filter_ (or simply a filter) on the joining attribute, say, \(A\), is installed. The filter is represented as an _interval_\([v_{I},\,v_{2}]\) of the values of \(A\). For ease of explanation, let us consider an equi-join query \(q\) on one joining attribute \(A\): \(\mathrm{q}=R\bowtie_{A=A}S\) (_CJF_ can process a theta-join on \(k\) joining attributes. The filter in each node consists of \(k\) intervals, one for each joining attribute. In each execution of \(q\), each node sends its tuple \(t\) to the base station if \(t.A\) is outside (the interval of) the filter. Otherwise, it filters out (does _not_ send) \(t\). The base station computes the final join result with the received tuples. For correctness, however, the base station also checks if the value of \(A\) of any received tuple belongs to the interval of the filter in any node (say, \(N\)) that has not sent its tuple (say, \(u\)). This is called a _collision_, and it indicates the join possibility. If a collision occurs, the base station retrieves the missing tuple \(u\) by requesting \(N\) to send \(u\) to the base station. For this process, the base station needs to keep the filters of all the nodes. In fact, the filters of all the nodes are set by the base station before each execution of \(q\). More description about this will be given shortly. The interval of a filter \([v_{I},\,v_{2}]\) in node \(N\) is set using two values, \(v\) and \(s\): \(v_{I}=v-s/2\), and \(v_{2}=v+s/2\). \(v\) is an estimate (_i.e._, expected value) of \(A\) to be sampled in \(N\). \(s\) is the _filter size_ (_i.e._, the size of the interval). A constraint in setting filters is that the filter intervals of two different nodes should not overlap. This is to ensure that the joinable tuples are not filtered out. For a pair of nodes \(N_{I}\) and \(N_{2}\) for which such a constraint cannot be enforced because the two tuples of \(N_{I}\) and \(N_{2}\) might be joined with each other, the filter is installed neither in \(N_{I}\) nor in \(N_{2}\). That is, both filter sizes are set to 0. Then, \(N_{I}\) and \(N_{2}\) are supposed to send their tuples to the base station. That is, the filter size of a node whose tuple is joinable is set to 0 while that of a node whose tuple is not joinable is set as greater than 0. The communication cost incurred in each execution of \(q\) depends on the filter sizes. Suppose tuple \(t\) produced in node \(N\) is not joinable. If the filter in \(N\) is too small, \(t\) might avoid the filter and be unnecessarily sent to the base station. If it is too large, the risk of collision at the base station getshigher. With this trade-off and the aforementioned constraint being considered, in [24], [PERSON] _et al_. formulated the problem of determining the filter sizes for a given join query as a mathematical optimization problem, and proposed a solution. In _CJF_, the base station computes the optimal filter sizes of all the nodes before each execution of the query. They are notified into the network for the filters to be maintained. In [24], it is assumed that the sensor readings would not drastically change between successive samplings. For example, the temperature in a region would not change much in a short period of time. Thus, the new filter sizes would not be much different from the previous ones. The filter updates are executed at some nodes only if communication cost for the update could be amortized in the next execution of the query. As for the expected value \(v\) of \(A\) to be sampled at node \(N\), the actual measurement would gradually diverge from \(v\) as time elapses.