V*-kNN: an Efficient Algorithm for Moving k Nearest Neighbor Queries

Abstract

This demonstration program presents the V*-kNN algorithm, an efficient algorithm to process moving k nearest neighbor queries (MkNN). The V*-kNN algorithm is based on a safe-region concept called the V*-Diagram. By incrementally maintaining the V*-Diagram, V*-kNN continuously provides accurateMkNN query results and supports dynamically changing values of k. Our approach exploits information regarding the current location of the query point and the search space in addition to the data objects. As a result, the V*-kNN has much smaller IO and computation costs than existing methods. © 2009 IEEE.