Font Size: a A A

Hash-R Indexing Of Moving Point Objects And Reverse Nearest Neighbors Query

Posted on:2011-01-26Degree:MasterType:Thesis
Country:ChinaCandidate:H M LiFull Text:PDF
GTID:2178330332471484Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Moving objects is a branch of extensive research now. In this paper, we focus on moving point objects, and highlight its indexing structure and query technology in spatio-temporal database, since their wide application in our daily life and deep study value.In this paper, the work of the index structure are: First, give a detailed account of several spatio-temporal indexing technologies based on discrete data and continuous data expression. Second, the new Hash-R-tree indexing structure was proposed based on R-tree. We analysed build,insert and delete ideas, and designed build,insert and delete algorithm. Third, introduced two Hash secondary indexs built on the leaf nodes and root node to improve update and query performance. Forth, k-means clustering algorithm was introduced in creation for improving the quality of the index structure.The work of the query are: First, classified the query methods of moving objects from different angles and clarified the basic concepts. Second, the reverse nearest neighbor query of the Hash-R index structure was proposed. In the algorithm, introduced the concept of timestamps, discussed three cases so as to make the time scope to be the window scope, achieve a pre-cut off beyond a certain life cycle of the object information, and enhance query efficiency. Third, We seized the reverse nearest neighbor query definition, verify the correctness,validity,analyzability and readability through a validation algorithm of the result set. Forth, Experiments showed the reverse nearest neighbor algorithm scalability and I/O updating cost, and comparatively analyzed of the Hash-R tree and TPR tree query efficiency and disk access times.
Keywords/Search Tags:moving objects, Hash-R-tree index, reverse nearest neighbors query
PDF Full Text Request
Related items