Conference Proceedings

A GPU accelerated update efficient index for κnn queries in road networks

C Li, Y Gu, J Qi, J He, Q Deng, G Yu

2018 IEEE 34th International Conference on Data Engineering (ICDE) | IEEE | Published : 2018

Abstract

© 2018 IEEE. The k nearest neighbor (kNN) query in road networks is a traditional query type in spatial databases. This query has found new applications in the fast-growing location-based services, e.g., finding the k nearest Uber cars of a user for ridesharing. KNN queries in these applications are non-Trivial to process due to the frequent location updates of data objects (e.g., movements of the cars). This calls for novel spatial indexes with high efficiency in not only query processing but also update handling. To address this need, we propose an index structure that uses a 'lazy update' strategy to reduce the costs of update handling without sacrificing query efficiency or answer accura..

View full abstract

Grants

Awarded by National Key Research and Development Program of China


Awarded by National Natural Science Foundation of China


Awarded by Australian Research Council (ARC)


Funding Acknowledgements

This work is supported by the National Key Research and Development Program of China (2016YFC0801607), the National Natural Science Foundation of China (61433008, 61472071, 61472072), and Australian Research Council (ARC) Discovery Project DP180103332. Yu Gu is the corresponding author of this work.