支持室内障碍空间的DSP-Topk查询优化算法研究

发布时间：2019-11-14 20:07

【摘要】：多目标优化查询是目前移动对象数据管理的研究热点.多目标优化查询过程中,用户关心的目标对象属性可能依赖于其他移动对象,因此移动对象之间的相互影响将导致目标对象属性存在不确定性.已有的多目标优化算法需要遍历所有目标对象,且不能有效支持目标对象属性的动态变化.基于以上问题,提出了一种有效的应用于障碍空间的多目标优化算法DSP-Topk(dynamic and support pruning Topk),该算法采用可视区域模型处理障碍空间中移动对象的距离计算,利用基于最大夹角差的可视区域方法,提高了计算距离的效率.进而,利用动态调整机制解决目标对象属性的不确定性,预处理的裁剪策略提高了算法效率.实验结合商场真实商品数据集进行测试,与已有的Topk和DS-Topk算法对比表明:所提算法在查询效率上有显著提高,验证了算法的有效性.
【图文】：

可以发现部分餐馆在可视区域ＶＩＳＡ（ｐ）中，如ｑ１，ｑ２，也有部分餐馆不在ＶＩＳＡ（ｐ）中如ｑ４，ｑ５．Ｆｉｇ．１ＶＩＳＡｏｆｑｕｅｒｙｏｂｊｅｃｔｐｏｎｓｉｎｇｌｅｏｂｓｔａｃｌｅ图１单个障碍物下查询对象ｐ的可视区域如图２、图３所示，当障碍空间内具有多个障碍物时，需要对每个多边形的可视区域ＶＩＳＡ（Ｓｉ）求交集得到可视区域ＶＩＳＡ（ｐ）．在图２中障碍空间中有多边形Ｓ１，Ｓ２，Ｓ３．这种情况下ＶＩＳＡ（ｐ）＝ＶＩＳＡ（Ｓ１）∩ＶＩＳＡ（Ｓ２）∩ＶＩＳＡ（Ｓ３）其中ＶＩＳＡ（Ｓ１），ＶＩＳＡ（Ｓ２）和ＶＩＳＡ（Ｓ３）是查询对象ｐ相对于每个多边形所求的可视区域如图３所示．Ｆｉｇ．２ＶＩＳＡｏｆｑｕｅｒｙｏｂｊｅｃｔｐｏｎｍｕｌｔｉ－ｏｂｓｔａｃｌｅｓ图２多个障碍物下查询对象ｐ的可视区域Ｆｉｇ．３ＶＩＳＡｏｆｓｉｎｇｌｅｃｏｎｖｅｘｐｏｌｙｇｏｎｏｎｍｕｌｔｉ－ｏｂｓｔａｃｌｅｓ图３多障碍物下单个多边形可视区域示意图移动对象多目标优化查询可以帮助用户解决在一定条件约束下希望查询结果在多个目标下达到最优的问题．用户关心的多个目标对应于目标对象的多个属性，关于目标对象多属性的定义如下：定义２．目标对象多属性．移动对象多目标优化查询的对象称为目标对象，目标对象具有的属性包含的空间属性和非空间属性．空间属性是指目标对象与查询对象在障碍空间中的最短距离；非空间属性是指对象除空间信息外含有的其他属性．当目标对象的规模较大时，对初始的候选

可以发现部分餐馆在可视区域ＶＩＳＡ（ｐ）中，如ｑ１，ｑ２，也有部分餐馆不在ＶＩＳＡ（ｐ）中如ｑ４，ｑ５．Ｆｉｇ．１ＶＩＳＡｏｆｑｕｅｒｙｏｂｊｅｃｔｐｏｎｓｉｎｇｌｅｏｂｓｔａｃｌｅ图１单个障碍物下查询对象ｐ的可视区域如图２、图３所示，当障碍空间内具有多个障碍物时，需要对每个多边形的可视区域ＶＩＳＡ（Ｓｉ）求交集得到可视区域ＶＩＳＡ（ｐ）．在图２中障碍空间中有多边形Ｓ１，Ｓ２，，Ｓ３．这种情况下ＶＩＳＡ（ｐ）＝ＶＩＳＡ（Ｓ１）∩ＶＩＳＡ（Ｓ２）∩ＶＩＳＡ（Ｓ３）其中ＶＩＳＡ（Ｓ１），ＶＩＳＡ（Ｓ２）和ＶＩＳＡ（Ｓ３）是查询对象ｐ相对于每个多边形所求的可视区域如图３所示．Ｆｉｇ．２ＶＩＳＡｏｆｑｕｅｒｙｏｂｊｅｃｔｐｏｎｍｕｌｔｉ－ｏｂｓｔａｃｌｅｓ图２多个障碍物下查询对象ｐ的可视区域Ｆｉｇ．３ＶＩＳＡｏｆｓｉｎｇｌｅｃｏｎｖｅｘｐｏｌｙｇｏｎｏｎｍｕｌｔｉ－ｏｂｓｔａｃｌｅｓ图３多障碍物下单个多边形可视区域示意图移动对象多目标优化查询可以帮助用户解决在一定条件约束下希望查询结果在多个目标下达到最优的问题．用户关心的多个目标对应于目标对象的多个属性，关于目标对象多属性的定义如下：定义２．目标对象多属性．移动对象多目标优化查询的对象称为目标对象，目标对象具有的属性包含的空间属性和非空间属性．空间属性是指目标对象与查询对象在障碍空间中的最短距离；非空间属性是指对象除空间信息外含有的其他属性．当目标对象的规模较大时，对初始的候选

【相似文献】

相关期刊论文 前10条

1 黄添强;卓飞豹;;移动对象查询研究进展[J];系统仿真技术;2007年04期

2 李伯权;;基于轨迹不确定的移动对象的预测处理[J];齐齐哈尔大学学报;2008年06期

3 王元芝;鄢来斌;;一种移动对象位置信息的处理方法[J];计算机工程与科学;2009年12期

4 李实吉;秦小麟;施竣严;;障碍空间中的移动对象位置预测[J];计算机科学;2014年07期

5 易善桢,张勇,周立柱;一种平面移动对象的时空数据模型[J];软件学报;2002年08期

6 吴劲;卢显良;;移动对象数据模型[J];计算机科学;2002年06期

7 董毅,Edward Chan,黄载禄;LDCQ的距离更新策略[J];华中科技大学学报(自然科学版);2003年12期

8 李国徽;钟细亚;;一种基于固定网络的移动对象运动轨迹索引模型[J];计算机研究与发展;2006年05期

9 卢炎生;查志勇;潘鹏;;一种改进的移动对象时空数据模型[J];华中科技大学学报(自然科学版);2006年08期

10 廖巍;唐桂芬;景宁;钟志农;;基于速度分布的移动对象混合索引方法[J];计算机学报;2007年04期

相关会议论文 前10条

1 翁敬农;;移动对象及其时空模型的研究[A];中国地理信息系统协会第九届年会论文集[C];2005年

2 张伟;皮德常;;挖掘移动对象的频繁运动模式[A];2009年中国智能自动化会议论文集（第三分册）[C];2009年

3 曹会萍;丁治明;王珊;孟小峰;;移动对象管理的自适应索引方法[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年

4 胡志智;孟小峰;郭研妍;李本钊;陈继东;;基于模拟预测的移动对象位置主动更新策略[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

5 陈滨;丁治明;纪鹏程;;基于动态交通网络的移动对象的索引[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

6 王波涛;陈贺;马俊;喜连川优;王国仁;;基于区域覆盖的移动对象索引的设计与实现[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

7 涂丹丹;向琳;左德承;杨孝宗;;移动对象数据库管理技术[A];黑龙江省计算机学会2007年学术交流年会论文集[C];2007年

8 白芸;孟小峰;丁锐;杨楠;胡志智;;基于移动对象流的道路索引[A];第二十届全国数据库学术会议论文集（研究报告篇）[C];2003年

9 刘小峰;陈传波;刘云生;;移动对象全局K最接近邻居查询研究[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年

10 赵亮;陈荦;景宁;钟志农;;一种高效的移动对象连续多范围查询处理框架[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

相关重要报纸文章 前4条

1 中国人民大学信息学院 孟小峰 丁治明;让数据跟随你移动[N];计算机世界;2001年

2 中国人民大学信息学院 郝兴;移动数据管理待补课[N];中国计算机报;2008年

3 ;Word中的“微调”技术[N];中国计算机报;2005年

4 四川 余文勇;课件特殊效果巧实现[N];中国电脑教育报;2001年

相关博士学位论文 前10条

1 吴佩莉;移动对象轨迹数据管理关键技术研究[D];北京理工大学;2015年

2 杨彬;室内移动对象的数据管理[D];复旦大学;2010年

3 叶李;移动对象数据库查询及处理技术研究[D];电子科技大学;2011年

4 张恒飞;空间数据库中移动对象位置管理技术研究[D];华中科技大学;2012年

5 方颖;移动对象数据库中移动对象索引方法研究[D];武汉大学;2010年

6 廖巍;面向位置服务的移动对象索引与查询处理技术研究[D];国防科学技术大学;2007年

7 陈楠;时空数据库中移动对象的索引和查询技术研究[D];浙江大学;2010年

8 赵亮;面向位置服务的移动对象并发查询处理技术[D];国防科学技术大学;2010年

9 张凤荔;移动对象数据智能处理模型研究[D];电子科技大学;2007年

10 袁冠;移动对象轨迹数据挖掘方法研究[D];中国矿业大学;2012年

相关硕士学位论文 前10条

1 黄川林;室内移动对象轨迹分析研究[D];中国科学技术大学;2014年

2 王梦冉;蜂窝网中基于频繁轨迹的越区切换算法研究[D];西南交通大学;2015年

3 金琨;不确定环境下移动对象轨迹模式挖掘及路径规划研究[D];西南交通大学;2015年

4 易显天;面向位置服务的道路网络下的汽车索引技术研究[D];电子科技大学;2015年

5 毕彦博;优化的基于Voronoi图的移动对象K近邻查询算法的研究与实现[D];东北大学;2013年

6 孙清清;面向移动对象间状态查询优化算法的研究与实现[D];东北大学;2013年

7 杨雨;面向GPS的移动对象轨迹模式挖掘研究[D];东北大学;2014年

8 张盼盼;融合复合特征的移动轨迹预测方法的研究与实现[D];西安电子科技大学;2014年

9 吴昊;基于路网的移动对象位置管理关键技术研究[D];南京邮电大学;2015年

10 李岳昌;基于代价聚簇的城市路网移动对象索引技术[D];南京邮电大学;2015年

本文编号：2560974