In this paper, we propose iSEE, a set of algorithms for efficient processing of continuous k-nearest-neighbor (CKNN) queries over moving objects. iSEE utilizes a grid index and incrementally updates the queries? results based on moving objects? explicit location update messages. We have three innovations in iSEE: a Visit Order Builder (VOB) method that dynamically constructs a query?s optimal visit order to the cells in the grid index with low cost, an Efficient Expand (EFEX) algorithm which avoids unnecessary and redundant searching when updating a query?s result, and an efficient algorithm that quickly identifies the cells that should be updated after a query?s result is changed. Experimental results show that iSEE achieves a 2X speedup, when compared with the state-of-the-art CPM scheme.
Citation:
Wei Wu, Kian-Lee Tan, "iSEE: Efficient Continuous K-Nearest-Neighbor Monitoring over Moving Objects," ssdbm, pp.36, 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), 2007