Research Of The Indexing For Trajectories' Nearest Neighbors Based On Spatio-Temporal Databases

The development of Spatio-Temporal Databases is based on the Spatial Databases and Temporal Databases. The research on Spatio-Temporal Databases is more complicated than that of the Spatial Databases and Temporal Databases because of the unique data form in Spatio-Temporal Databases—moving objects.The indexing and query in Spatio-Temporal Databases compose of the important part of the key research problems of Spatio-Temporal Databases. The performance of query determines that of Spatio-Temporal Databases because query is the primary operation in Databases. Moreover, a good indexing mechanism also determines high performance of query. Establishing an indexing mechanism with high performance is the most important thing to Spatio-Temporal Databases with a large number of data.Firstly, we introduce the relative knowledge about Spatio-Temporal Databases, and explain the relative conception and theory. At the same time, the indexing and query methods of Spatio-Temporal Databases are classified, respectively.Secondly, we research and analyze the existing main indexing structures in Spatio-Temporal Databases. we mainly introduce the R-tree variants, and emphatically, classify and summarize systematically and completely the indexing methods for moving objects in Spatio-Temporal Databases, and analyze the main ideas and existing advantages and drawbacks, respectively. Thirdly, we classify the problems of the nearest neighbor query, and give the definition accordingly. The nearest neighbor query methods for static objects and those for moving objects are mainly analyzed. Last, we propose a new indexing structure for trajectories'nearest neighbors based on Spatio-Temporal Databases. This indexing structure is improved from R-trees. It introduces two auxiliary storage structures. One is list structure for dynamic storing the nearest neighbors information of moving objects, and the other is auxiliary cache for accessing directly leaf nodes. According to the indexing structure, the time-slice nearest neighbor query algorithm and interval nearest neighbor query algorithm are proposed, and the performance evaluation is given. The experiment shows that because of the introduction of the two auxiliary storage structures, the nearest neighbor query time is reduced significantly, and therefore, the performance of the nearest neighbor query based on the indexing structure is improved.