Probabilistic CkNN queries of uncertain data in large road networks

Yanhong Li, Rongbo Zhu, Guohui Li, Lihchyun Shu, Changyin Luo

Research output: Contribution to journalArticlepeer-review


Continuous k -nearest neighbor (CkNN) query processing is an important issue in spatial temporal databases. In real-world scenarios, query clients and data objects may move with uncertain speeds on the road networks, which makes retrieving the exact CkNN query result a challenge. This paper addresses the issue of processing probabilistic CkNN queries of uncertain data (CPkNN) for road networks, where moving objects and query points are restricted by the connectivity of the road network and the object-query distance updates affect the query result. A novel model is proposed to estimate network distances between moving objects and a submitted moving query in the road network. Then, a CPkNN query monitoring method is presented to continuously report the possible result objects within a given time interval. In addition, an efficient method is proposed to arrange all the candidate objects according to their probabilities of being a kNN of a query. The method then chooses the top- k objects as the final query result. In addition, we extend our method to large networks with high efficiency. Finally, extensive experiments are conducted to demonstrate the effectiveness of the proposed schema.

Original languageEnglish
Article number7769182
Pages (from-to)8900-8913
Number of pages14
JournalIEEE Access
Publication statusPublished - 2016

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Materials Science(all)
  • Engineering(all)


Dive into the research topics of 'Probabilistic CkNN queries of uncertain data in large road networks'. Together they form a unique fingerprint.

Cite this