ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (3): 557-569.doi: 10.7544/issn1000-1239.2017.20150895

Previous Articles     Next Articles

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

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

CLC Number: