YPK-CNN

Yu et al. [YPK05] proposed a method for continuous monitoring of exact kNN queries hereafter referred as YPK-CNN. The new query is evaluated in two steps. First the algorithm searches for $k$ objects around $q$ in iteratively enlarged square $R$ centered at cell $c^q$ , the resident cell of query. Fig.  shows an example of 1-NN query where in first step $p_1$ is found with distance $d$ from q. To guarantee the correctness of results, YPK-CNN processes all the cells intersected by a square SR centered at $c^q$ with side length $2.d+\delta$ and updates the answer if necessary. Fig.  shows that the actual answer $p_2$ is found when all the cells within square of each side $2.d+\delta$ (shaded cells) are visited. YPK-CNN processes all objects from $p_1$ to $p_6$ in the running example.

Figure: YPK-CNN

[initial NN computation] [Update Handling]

Upon receiving the object updates, YPK-CNN uses the previous result of query to update the new result. Let $d_{max}$ be the maximum distance of the object $p\in q.kNN$ from $q$ that is one of the previous nearest neighbors and has now moved farthest from $q$ , YPK-CNN updates the results as follows. Algorithm visits all the cells within square SR with side length $2.d_{max}+\delta$ . Fig.  shows that object $p_2$ issues an update to location $p'_2$ so $d_{max}$ is set to dist($p'_2$ ,q). YPK-CNN visits all objects ($p_1$ to $p_{10}$ ) in the shaded cells of the figure and identifies $p_1$ as the new NN. When a query point changes its location, it is deleted and then handled as new query (i.e., its answer is computed from scratch).