Parallel Continuous k-Nearest Neighbor Computing in Location Based Spatial Networks on GPUs

摘要

The k nearest neighbor (kNN) computing is an important task in different fields such as LBSN and database area. Recently some methods have been proposed to accelerate kNN searching algorithms for static points with GPUs. To evaluate massive concurrent queries towards mobile objects in spatial networks, we present a multi-staged framework MSF to improve the parallelism with multi-threaded technology, which departs the query processing into three simultaneous stages for continuous kNN queries processing. Further, in-memory spatial network adjacent matrix, shortest path matrix and hash table structures are introduced to describe the road network topology and store the mobile objects. Under MSF framework a GPU-SPNE algorithm is proposed to decrease the computing cost of kNN queries by using threaded workload parallelism. Experimental evaluation shows that GPU-SPNE algorithm achieves a performance improvement about one to two orders of magnitude over its CPU counterparts, and still performs better than the brute-force algorithm on GPU in all conditions.