Complete Update Handling Module

In section  we described how to update the results on receiving data point updates and we discussed handling the updates of queries in section . Now we describe how to deal with data point and query point updates simultaneously at each time stamp. Our update handling module consists of two phases.

$\bullet$ receive updates: First we receive the query point updates and then we handle data point updates. For each query update, if $dist(q_{pre}, q_{cur}) \geq 2q_{pre}.dist_k$ , we delete $q$ and insert a new query in system. Otherwise, we mark the query as moving and calculate $dist(p, q_{cur})$ for every $k$ NN $p$ of $q_{pre}$ and temporarily set $q_{cur}.dist_k$ as ( $q_{pre}.dist_k+dist(q_{pre},q_{cur}$ ).

After handling query updates, we receive point updates. For each query $q$ affected by a point update, we insert (delete) $p$ in (from) $q.kNN$ if it is an incoming (outgoing) update. Only the order of $q.kNN$ is changed in case of internal update.

$\bullet$ update results: We update the results of all affected queries in this phase. The new queries are updated by calling initial computation module described in Algorithm . The affected queries that were not moved are handled as described in section . The queries marked as moving are updated by first setting the $q_{cur}.dist_k$ equal to the distance of $k^{th}$ data point in $q.kNN$ (set as $\infty$ if $\mid q.kNN\mid < k$ ). The update algorithm is similar to initial kNN algorithm and the radius of first round $r_0$ is $max\{max(c^q,q),(q_{pre}.dist_k - dist(q_{pre},q_{cur})\}$ . During computation, the data points that are already in $q.kNN$ are ignored. Clearly, the cells with $maxdist(c, q_{pre}) \leq q_{pre}.dist_k$ are also skipped as all the data points in these cells belong to $q.kNN$ . The algorithm terminates when the next cell $c$ to be accessed has $mindist(c,q)\geq q_{cur}.dist_k$ .

Figure: Handling Multiple Updates

[$q$ , $p_2$ and $p_3$ issue location updates]

[$p_1$ is found as new NN]

Algorithm  summarizes the complete update handling module.