ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (3): 557-569.doi: 10.7544/issn1000-1239.2017.20150895

• 软件技术 • 上一篇    下一篇

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

李博涵1,2,3,张潮1,李东静1,许建秋1,2,夏斌1,秦小麟1,2   

  1. 1(南京航空航天大学计算机科学与技术学院 南京 210016); 2(江苏省软件新技术与产业化协同创新中心 南京 210016); 3(江苏易图地理信息科技股份有限公司 江苏扬州 225000) (bhli@nuaa.edu.cn)
  • 出版日期: 2017-03-01
  • 基金资助: 
    国家自然科学基金项目(61373015,61300052,41301047);中央高校基本科研业务费专项资金项目(NP2013307, NZ2013306); 中国留学基金委国家公派留学项目(201406835051); 中国民用航空局安全能力建设基金(AS-SA2015/21);江苏省自然科学基金青年基金项目(BK20130819);江苏高校优势学科建设工程资助项目;南京航空航天大学科研基地创新基金(NJ20160028);南京航空航天大学研究生创新实验室开放基金项目(kfjj20151607).

A DSP-Topk Query Optimization Algorithm Supporting Indoor Obstacle Space

Li Bohan1,2,3, Zhang Chao1, Li Dongjing1, Xu Jianqiu1,2, Xia Bin1, Qin Xiaolin1,2   

  1. 1(School of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016); 2(Collaborative Innovation Center for Novel Software Technology and Industrialization of Jiangsu Province, Nanjing 210016); 3(Jiangsu Easymap Geographic Information Technology Corp Ltd, Yangzhou, Jiangsu 225000)
  • Online: 2017-03-01

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

关键词: 移动对象, 多目标优化, 不确定性, 裁剪, 动态调整

Abstract: Multi-objective optimization is one of the key technologies in moving objects data management. While in the procession of multi-objective optimization query, the concerned target object's attributes may depend on the other moving objects' attributes. Therefore, moving objects can affect each other, which will lead to the uncertainty of the object's properties. The existing multi-objective optimization algorithms need to traverse all the target objects, furthermore, they can't effectively solve the problem of dynamic change of object attributes. We propose an effective multi-objective optimization algorithm DSP-Topk (dynamic and support pruning Topk) to solve the query in the obstacle space. Visual area model can calculate the distance between the moving objects with obstacles. The method of viewable area which applies the maximum differential angle can improve the calculation performance of the distance between moving objects. Then, we study the uncertainty of the object's attributes by using the dynamic adjustment mechanism. The given pruning strategy with preprocessing improves the efficiency of the query. The results of experiments indicate that DSP-Topk algorithm improves the query efficiency significantly compared with the existing Topk algorithm and DS-Topk algorithm. Combined with the real testing data of goods in stores, the rationality and effectiveness of the algorithm are also verified.

Key words: moving objects, multi-objective optimization, uncertainty, pruning, dynamic adjustment

中图分类号: