Accelerating Visualization Update of Moving Objects in GPU Environment

doi:10.3778/j.issn.1002-8331.2106-0472

Abstract

Abstract: Moving objects data, with the characteristics of large scale and frequent updates, requires high performance for data visualization. As the data scale increases, the performance and efficiency of visualization with real-time loading of data will decrease accordingly. To improve the efficiency of moving objects visualization, an update method of moving objects under GPU environment is proposed, and a parallel query scheme is designed based on the characteristics of moving objects. At the same time, the update function of moving objects is optimized by comparing the time interval of two adjacent visual queries, the time segment that needs to be updated is found and updated accordingly, so as to avoid the update of the whole time interval. The experiment uses synthetic datasets with data sizes of 4 million to 10 million, and a real taxi dataset with about 9.6 million sampling points. The experimental result shows that, compared with the R-tree query on CPU, the R-tree query on GPU and the serial index query in the update function on CPU, the proposed method has better query performance, and the acceleration ratio is up to 18.48. After the optimization of the moving objects update function, when two adjacent visual query time intervals overlap completely, the acceleration rate is close to 100%.

Key words: moving objects update, visualization efficiency, graphic processing unit（GPU）

摘要： 移动对象数据具有规模大、更新频繁的特点，对数据可视化具有较高的性能要求。当数据规模增大时，实时加载数据进行可视化的性能效率会随之降低。为了提高移动对象可视化的效率，提出了GPU环境下的移动对象更新方法，并结合移动对象特征设计出并行查询方案。同时，优化了移动对象的更新函数，通过比较临近的两次可视化查询的时间区间，找出需要更新的时间片，对其进行相应的更新，从而避免了整个时间区间的更新。实验使用了数据规模为400万到1?000万的合成数据集，和包含约960万个采样点的真实出租车数据集。实验结果表明，与CPU上的R-Tree查询、GPU上的R-Tree查询和CPU上更新函数中的串行索引查询方法相比，所提方法具有较好的查询性能，加速比最高可达18.48。移动对象更新函数优化后，当临近的两次可视化查询时间区间完全重叠时，加速效率接近100%。

关键词: 移动对象更新, 可视化效率, 图形处理器（GPU）

MAO Yanchun, XU Jianqiu. Accelerating Visualization Update of Moving Objects in GPU Environment[J]. Computer Engineering and Applications, 2022, 58(23): 261-267.

冒艳纯, 许建秋. GPU环境下加速移动对象可视化更新的方法研究[J]. 计算机工程与应用, 2022, 58(23): 261-267.

References

[1] CUZZOCREA A.Advanced query answering techniques over big mobile data[C]//2016 17th IEEE International Conference on Mobile Data Management（MDM），Porto，Portugal，2016：4-7.
[2] GUETING R H，BEHR R，XU R.Efficient k-nearest neighbor search on moving object trajectories[J].The VLDB Journal，2010，19（5）：687-714.
[3] GATTERBAUER W.Databases will visualize queries too[J].Proceedings of the VLDB Endowment，2011，4：1498-1501.
[4] ORTAL P，KATO S，EDAHIRO M.Real-time visualization of moving objects[C]//2015 IEEE 3rd International Conference on Cyber-Physical Systems，Hong Kong，China，2015：60-65.
[5] WANG Z，LU M，YUAN X，et al.Visual traffic jam analysis based on trajectory data[J].IEEE Transactions on Visuali-zation and Computer Graphics，2013，19（12）：2159-2168.
[6] GüTING R H，BEHR T，DüNTGEN C.SECONDO：a platform for moving objects database research and for publishing and integrating research implementations[J].IEEE Data Eng，2010，33（2）：56-63.
[7] XU J，GüTING R H.Infrastructures for research on multimodal moving objects[C]//IEEE 12th International Conference on Mobile Data Management，Lulea，Sweden，2011：329-332.
[8] NVIDIA Corporation.High performance computing[EB/OL].[2021-04-26].https：//developer.nvidia.cn/zh-cn/hpc.
[9] 李涛，董前琨，张帅，等.基于线程池的GPU任务并行计算模式研究[J].计算机学报，2018，41（10）：2175-2192.
LI T，DONG Q K，ZHANG S，et al.GPU task parallel computing paradigm based on thread pool model[J].Chinese Journal of Computers，2018，41（10）：2175-2192.
[10] STUART J A，CHEN C K，MA K L，et al.Multi-GPU volume rendering using MapReduce[C]//Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing.New York：ACM，2010：841-848.
[11] 梅鸿辉，陈海东，肇昕，等.一种全球尺度三维大气数据可视化系统[J].软件学报，2016，27（5）：1140-1150.
MEI H H，CHEN H D，ZHAO X，et al.Visualization system of 3D global scale meteorological data[J].Journal of Software，2016，27（5）：1140-1150.
[12] GOWANLOCK M，CASANOVA H.Indexing of spatiotemporal trajectories for efficient distance threshold similarity searches on the GPU[C]//2015 IEEE International Parallel and Distributed Processing Symposium，Hyderabad，India，2015：387-396.
[13] LUO L，WONG M.Parallel Implementation of R-trees on the GPU[C]//17th Asia and South Pacific Design Automation Conference，2012：352-358.
[14] PRASAD S K，MCDERMOTT M，HE X，et al.GPU-based parallel R-tree construction and querying[C]//2015 IEEE International Parallel and Distributed Processing Symposium Workshop，Hyderabad，India，2015：618-627.
[15] YOU S，ZHANG J，GRUENWALD L.Parallel spatial query processing on GPUs using R-trees[C]//Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data.New York：ACM，2013：23-31.
[16] COOK S.CUDA programming：a developer’s guide to parallel computing with GPUs[M].San Francisco：Morgan Kaufmann，2012.
[17] PIORKOWSKI M，SARAFIJANOVIC?DJUKIC N，GROSSGLAUSER M.CRAWDAD mobility dataset[DB/OL].[2009?02?24].https：//crawdad.org/epfl/mobility/20090224/index.html.
[18] BRINKHOFF T.Generating traffic data[J].IEEE Data Engineering Bulletin，2003，26（2）：19-25.