Probabilistic Threshold k-ANN Query Method Based on Uncertain Voronoi Diagram in Internet of Vehicles

Effective querying of data in the road networks is an important problem in the Internet of vehicles. Aggregate nearest neighbor queries can return the objects that minimizes an aggregate distance function on road networks considering a set of query points in the Internet of vehicles. And {k} aggre...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on intelligent transportation systems 2021-06, Vol.22 (6), p.3592-3602
Main Authors: Li, Song, Li, Bohan, Yu, Jiaxi, Zhang, Liping, Zhang, Anman, Cai, Ken
Format: Article
Language:English
Subjects:
Aggregates
Algorithms
Computer science
Data aggregation
Data models
Data points
Internet
Internet of Vehicles
k-ANN Query
Probabilistic logic
Queries
road networks
Roads
uncertain Voronoi diagram
Vehicles
Voronoi graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Effective querying of data in the road networks is an important problem in the Internet of vehicles. Aggregate nearest neighbor queries can return the objects that minimizes an aggregate distance function on road networks considering a set of query points in the Internet of vehicles. And {k} aggregate nearest neighbor query ( {k} - ANN) is a complicate version for the basic one. The existing {k} - ANN queries lack effective model to deal with the uncertain data and the existing query methods cannot be applied to solve the problem of ( {k} - ANN) query on uncertain data directly. Therefore, in this paper, a probabilistic threshold {k} - ANN query method based on uncertain Voronoi diagram is proposed. The method includes three phases: processing phase, pruning phase and refinement phase. The processing phase is to compute the minimum covered circle of the query dataset which is prepared for the pruning phase. In pruning phase, the different pruning algorithms are proposed for the corresponding three aggregate function of aggregate nearest neighbor query. The data points that cannot be the result are pruned and the candidate set is obtained. In refinement phase, the sets composed of {k} data points in candidate set whose probabilities are not less than the user-specified threshold are stored into the result set and returned to the user. Experiments are performed to evaluate the effectiveness and superiority of these algorithms on probabilistic threshold k-ANN query.
ISSN:1524-9050
1558-0016
DOI:10.1109/TITS.2020.3003902