Probabilistic CkNN queries of uncertain data in large road networks

Yanhong Li, Rongbo Zhu, Guohui Li, Lih-Chyun Shu, Changyin Luo

Research output: Contribution to journalArticle

Abstract

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
Volume4
DOIs
Publication statusPublished - 2016 Jan 1

Fingerprint

Query processing
Monitoring
Processing
Experiments

All Science Journal Classification (ASJC) codes

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

Cite this

Li, Yanhong ; Zhu, Rongbo ; Li, Guohui ; Shu, Lih-Chyun ; Luo, Changyin. / Probabilistic CkNN queries of uncertain data in large road networks. In: IEEE Access. 2016 ; Vol. 4. pp. 8900-8913.
@article{be79814580ff4f4bb05594cbdb646f8c,
title = "Probabilistic CkNN queries of uncertain data in large road networks",
abstract = "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.",
author = "Yanhong Li and Rongbo Zhu and Guohui Li and Lih-Chyun Shu and Changyin Luo",
year = "2016",
month = "1",
day = "1",
doi = "10.1109/ACCESS.2016.2635682",
language = "English",
volume = "4",
pages = "8900--8913",
journal = "IEEE Access",
issn = "2169-3536",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

Probabilistic CkNN queries of uncertain data in large road networks. / Li, Yanhong; Zhu, Rongbo; Li, Guohui; Shu, Lih-Chyun; Luo, Changyin.

In: IEEE Access, Vol. 4, 7769182, 01.01.2016, p. 8900-8913.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Probabilistic CkNN queries of uncertain data in large road networks

AU - Li, Yanhong

AU - Zhu, Rongbo

AU - Li, Guohui

AU - Shu, Lih-Chyun

AU - Luo, Changyin

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85009165851&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85009165851&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2016.2635682

DO - 10.1109/ACCESS.2016.2635682

M3 - Article

VL - 4

SP - 8900

EP - 8913

JO - IEEE Access

JF - IEEE Access

SN - 2169-3536

M1 - 7769182

ER -