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}$ 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.