# Enhanced Distributed Dynamic Skyline Query for Wireless Sensor Networks
## 3 Basic System Design
### Skyline Query
#### 3.5.2 Basic System Operation  
A query node first calculates hash \(h_{q}\) using Equation (10) for the _Dynamic Skyline Query_ (DS \((q,r)\)). The query is then forwarded to the \(SH_{i}\) where \(P_{i}\leqslant h_{q}\leqslant P_{i+1}\). \(SH_{i}\) finds the range of the query, _i.e._, \([h_{q}\)-\(r,h_{q}\)+\(r]\). Hence, the target sectors where the sample dataset of the query need to be considered are \(SH_{j}\), \(SH_{j+1}\),..., \(SH_{k}\), here \(P_{j}\leqslant h_{q-r}\leqslant P_{j+1}\), \(P_{k}\leqslant h_{q+r}\leqslant P_{k+1}\) and \(j\leqslant k\). The threshold based hierarchical approach includes three phases--_Tree Propagation_, _Regular Update_ and _Triggered Query_.  
\(SH_{i}\) issues a _Triggered Query_ containing \(LS_{i}\) to \(SH_{j+1}\), \(SH_{j+2}\)..., \(SH_{k}\). The _Triggered Query_ is issued to ensure fetching all possible events that might be included in the final skyline but was not reported during the _Regular Update_ phase. \(SH_{i}\) sends _Triggered Query_ to each of its child \(SH_{j}\) that satisfies \(LS_{i}\preceq\theta_{j}\). Any child node \(SH_{j}\) satisfying \(LS_{i}\preceq\theta_{j}\) can be discarded since no ineligible event can exist in the final skytline. There cannot exist any event that can be eligible to be included in the final skyline. An _internal_ child node \(SH_{j}\) after receiving _Triggered Query_\(LS_{p}\) from its parent computes \(LS_{j}\) among \(LS_{p}\) and its non-reported points. \(SH_{j}\) then forwards \(LS_{j}\) to each of its children \(SH_{k}\) that satisfies \(LS_{j}\preceq\theta_{k}\) and waits for a reply with new points that are not dominated by \(LS_{j}\). \(SH_{j}\) updates the local skyline after receiving replies from all of its child nodes and finally replies to its parent \(SH_{p}\) with the new  
Figure 8: SH of _13 th_ Sector implies Algorithm 3 in order to convert the \(5\times 5\) grid into a tree rooted at _13 th_ (2, 3) Sector.  
Figure 10: Hierarchy based on segmentation.  
Figure 9: Tree rooted at _13 th_ Sector (2, 3).  
skyline event set. In contrast, a leaf node \(SH_{j}\) reports nothing if it reports \(e_{j}\) in the first phase or satisfies \(LS_{i}\preceq\theta_{j}\). Otherwise, it reports event \(e_{j}\).  
Figure 11 illustrates the functionality of the two phases--_Regular Update_ and _Triggered Query_ in a particular scenario. In the first phase (_Regular Update_) (Figure 11a), \(SH_{0}\) and \(SH_{7}\) reports \(e_{o}\) and \(e_{7}\) to \(SH_{3}\) and \(SH_{4}\), respectively. However, \(e_{7}\) and \(e_{3}\) have been pruned by \(e_{4}\). Thus, the skyline set after the first phase includes \(\{e_{0},e_{4}\}\) (see Figure 11b). Figure 11c,d illustrates the second phase. \(SH_{4}\) issues a _Triggered Query_ containing \(\{e_{0},e_{4}\}\) to \(SH_{3}\), \(SH_{6}\), \(SH_{5}\), and \(SH_{8}\) (here, it is assumed that \([h_{q}-r,h_{q}+r]\) covers all the tree \(SH\)). \(SH_{0}\), \(SH_{1}\), \(SH_{7}\) and \(SH_{2}\), however, are discarded since their corresponding thresholds are dominated by \(e_{4}\). After receiving the _Triggered Query_, \(SH_{5}\) prunes \(e_{5}\) and forwards the updated skyline set \(\{e_{0},e_{4}\}\) to \(SH_{8}\). \(SH_{8}\) calculates its local skyline and prunes among the query it receives from its parent and its own event \(e_{8}\). Since \(e_{8}\) is not dominated, it has also been included into the final local skyline set, _i.e._, \(\{e_{0},e_{4},e_{8}\}\), and is finally sent back to the \(SH_{4}\). It is to be noted that, during both phases, \(SH_{1}\) and \(SH_{2}\) do not need to transmit any event.  
Figure 11: Basic Approach Example (3 \(\times\) 3 Grids). (**a**) Regular update. (**b**) Skyline set after first phase. (**c**) Triggered query. (**d**) Skyline set after second phase.