Continuous Monitoring

Continuous monitoring of a $k$ farthest neighbors is also very similar to that of a $k$ nearest neighbors query. Let $q.kFN$ be the set of $k$ farthest neighbors of $q$ . In monitoring of $k$ farthest neighbors, an update $<p.id,p_{pre},p_{cur}>$ is considered outgoing update if $dist(p_{pre},q)\geq q.dist_k$ and $dist(p_{cur},q)<q.dist_k$ . Similarly, an update is considered incoming if $dist(p_{pre},q)<q.dist_k$ and $dist(p_{cur},q)> q.dist_k$ . During update handling, the algorithm deletes an object $p$ from $q.kFN$ if it issues an outgoing update and inserts it in $q.kFN$ if it issues an incoming update. After handling all the updates, if $q.kFN$ contains more than or equal to $k$ objects, the algorithm keeps $k$ farthest objects and deletes all other. On the other hand, if $q.kFN$ contains less than $k$ objects, the algorithm updates the result by calling CircularTrip with radius $q.dist_k$ and iteratively decreasing it by $\delta$ unless $k$ farthest neighbors have been found.

Figure: Update Handling of a Farthest Neighbor Query

[$p_3$ issues an update at $p'_3$ ] [$p_2$ is new farthest neighbor]