Technique

Consider a $k$ NN query has been updated to ($k+m$ )NN query where $k$ nearest neighbors of the query are already known. If $0>m>-k$ , then the update of the results is trivial. We only keep ($k+m$ ) closest objects among $q.kNN$ and delete all other objects. If $m>0$ , then the results are updated as follows. Let $q.dist_k$ be the distance of $k^{th}$ nearest neighbor of the query $q$ . The algorithm starts calling CircularTrip with radius set equal to $q.dist_k$ and iteratively increases it by $\delta$ unless all ($k+m$ ) nearest neighbors have been found.

Figure: A ($k+m$ )NNs Query ($k=3, m=2$ )

[$k$ NN query ($k=3$ )]

[query updated to ($k+m$ )NN query ($m=2$ )]