城市路网上动态迁移的移动对象索引结构-《计算机技术与发展》

文章信息/Info

Title:: A Moving Object Index Structure of Dynamic Migration on Urban Road Network

作者:: 张郁彬1 2 ; 张深深3 ; 孟旭东1 2; 1. 宽带无线通信与传感网技术教育部重点实验室,江苏南京 210003;
2. 南京邮电大学江苏省电信网络融合实验室,江苏南京 210003;
3. 南京邮电大学计算机学院,江苏南京 210003

Author(s):: ZHANG Yu-bin1 2 ; ZHANG Shen-shen3 ; MENG Xu-dong1 2; 1. Key Lab of Broadband Wireless Communication and Sensor Network of Ministry of Education,Nanjing 210003,China;
2. Jiangsu Telecom Network Fusion Laboratory,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;
3. School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China

Keywords:: urban road network; hotspot area; moving object; dynamic migration; indexing technology

摘要:: 移动对象索引技术是有效管理海量移动对象数据的支撑。目前的移动对象索引方法如 FNR-tree、NDTR-tree 等均采用基于磁盘的索引结构,忽略了移动对象在城市道路上密度分布不均衡的情况,因此在移动对象位置更新频繁时,该类方法的性能会严重下降。针对以上不足,提出一个针对城市路网上热点区域变化进行内外存索引迁移的结构(hot-spots dynamic migration index,HDMI)。 HDMI 是双层索引结构,上层采用 R*-tree 对路网数据进行管理,下层釆用 R-tree群对实时更新的移动对象运动信息进行索引。 HDMI 采用基于内存的索引结构管理热点区域和该区域中的移动对象,针对非热点区域和其中的移动对象则采用基于外存的索引结构来进行管理。 HDMI 能够根据道路上车辆密度的变化进行内外存索引的迁移,从而在有限的内存条件下,保障索引更新和查询的性能。实验结果表明,HDMI 于 NDTR-tree 相比,不仅减少了索引建立和维护的 I/ O 代价,而且提高了时空窗口查询处理性能。

Abstract:: Moving object indexing technology is the support for managing the massive moving object data effectively. The current moving object indexing methods such as FNR-tree and NDTR-tree adopt the disk-based index structure,and ignore the situation that the density distribution of the moving objects is reduced on the urban road,so when the moving object location updates frequently,the performance of the index method will be a serious decline. Aiming at the shortcomings of the above methods,we propose a structure for the internal and external index migration of urban hotspots (hot-spots dynamic migration index,HDMI). It is a double-layer index structure,the upper layer uses R *-tree to manage the network data,and the lower layer uses the R-tree group to index the moving object motion information updated in real time. HDMI uses a memory-based index structure to manage hotspots and moving objects in that area,and for nonhotspot areas and moving objects in them,they are managed using an external-based indexing structure. It can carry on the migration of the internal and external index based on the vehicle density changes on the road,which in limited memory conditions,to protect the index update and query performance. Experiments show that HDMI reduces the I/ O cost of index creation and maintenance compared to NDTR-tree,and improves the performance of space-time window query processing.