## 4 Techniques of In-Network Join Processing
### Techniques with Filtering of Non-Joinable Tuples
proposed _SENS-Join_ to answer a one-shot join query \(q=R\bowtie S\) whose join condition could be any form of _arbitrary predicates_ on \(n\) joining attributes. In [7], the sensor relations \(R\) and \(S\) are modeled as storing one tuple per node (_i.e._, the most recent measurement). The result of \(q\) is obtained in three steps after all the sensor nodes relevant to \(q\) form a routing tree with the base station as the root:  
* **Step 1. ** All the joining attribute values are collected at the base station, where the join condition is checked to filter out non-joinable values. * **Step 2. ** The _join filter_ consisting of those values that have survived is constructed and broadcast to the network, where each node filters out non-joinable tuples by looking up the join filter. * **Step 3. ** The remaining tuples considered joinable are sent to the base station where the final join is conducted. In the first two steps, the joining attribute values are sent or broadcast in an _encoded_ and _indexed_ form for considerable reduction of communication cost. The data structure employed for compact representation of the joining attribute values is a _quadtree_[36] constructed in connection with _Z-ordering_[37]. The encoding works based on the _quantization_ of joining attribute values as follows: Suppose there are \(n\) joining attributes in \(q\). Each tuple can have up to \(n\) joining attribute values, which are mapped to a point in the \(n\)-dimensional space. For each dimension, its value range is divided into subranges of equal size. The number of subranges is a priori determined at the base station depending on the resolution of the dimension to be supported, and disseminated to the network independent of \(q\). Then, a point in the \(n\)-dimensional space belongs to an \(n\)-dimensional cell. Each cell is numbered in Z-ordering (_i.e._, assigned a _Z-number_), a technique which maps multi-dimensional data to  
Figure 10: Z-ordering and its application for encoding joining attribute values. **(a)**\(Z\)-numbers in bits. The bit string in a cell is obtained through bit interleaving: one bit from \(x\)-dimension, and the next bit from \(y\)-dimension, and so on; **(b)**\(Z\)-numbers in decimal; **(c)** Relation \(R\) with 2 joining attributes \(X\) and \(Y\), where value range of \(X\) is [0, 399] and that of \(Y\) is [0, 399]. Their subranges are specified in (d); **(d)** Mapping of the tuples of \(R\) in (c) to the marked cells of the 2-dimensional space. one-dimensional data while preserving data locality. Figure 10 shows an example of Z-ordering for 2-dimensional cells and its application for encoding joining attribute values. Now a tuple \(t\) (to be exact, the \(n\) joining attribute values of \(t\)) is mapped to a Z-number. The Z-numbers of all the tuples are represented in a quadtree, which is known to be efficiently constructed in connection with Z-ordering. Due to the _discrete_ quantization of joining attribute values as described above, accuracy could be sacrificed in the first two steps while not undermining the correctness of the final join result in the third step. The degree of reduction of the join operand relation would be partial to full depending on the resolutions supported in encoding the join attribute values. It could be full reduction if the supported resolutions cover all the exact values of the joining attributes. _SENS-Join_ requires the routing tree to be stable throughout the execution of a query. In _SENS-Join_, link failure is handled. If a link fails during the execution of a query, the routing tree is repaired to be restructured. Then, the query is re-executed. _Continuous Join Filtering (CJF)_. In [24], [PERSON] _et al_. proposed _CJF_ to answer a continuous join query. It periodically executes a theta-join query \(q=R\bowtie S\). Each execution is against static relations \(R\) and \(S\). In [24], the sensor relations \(R\) and \(S\) are modeled as storing one tuple per node (_i.e._, the most recent measurement).