Research Of Dynamic Compound Indexing For Moving Objects Based On Road Distribution

Moving object indexing is the key point of moving object management, which consolidates the foundation of moving object database. Most current indexing methods of moving objects don't take the limitation of moving objects'motion into account. While, the motion of most moving objects is under some topology constrains. According to defects of road-network based FNR-Tree indexing method, we propose a road-distribution-based dynamic combined indexing method for moving objects, and analyze its performance. Performance analysis shows that this method can effectively manage the historical track information and current position information of moving objects in restrained road network.Based on the research on current indexing technologies and application requirements for road-network restrained moving objects, a dynamic combined indexing structure is proposed in this paper. The dynamic combined indexing structure proposed in this paper is a 3 layer structure: PMR QUAD tree, R tree and Hash structure. PMR QUAD tree is involved to layer division on rough granularity which divides the space of index into multi-layer sub-index space. The leave nodes of PMR QUAD tree in the bottom divide roads into sections and adopt each section to an R tree. The R tree manages the time information of all moving objects along some road section. As time goes on, time segment is dynamically added into the R tree. The spatio-temporal track information of each moving object is stored in the Hash structure, which consists of a hash table and a dynamic link list. The hash table holds moving object's identification, and each moving object points to a link list, which holds the time sorted location information of moving object in its node.Based on the dynamic combined index structure, we use points to connect each road segment belonging to the same road together in the node of PMR QUAD tree, which implements the spatio-temporal search of whole roads and middle-down dynamic update algorithm from parent nodes'information.In this paper, we use the T Brinkhoff's road network based moving object simulator and real road traffic map to produce the experimental data of moving objects on the road. We compare the performance of dynamic combined indexing and FNR tree indexing by the number of node access. The result shows, the road-distribution based dynamic combined indexing has edge on the aspects of dynamic updating, window search,especially track search.