-
题名路网中连续反向k近邻查询处理
被引量:2
- 1
-
-
作者
卢秉亮
崔晓玉
刘娜
-
机构
沈阳航空航天大学计算机学院
沈阳工程学院信息学院
-
出处
《计算机工程与设计》
CSCD
北大核心
2014年第7期2395-2401,共7页
-
基金
沈阳市科技计划基金项目(F13-316-1-35)
-
文摘
现存的反向k近邻查询方案中,比较高效地研究大多集中在欧式空间,对于路网中的反向k近邻查询的研究相对较少。针对这一问题,考虑路网中移动查询点和移动数据对象的移动性,选用PMR四叉树来索引路网,基于安全区的概念提出一种反向k近邻(RkNN)查询算法,通过监控查询点和移动对象的安全区来处理路网更新。基于"初始化-维护更新"框架,采用Dijkstra搜索策略,设置验证监控区域来判定候选对象解的真假性。为了减少网络搜寻的工作量,提出了一系列剪枝规则来削减搜索空间。实验结果表明,该算法适用于路网中k值不固定的连续RkNN查询。
-
关键词
路网
移动性
连续反向k近邻(rknn)
安全区
PMR四叉树
-
Keywords
road network
mobility
continuous reverse nearest k neighbors (rknn)
safe regiom PMR quad-tree
-
分类号
TP392
[自动化与计算机技术—计算机应用技术]
-
-
题名路网中双色反向k近邻查询处理
被引量:5
- 2
-
-
作者
卢秉亮
崔晓玉
刘娜
-
机构
沈阳航空航天大学计算机学院
沈阳工程学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2015年第2期266-270,共5页
-
基金
沈阳市科技计划项目(F13-316-1-35)资助
-
文摘
目前,路网中反向最近邻查询引起了广泛关注,有很多算法被提出.在实际路网中,由于移动数据对象的种类多种多样,单色反向最近邻查询有时并不能完全满足要求.因此,研究路网双色反向最近邻查询具有重要的实际意义.考虑到这种情况,提出一种路网中双色反向最近邻查询算法.通过PMR四叉树索引路网,采用Dijkstra算法遍历路网.为了保证连续监控,为查询点和对象分别设置安全区.为了验证候选对象,为其设置验证监控区.由于双色查询中,对象的种类不同,因此分别采用两个集合来保存这两类对象.通过实验对比,证明该算法具有较好的有效性和稳定性.
-
关键词
路网
双色反向k近邻(BRk
NN)
安全区
验证监控区
PMR四叉树
连续监控
-
Keywords
road network
bichromatic reverse nearest k neighbors ( Brknn )
safe region
verifying region
PMR quad-tree
continuousmonitoring
-
分类号
TP392
[自动化与计算机技术—计算机应用技术]
-
-
题名时间依赖路网中反向k近邻查询
被引量:1
- 3
-
-
作者
李佳佳
沈盼盼
夏秀峰
刘向宇
-
机构
沈阳航空航天大学计算机学院
-
出处
《计算机科学》
CSCD
北大核心
2019年第1期232-237,共6页
-
基金
国家自然科学基金(61502317)
辽宁省自然科学基金(201602559
201602568)资助
-
文摘
在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少。已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低。对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后,利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果。实验中将mTD-SubG算法与已有算法mTD-Eager进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05%,遍历节点个数比mTD-Eager算法减少了51.40%。
-
关键词
时间依赖
路网
反向k近邻(rknn)
mTD-SubG算法
-
Keywords
Time-dependent
Road networks
Reverse k nearest neighbor
mTD-SubG algorithm
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-