## 4 Techniques of In-Network Join Processing
### Techniques without Filtering of Non-Joinable Tuples
\(t\) is routed to the sensor node \(N_{c}\) that is nearest to \(c\) using a location routing protocol like GPSR. Join tuple matching for \(t\) is done at \(N_{c}\) because only the partition of \(\widehat{\mathrm{w}}_{S}\) (\(\widehat{\mathrm{w}}_{R}\)) which was hashed to \(c\) and placed at \(N_{c}\) stores the tuples joinable with \(t\). If the memory overflow occurs at \(N_{c}\) when \(t\) is to be placed there, \(t\) is stored at the neighbor nodes of \(N_{c}\). \(N_{c}\) keeps a record on its overflow area, maintaining it up-to-date afterwards. In case \(\theta\) is inequality (_i.e._, a range query), a _locality preserving_ hash function is employed. It hashes the tuples whose joining attribute values are in close proximity with each other to the sensor nodes located near to each other. Join processing for the range predicate is performed across these nodes. In _Distributed Hash-Join_, node failures are handled by data replication. Suppose a node \(N\) stores the partitions of sliding windows \(\widehat{\mathrm{w}}_{R}\) and \(\widehat{\mathrm{w}}_{S}\). The tuples in those partitions are replicated at nearby nodes. Unless not all of them including \(N\) fail, at least one active node that is closest to the hashed geographic coordinates is guaranteed to have the tuples stored in \(N\). _Pair-wise Join._ In [22, 23], [PERSON] _et al._ considered a long-running continuous join whose expression could be as general as the following:\[(\sigma_{\phi_{R}\wedge\psi_{R}}R)\bowtie_{\phi_{RS}\wedge\psi_{RS}}(\sigma_{\phi_{ S}\wedge\psi_{S}}S). \tag{1}\]  
\(\phi_{R}\), \(\psi_{R}\), \(\phi_{S}\), and \(\psi_{S}\) are _selection_ predicates, and \(\phi_{RS}\) and \(\psi_{RS}\) are _join_ predicates. The join is modeled as a sliding window join. Selection predicate \(\phi\)  is only on the auxiliary attributes which are _static_ (e.g., node ID, the coordinates of an immobile node, _etc._). Selection predicate \(\psi\) is related with at least one sensor attribute. Similarly, the join predicates \(\phi\) and \(\psi\) are on the static and on the sensor attributes, respectively. For example, a join which is a modified version of an example query in [22], can be given as follows:  
\[(\sigma_{ID<25\wedge A>200}R)\bowtie_{R.x=S,y+5\wedge R.A=S,B}(\sigma_{ID>50 \wedge B>200}S) \tag{2}\]  
where _ID_ is the node ID, \(x\) and \(y\) represent the coordinates of a node, \(A\) and \(B\) are respectively the sensor attributes of \(R\) and \(S\). Because of the spatial join predicate on the static attributes \(x\) and \(y\) (_i.e._, \(R.x=S.y+5\)), a node that has received this query cannot determine if it is to participate in the query without communicating with other nodes. In [23], the problem of optimal join initiation for a query \(q\) with a spatial join predicate \(\phi_{RS}\) was investigated. Each node \(N_{i}\) that has received \(q\) searches the network through _multicasting_ for its join counterpart node \(N_{t}\) which satisfies \(\phi_{RS}\) with \(N_{i}\). \(N_{i}\) is called an _initiator node_, and \(N_{t}\) is called a _target node_ (Figure 5(a)). Note that for each initiator node, there could be multiple target nodes (Figure 5(b)). While \(N_{i}\) searches for its target nodes, the vector information on the current path traversed so far is maintained so that backtracking to \(N_{i}\) is possible. Once a target node \(N_{t}\) is found, \(N_{i}\) and \(N_{t}\) communicate with each other, setting up the optimal in-network strategy of joining the tuples in \(N_{i}\) with those in \(N_{t}\). In [22], this join between two nodes \(N_{i}\) and \(N_{t}\) is called a _pair-wise join_ (or _1:1 join_). Since there could be multiple target nodes for each initiator node, there could be multiple pair-wise joins that contribute to the result of \(q\). In [23], join initiation is carried out for each pair-wise join individually. As for multiple join pair optimization, it is carried out after individual join initiations are completed. It is described shortly.