## 3 \(l\)-\(k\)-Nearest-Neighbors Query Processing
### Algorithm for Query Dissemination
```
search_next_vnode(\(h\), \(l\), \(k\), \(f\), \(Q\), \(c\))
```
**Algorithm 2** Determining the Next Search Direction
```
1:Initialize a track-sector discriminants set of current node \(D\)\(\leftarrow\)\(\{\emptyset\}\); /* find four discriminants determining border lines of a track-sector */
2:\(t_{idx}\)\(\leftarrow\)\(\left[\)\(\(\sqrt{(c.\,x-h.\,x)^{2}+(c.\,y-h.\,y)^{2}}\) / \(l\)\()\()\()\right]\); // calculate the track index of cur_node by using \(h\) and \(c\)
3:\(R\)\(\leftarrow\)\(l\)\(\times\)\(t_{idx}\); // calculate the current track radius
4:\(D\)\(\leftarrow\)\(D\)\(\cup\)\(\{(x-h.\,x)^{2}+(y-h.\,y)^{2}=R^{2}\) ; // a upper arc of the track-sector
5:\(D\)\(\leftarrow\)\(D\)\(\cup\)\(\{(x-h.\,x)^{2}+(y-h.\,y)^{2}=(R\quad-l)^{2}\}\); // a lower arc of the track-sector
6:if( \(t_{idx}\) is an even number ) // if the current track is a query track
7:if(\(f\) is true) // if a Q-node is selected
8:\(\theta_{v}\)\(\leftarrow\) calculate the angle of a tractor-sector by \(R\)\(\times\)\(sin\)\(\left(\frac{\theta_{v}}{2}\right)=\frac{l}{2}\) ; // move to the next track-sector
9:else // if a Q-node is not selected
10:\(\theta_{v}\)\(\leftarrow\) calculate the angle for the next vnode by \(R\)\(\times\)\(sin\)\(\left(\frac{\theta_{v}}{2}\right)=\frac{1}{2}\)\(\times\)\(\frac{\sqrt{3}}{2}\) ; // move to the next vnode
11:else // if current track is a margin track
12:\(\theta_{v}\)\(\leftarrow\)\(l\)\(\times\)\(sin\)\(\left(\frac{\theta_{v}}{2}\right)=\frac{l}{2}\); // move to the next query track
13:\(\theta_{cur}\)\(\leftarrow\) calculate the angle between the baseline and the current node by \(tan\theta_{cur}=\frac{c.y-h.y}{c.x-h.x}\) ;
14:\(s_{idx}\)\(\leftarrow\) calculate the sector index of current node by \(\left[(\theta_{cur}\) / \(\theta_{v})\right]\) ;
15:\(D\)\(\leftarrow\)\(D\)\(\cup\)\(\{y=tan(\theta_{v}\)\(\times\)\(s_{idx})(x-c.\,x)+c.\,y\}\); // a left-side line of the track-sector
16:\(D\)\(\leftarrow\)\(D\)\(\cup\)\(\{y=tan(\theta_{v}\)\(\times\)\((s_{idx}-1))(x-c.\,x)+c.\,y\}\); // a right-side line of the track-sector
17: Calculate intersecting points \(P\)\(=\)\(\{ne,nw,se,sw\}\) between each pair of the track-sector discriminants, such as the upper arc \(n\), the lower arc \(s\), the left-side line \(w\), and the right-side line \(e\); /* check that whether the Q-node is selected or not in this tracksector */
18:if(IsSelectTrackSector (\(t_{idx},s_{idx}\)) && \(f\) is \(false\))
19: Find the sensor node \(n\) nearest to the corner intersecting the lower arc and the margin sector;
20:\(Q\)\(\leftarrow\)\(Q\)\(\cup\)\(n\);
21:\(f\)\(\leftarrow\)\(true\);
22:\(dir\)\(\leftarrow\) getNextDirection(\(t_{idx},s_{idx}\)); // decide the next direction by using the track and sector indexes
23:next_vnode\(\leftarrow\) select the next moving point in \(P\)\(=\)\(\{ne,nw,se,sw\}\) according to \(dir\);
24:returnnext_vnode;
```
**Algorithm 3** The Search Direction
```
**Algorithm 3** Determining the Next Forward Direction

Algorithm 4 checks whether the current track-sector \(TS_{t,s}\) is a query sector or a margin sector. If the track-sector has an odd-number sector, it is a query sector (lines 1-9). However, if the total number of sectors is an odd number and the current track-sector is the last sector, it is determined to be a margin sector because two consecutive sectors that are the first and the last sectors cannot be query sectors (lines 3-5).