Handling Data Point Updates

Regarding a query $q$ , the update of data point $p$ can be classified into $3$ categories:

• internal update: $dist(p_{pre},q)\leq q.dist_k$ and $dist(p_{cur},q)\leq q.dist_k$ ; Clearly, only the order of $q.kNN$ is affected so we update the order of data points in $q.kNN$ accordingly.
• incoming update: $dist(p_{pre},q)>q.dist_k$ and $dist(p_{cur},q)\leq q.dist_k$ ; $p$ may have become a result so we insert it in $q.kNN$ .
• outgoing update: $dist(p_{pre},q)\leq q.dist_k$ and $dist(p_{cur},q)> q.dist_k$ ; $p$ is deleted from $q.kNN$ because it is no more a part of the answer set.

It is immediately verified that only the queries recorded in the influence lists of cell $c^{p_{pre}}$ or cell $c^{p_{cur}}$ may be affected by the update $\langle p.id, p_{pre},p_{cur}\rangle$ , where $c^{p_{pre}}$ ( $c^{p_{cur}}$ ) is the cell containing $p_{pre}$ ($p_{cur}$ ). Therefore, after receiving an update $\langle p.id, p_{pre},p_{cur}\rangle$ , continuous monitoring module checks these queries $q$ only and takes the necessary action as described above. Note that a new point registered at system can be treated as an object update assuming $p_{pre}$ be at infinite distance from $q$ . Similarly, a point deletion can be considered as an object moved to a location at infinite distance from $q$ ( $dist(p_{cur},q)=\infty$ ).

After all the updates are handled as described above, we update the results of each affected query $q$ as follows.

$\bullet$ Case 1: if $\mid q.kNN \mid \geq k$ . We keep only $k$ closest points to $q$ and delete all others. Then, $q.dist_k$ is updated accordingly. After updating the results, $q.dist_k$ may become smaller. So, we have to remove $q$ from the influence lists of cells $c$ whose $mindist(c,q)$ is greater than current $q.dist_k$ . The update of influence lists is discussed in section .

$\bullet$ Case 2: if $\mid q.kNN\mid < k$ . The recomputation is similar to initial $k$ NN computation but we only need to find the new $(k-\mid q.kNN\mid)$ nearest neighbors of $q$ instead of all $k$ NNs. The only difference is that, we set the radius of the first circle $r_0$ as $q.dist_k$ and then initialize $q.dist_k$ to be $\infty$ . Similar to Algorithm , we repeatedly collect cells round by round and examine them in ascending order of their minimum distance to $q$ till all $k$ NNs are found. When accessing a cell, we only consider data points $p$ which do not already belong to $q.kNN$ .

Figure: Handling Data Point Updates

[Handling an outgoing update $p'_1$ ]

[Handling an incoming update]