Continuous k-Nearest Neighbor Queries on Multi-core CPUs

Modern microprocessors employ multi cores to accelerate computations, and parallelizing multiple queries execution to exploit multi-core parallelism has become a challenge for moving objects database applications. To evaluate massive concurrent queries towards moving objects, parallel processing techniques and cache-conscious algorithms adapting to memory hierarchy and multi-core architecture should be developed to maximize the processor computation abilities and reduce the memory stalls. This paper first presents a distributed moving objects updating strategy to reduce the computing cost of server. 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 moving objects. A shortest path based network expansion (SPNE) algorithm is proposed to decrease the processing cost of k nearest neighbor (k-NN) queries by reducing the search network space. For massive k-NN queries evaluation, we use a multi-staged engine, which exploits pipeline strategy and departs the query processing into three simultaneous stages to improve the parallelism with multi-threaded technology. And we present a multi-threaded network expansion (MSPNE) algorithm for massive k-NN queries processing. MSPNE algorithm uses threaded workload parallelism and cache-conscious execution reorganization strategies to improve the spatial and temporal locality. Experimental evaluation on a dual-core platform and analysis show that SPNE and MSPNE algorithms achieve a performance improvement over the existing traditional optimization counterparts.