Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (2): 341-346.DOI: 10.11772/j.issn.1001-9081.2017.02.0341

Previous Articles     Next Articles

Probabilistic bichromatic reverse-kNN query on road network

XU Wei, LI Wengen, ZHANG Yichao, GUAN Jihong   

  1. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China
  • Received:2016-08-12 Revised:2016-09-13 Online:2017-02-10 Published:2017-02-11
  • Supported by:

    This work is partially supported by the National Natural Science Foundation of China (61373036), the Program of Shanghai Subject Chief Scientist (15XD1503600).

路网中位置不确定的二元反kNN查询

徐伟, 李文根, 张毅超, 关佶红   

  1. 同济大学 计算机科学与技术系, 上海 201804
  • 通讯作者: 关佶红,jhguan@tongji.edu.cn
  • 作者简介:徐伟(1991-),男,江苏淮安人,硕士研究生,CCF会员,主要研究方向:空间关键词查询、数据挖掘;李文根(1987-),男,四川南充人,博士研究生,CCF会员,主要研究方向:空间数据库、数据挖掘;张毅超(1982-),男,上海人,助理教授,博士,CCF会员,主要研究方向:复杂网络、数据挖掘;关佶红(1969-),女,辽宁开原人,教授,博士生导师,博士,CCF高级会员,主要研究方向:空间数据库、数据挖掘。
  • 基金资助:

    国家自然科学基金资助项目(61373036);上海市优秀学术带头人计划项目(15XD1503600)。

Abstract:

Considering the road network constraint and the uncertainty of moving object location, a new reverse-kNN query on road network termed Probabilistic Bichromatic Reverse-kNN (PBRkNN) was proposed to find a set of uncertain points and make the probability which the kNN of each uncertain point contains the given query point be greater than a specified threshold. Firstly, a basic algorithm called Probabilistic Eager (PE) was proposed, which used Dijkstra algorithm for pruning. Then, the Pre-compute Probabilistic Eager (PPE) algorithm which pre-computes the kNN for each point was proposed to improve the query efficiency. In addition, for further improving the query efficiency, the Pre-compute Probabilistic Eager External (PPEE) algorithm which used grid index to accelerate range query was proposed. The experimental results on the road networks of Beijing and California show that the proposed pre-computation strategies can help to efficiently process probabilistic bichromatic reverse-kNN queries on road networks.

Key words: reverse-kNN query, road network, Dijkstra algorithm, uncertainty

摘要:

针对路网限制和物体位置的不确定性,提出了路网中位置不确定的二元反kNN查询(PBRkNN),旨在查找一组位置不确定的点,使得每个不确定点的kNN包含给定查询点的概率大于一个阈值。为了解决该问题,首先提出一种基于Dijkstra进行剪枝处理的基本算法,即PE算法;接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度,即PPE算法;而为了进一步减小PPE算法中范围查询的开销,提出PPEE算法,利用网格索引来索引范围查询中要查询的不确定空间点,从而提升算法的效率。最后,在北京和加州路网数据集上进行了大量实验,结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询。

关键词: kNN查询, 路网, Dijkstra算法, 不确定性

CLC Number: