SEA-CNN

Xiong et al. [XMA05] proposed SEA-CNN which focuses exclusively on monitoring the NN changes, without including a module for the evaluation of initial results of a newly registered query. Objects are indexed with grid in secondary memory. The answer region of a query $q$ is defined as the circle centred at $q$ with radius $best\_dist$ where $best\_dist$ is the distance of $k^{th}$ NN from $q$ . The cells intersecting this circle store book-keeping information to indicate the fact that they are affected by q.

Figure: SEA-CNN

[$p_2$ issues update] [q issues update]

Updates are handled by expanding the circle to radius $d_{max}$ , the maximum distance of all outgoing objects. In Fig. , the object $p_2$ issues an update and $d_{max}$ is set as dist($p'_2$ ,q). Search region SR is set as the circle with radius r=$d_{max}$ and all the cells intersecting this circle (shaded cells in the figure) are visited and result is updated. Finally, if the query q moves to a new location $q'$ as shown in Fig. , the SEA-CNN sets $r=best\_dist + dist(q,q')$ and computes the new kNN set of $q$ by processing all the cells that lie in the circle centered at $q'$ with radius $r$ . The processed cells are shown shaded.