An Efficient Framework for Correctness-Aware kNN Queries on Road Networks
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractGiven a set O of objects and a query point q on a road network, the k Nearest Neighbor (kNN) query returns the k nearest objects in O with the shortest road network distance to q. These kNN queries find many applications in location-based services, e.g., ride-hailing services, where each taxi is regarded as an object. In such applications, objects are constantly moving such that even for the same query point, the correct answer of a kNN query may vary with time. Ideally, the returned answer should be adequately correct with respect to the moving object set. However, in literature, all existing solutions for kNN queries mainly focus on reducing the query time, indexing storage, or throughput of the kNN queries with little focus on their correctness. Motivated by this, we propose a framework on correctness-aware kNN queries which aim to optimize system throughput while guaranteeing query correctness on moving objects. We formally define the serializable-kNN query that ensures the correctness of the query answer when considering moving objects and dependencies of different queries. We propose several techniques to optimize the throughput of serializable-kNN queries: firstly, we propose efficient index structures and new query algorithms that significantly improve the throughput; we further present novel scheduling algorithms that aim to avoid conflicts and improve the system throughput. Moreover, we devise approximate solutions that provide a controllable trade-off between the correctness of kNN queries and system throughput. Extensive experiments on real-world data demonstrate the effectiveness and efficiency of our proposed solutions over alternatives.
All Author(s) ListHe D, Wang S, Zhou X, Cheng R
Name of ConferenceIEEE 35th International Conference on Data Engineering (ICDE)
Start Date of Conference08/04/2019
End Date of Conference11/04/2019
Place of ConferenceMacau
Country/Region of ConferenceMacau
Proceedings Title2019 IEEE 35th International Conference on Data Engineering (ICDE)
Book title35th {IEEE} International Conference on Data Engineering, {ICDE} 2019, Macao, China, April 8-11, 2019
Pages1298 - 1309
LanguagesEnglish-United States

Last updated on 2020-31-03 at 02:30