## 2 Related Works  
In sensor network, sensor nodes are formed by hundreds and hundreds of fixed nodes. Consequently, the value obtained periodically from sensor nodes is lack of expressing all the information about event or entity. It needs a join operation for that problem. The data stored at each sensor node forms a kind of table over all nodes, denoted R. To process a join query, we first have to decide which join queries are used. In this paper, we consider binary equi-join (BEJ). A BEJ query for sensor networks is defined as follows:  
**Definition 1**: Given two sensor tables \(\textbf{R}(A_{1},A_{2},\...,\ A_{n})\) and \(\textbf{S}(B_{1},\ B_{2},\...,\ B_{m})\), a binary equi-join (BEJ) is  
\(\textbf{R}\ \infty_{\text{Ai-Bj}}\ \textbf{S}\) (i \(\in\) {1,2,...., n},\ j\in\) {1,2,...., m})  
where \(\text{A}_{\text{i}}\) and \(\text{B}_{\text{j}}\) are two attributes of R and S respectively, which have the same domain. Consider a sensor network covering a road network from [7]. Each sensor node can detect the IDs of vehicles in its close vicinity, and record the timestamps at which the vehicles are detected. Suppose \(\text{N}_{\text{R}}\) and \(\text{N}_{\text{S}}\) represent two sets of sensor nodes located at two regions of a road segment, Region1 and Region2, respectively. To gather the necessary data for determining the speeds of vehicles traveling between the two regions, the following join query can be expressed:  
SELECT R.autoID, R.time, S.time  
FROM R, S  
WHERE R.location IN Region1 AND S.location IN Region2 AND R.autoID = S.autoID  
To evaluate the above query, sensor readings from Region1 and Region2 need to be collected and joined on the autoID attribute. Typical join strategies of sensor networks are classified into Na we join, Sequential join and Centroid join according to the join location and shown in Figure 1[9]. Figure 1: General join strategies. **(a)** Na \(\text{\char 37}\)e join. **(b)** Sequential join. **(c)** Centroid join. One of general join problems is a heavy communication cost to be transferred into among nodes and a lower join selectivity of query regarding overhead in communication. For instance, given there are two tables, R and S, pairs which is not participated in joining operation between R and S tables can be sent to another region F to join with another table. In the Na \(\bar{\mathrm{v}}\)e join algorithm in Figure 1(a), sensor nodes around the sink node in region F are join nodes N\({}_{\mathrm{F}}\) selected. Although the cost of routing join results to the sink node can be minimized, the each whole table in region R and S is routed to the sink. In the Sequential join algorithm in Figure 1(b), it is minimized by routing the join results to the sink after performing the local join R\({}_{\mathrm{i}}\)\(\propto\) S where R\({}_{\mathrm{i}}\) is the local table stored at node n\({}_{\mathrm{i}}\) in region R and S is the table in region S. In this algorithm, the problem is also that the whole table in region S is delivered to the nodes in region R. That makes communication cost be high. As compared with the earlier algorithms, the Centroid algorithm in Figure 1(c) could also deliver the tables in each region into region F. In spite of that delivery, the nodes which are close to each region R and S in distance are selected to be joined and it could minimize the communication cost. However, the tables in each region are also needed to be routed into the join region F.  
To solve or reduce the problems above, the synopsis strategy join was suggested. After reducing the number of pairs in R and S tables using synopsis to remove the rest pairs not to participate join operation, SNJ sends the pairs to join with others. The means of synopsis is an abstract of a table to process join operation. In addition, the size of the synopsis table is smaller than original table size. Therefore, each sensor creates its synopsis [9]. Synopsis strategy consists of 3 steps. First is synopsis join step. The second step is notification and third is final join operation.