CircularTrip Based Continuous $k$ NN Algorithm

Different from a snapshot $k$ NN query, continuous $k$ NN queries are issued once and run continuously to generate results in real-time along with the updates of the underlying datasets. Therefore, it is crucial to develop in-memory techniques to continuously process $k$ NN queries due to frequent location updates of data points and query points. In many applications [XMA05,YPK05,MHP05], it is also crucial to support the processing of a number of continuous $k$ NN queries simultaneously; consequently, scalability is a key issue.

To address the scalability, we focus on two issues: (1) minimization of computation costs; and (2) minimization of the memory requirements. We study continuous $k$ NN queries against the data points that move around in an arbitrary way. Similar to the previous work [XMA05,YPK05,MHP05], we assume that the dataset is indexed by an in-memory grid index. Based on CircularTrip presented in Chapter  , we present an efficient algorithm to continuously monitor $k$ NN queries.Compared with the most advanced algorithm CPM [MHP05], our CircularTrip-based continuous $k$ NN algorithm has the following advantages.

1. time efficient: although both algorithms access the minimum number of cells for initial computation, minimum cells are accessed during continuous monitoring in our algorithm.

2. space efficient: our algorithm does not employ any book-keeping information used in CPM (i.e., visit list and search heap for each query).

Our experimental study demonstrates that CircularTrip-based continuous $k$ NN algorithm is $2$ to $4$ times faster than CPM, while its memory usage is only $50\%$ to $85\%$ of CPM.