## 4 Techniques of In-Network Join Processing
### First Approaches  
In [29], [PERSON] and [PERSON] compared the communication cost of the external join with that of an in-network join implementation through an experiment. They showed that the performance could differ significantly in favor of as well as against the in-network join depending on the join selectivity. In the in-network join, it was assumed that the join is conducted in a single node of the network where all the tuples are collected. The optimal location of the join node was not addressed.  
In [20], [PERSON] and [PERSON] investigated the problem of searching for the optimal join node assuming that the join is conducted in a single node. They considered an inter-region join \(R\Join S\) whose result is to be consumed at the query sink. The join is a long-running continuous one modeled as a window join. Assuming that the data rates (or the sizes) of \(R\), \(S\), and \(R\Join S\) are known and that the communication cost between two sensor nodes is known, \(C_{a}(N)\), the join assignment cost of node \(N\) which is the cost of assigning the join operator to a node \(N\) is computed [20]. Initially, a node \(N_{0}\) is randomly selected as the join node. Afterwards, a neighbor node \(N_{1}\) of \(N_{0}\) is checked. If \(N_{1}\) has lower assignment cost than \(N_{0}\) (_i.e._, \(C_{a}(N_{1})<C_{a}(N_{0})\)), \(N_{1}\) becomes a new join node. This way, the location of the join node progressively moves towards its optimal location. Also, the optimal location of the join node would change adaptively as the data rates and selectivities change.  
In [25], [PERSON] _et al_. considered a join between a _storage point_ and the sensor relation. A storage point corresponds to a materialized view in relational databases or to a materialization point in data stream systems. It buffers a stream of sensor tuples that belong to a window specified by a query. A storage point is materialized at a single node. The join is implemented by a nested-loop join where the sensor relation is the outer relation and the storage point is the inner one. The tuples of the sensor relation are transmitted through a routing tree.  
In [30], [PERSON] _et al_. investigated a join between an _external relation_ and the sensor relation. The former stores the tuples that specify the conditions of the events to detect in the network. This relation is pushed into the network for the join. There are three cases depending on the size of the external relation. First, it can be stored at a node. Second, it can be partitioned into a group of nodes that are within 1 hop distance (intermediate join). Third, it is too large to fit in the group of nodes in the second case (large join). For an intermediate join, the techniques of group formation, relation partition, and distributed join were proposed. For a large join, the techniques of non-joinable tuple filtering using a Bloom filter [31], partial join, and cache diffusion were proposed.  
In these first approaches, the join was assumed to be performed in a single node [20,25,29] or one of the join operand relations was not a sensor relation [30]. In the next two subsections, the techniques of a join among the sensor readings that do not make the above assumption are presented.