Abstract: To efficiently process k nearest neighbor queries in spatial road networks, this paper presented a distributed moving objects updating strategy to reduce the computing cost of server. In-memory spatial network adjacent matrix,shortest path matrix and hash table structures were introduced to describe the road network topology and store the moving objects. A shortest path based network expansion (SPNE) algorithm was proposed to decrease the processing cost of k nearest neighbor queries by reducing the search network space. Experimental results show that the SPNE algorithm outperforms existing algorithms including NE and MKNN algorithms.

Key words: Spatial road networks, k-NN caueries, Shortest path matrix, SPNE algorithm