A GPU Accelerated Update Efficient Index for kNN Queries in Road Networks

摘要: The k nearest neighbor (kNN) query in road networks is a traditional type spatial databases. This has found new applications the fast-growing location-based services, e.g., finding Uber cars of user for ridesharing. KNN queries these are non-trivial to process due frequent location updates data objects (e.g., movements cars). calls novel indexes with high efficiency not only processing but also update handling. To address this need, we propose an index structure that uses "lazy update" strategy reduce costs handling without sacrificing or answer accuracy. We cache and corresponding entries when they queried. further kNN algorithm based on index. takes advantage strengths both CPU GPU. It first identifies queried region over using Then, it GPU produce candidate result set, which later refined by obtain final answer. conduct experiments real compare proposed state-of-the-art algorithms. experimental results show outperforms baseline algorithms orders magnitude time.