城市路网上动态迁移的移动对象索引结构

摘要

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