Discussion

To the best of our knowledge, there is no existing approach that can efficiently update a $k$ NN query to a ($k+m$ )NN query. Even though CPM stores extra book-keeping information (visit list and heap), it cannot efficiently update such query. CPM will need to first visit all the cells in visit list and than continue with the heap in order to find ($k+m$ ) NNs. Note that, CPM will visit the same number of cells that it visits to compute the initial result of a newly issued $k$ NN ($k=k+m$ ) query. i.e; it does not utilize the information of previously known $k$ nearest neighbors. Our algorithm, in contrast, utilizes previous information efficiently and answers the query by visiting minimum number of cells.