V*-kNN: an Efficient Algorithm for Moving k Nearest Neighbor Queries
Sarana Nutanong, Rui Zhang, Egemen Tanin, Lars Kulik
ICDE: 2009 IEEE 25TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, VOLS 1-3 | IEEE | Published : 2009
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.