Research On The Index Of Moving Objects

With the development of Internet technology and mobile communication technology,location-based services, such as mobile positioning and vehicle monitoring, present a demand ofmanaging the databases effectively, leading to the quick development of the research of MovingObjects Databases.In the research of Moving Objects Databases, the indexing of moving objects is an important andkey technology. At present, there are two problems in the study of indexing moving objects: 1)Mostindex structures of moving objects only support indexing moving objects’ historical information orfuture information, lacking of the ability of indexing about the past, the present and the anticipatedfuture positions of moving objects; 2) Objects’ movements are mostly limited by fixed networks inpractical applications, but the traditional index structures can’t deal with this situation. So, the study ofindexing moving objects in fixed networks about their past, present and future information is needed.On the other hand, the current computing system is being developed to be distributed and parallel.Additionally, Moving Objects Databases has the character of dealing with a large amount of datawhich has the high real-time demand. To deal with these situations, i.e. improving the processefficiency, and meeting the demands of multi-users, the study of the indexing moving objects indistributed and multi-user systems is also needed.To solve the problems above, the following works were carried out in this paper:1) The related technologies of indexing moving objects were studied. The main index structuresof moving objects used at present were also investigated, with their advantages and disadvantagesbeing pointed out. In addition, the problems of the current indexing technology were analyzed.2) A method to index past, current and future positions of moving objects in networks wasproposed. In this method, an index structure called MSMON was designed. It uses a group of Hashtables and Adjacency matrixes as assistant structures to support indexing past, current and futurepositions of moving objects. The constructing algorithm, updating algorithm and trans-storingalgorithm of MSMON were given.3)The query methods based on the above index structures were provided. Using MSMON,updating from bottom to up, nearest neighbor queries, timestamp queries and interval queries could allbe supported. The detailed methods were given.In the paper, an experiment was conducted to test the methods mentioned above. The result showed that the MSMON limited the dead spaces and overlapped areas caused in traditional indexstructures within an acceptable range and increased efficiency through managing moving objects’information by dividing time into segments. It also showed that the MSMON supported updating frombottom to up by using Hash tables, while supporting different types of queries. Thus, MSMON ismore effective than the MON-tree, which is currently widely used to index moving objects in network.It is more suitable for the practical applications. Also, because MSMON managed data by dividingtime into segments, it could be parallelly executed easily.4)The memory management mechanisms in single-core, multi-core and distributed systems, andthe similarities and differences among the mentioned three systems were studied. The key technologyto implement Distributed Shared Memory (DSM) was also investigated. Based on the above work, aDSM was implemented to manage memories in multi-machine environment. In the implementedDSM, network programming technology, namely Socket, was used to realize the communicationsamong all the node computers, making all the node computers work harmoniously. The strategies toallocate and free memories, locate information, and maintain consistency etc. were also provided.5)Based on the DSM implemented in this paper, a method to index moving objects in DSMsystem, called DSM_MSMON, was presented. The DSM_MSMON could be used to manage past,current and future information of moving objects in parallel in a distributed system. TheDSM_MSMON could also support various query methods. An experiment was carried out and itshowed that DSM_MSMON supported the index of moving objects of their past, current and futurepositions in the distributed system with superior operating efficiency of updating and querying, andcould satisfy the demands of different users at the same time.