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

摘要

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