## 4 Techniques of In-Network Join Processing
### Techniques without Filtering of Non-Joinable Tuples
In [8], [PERSON] and [PERSON] proposed an index join algorithm using a _distributed \(B^{+}\) tree_ implemented in WSNs to answer a continuous join query. It executes an inter-region theta-join \(R\Join_{P_{r}}S\), where \(P_{r}\) is a _range_ predicate of the form, \(|R.A.-S.B.|\)\(\theta\) for a value \(v\). The join is modeled as a sliding window join. \(\widehat{\w}_{R}\) and \(\widehat{\w}_{S}\) are indexed on their joining attributes using a distributed \(\mathrm{B}^{+}\) tree. It is created across the sensor nodes of the network as follows: First, a sensor node \(N_{R}\) to store the root node of the \(\mathrm{B}^{+}\) tree is chosen, and the degree (_i.e._, branch factor) \(d\) of the \(\mathrm{B}^{+}\) tree is determined. The proper value of \(d\) is set depending on the amount of memory available in a sensor node. Once \(N_{R}\) and \(d\) are determined, a set \(S_{N}\) of the sensor nodes including \(N_{R}\) to store the \(\mathrm{B}^{+}\) tree nodes are chosen. Each node in \(S_{N}\) is assigned a value _range_ of the joining attribute. This assignment process is conducted from \(N_{R}\) to its descendants level by level, and the leaf nodes of the \(\mathrm{B}^{+}\) tree are supposed to store the tuples of \(\widehat{\mathrm{w}}_{R}\) and \(\widehat{\mathrm{w}}_{S}\). In a conventional \(\mathrm{B}^{+}\) tree, a pointer to a child node or a sibling link of a leaf node is the memory address of the target node. In the proposed \(\mathrm{B}^{+}\) tree in WSNs, those pointers are represented by the geographic coordinates of the _sensor node_ that stores the target \(\mathrm{B}^{+}\) tree node. Thus, access to the target node is carried out by a location routing protocol like GPSR. Join processing proceeds as follows: When a tuple \(t\) of \(R\) (\(S\)) is produced, the tuples of \(\widehat{\mathrm{w}}_{S}\) (\(\widehat{\mathrm{w}}_{R}\)) that satisfy \(P_{r}\) with \(t\) are searched from the \(\mathrm{B}^{+}\) tree index, and \(t\) is stored at the leaf node of the \(\mathrm{B}^{+}\) tree where it belongs. _Distributed Index-Join_ is a symmetric _indexed_ nested-loop join, where the set of newly produced tuples of \(R\) (\(S\)) is the outer relation while \(\widehat{\mathrm{w}}_{S}\) (\(\widehat{\mathrm{w}}_{R}\)) plays the role of the indexed inner relation. Since the join predicate is a range one, the leaf node of the \(\mathrm{B}^{+}\) tree where the smallest value satisfying the predicate resides is searched, and then, through the sibling links, the subsequent leaf nodes are traversed until the largest value satisfying the predicate is reached. In _Distributed Index-Join_, node failures are handled by data replication. A \(\mathrm{B}^{+}\) tree index node \(N_{B}\) stored in a sensor node is replicated at nearby sensor nodes. In the parent node of \(N_{B}\), the geographic coordinates referring to \(N_{B}\) is now supposed to refer to a set of duplicated children. When the \(\mathrm{B}^{+}\) tree is searched and \(N_{B}\) is to be accessed, one of \(N_{B}\)'s duplicates can be chosen. _Distributed Index-Join_ can be effective for a long-running continuous join. The cost of building and maintaining (e.g., evicting the old tuples outside the indexed sliding window) the distributed \(\mathrm{B}^{+}\) tree index could be paid off for a long running join. _Distributed Hash-Join._ In [8], [PERSON] and [PERSON] proposed _Distributed Hash-Join_ to answer a continuous join query. It executes an inter-region theta-join \(R\bowtie_{P_{r}}S\), where \(P_{r}\) is a _range_ predicate of the form, \(|R.\,A-S.\,B|\)\(\theta\) for a value \(v\). _Distributed Hash-Join_ adapts the hash join to WSNs. The join is modeled as a sliding window join. It partitions \(\widehat{\mathrm{w}}_{R}\) and \(\widehat{\mathrm{w}}_{S}\) using the same hash function on the joining attributes. The join works as follows: In case \(\theta\) is equality (_i.e._, an equi-join), it hashes a newly produced tuple \(t\) of \(R\) (\(S\)) to geographic coordinates \(c\).