【作者】 刘晓军；

【导师】 张世栋；

【作者基本信息】 山东大学 ， 计算机软件与理论， 2007， 硕士

【摘要】 随着3G时代的到来和众多具有定位功能的无线手持设备的大量普及,促使一类基于位置的服务,称为位置相关服务(location based service,LBS)成为可能。相应的移动对象的位置追踪也变得越来越可行和必需,这就需要有一种高效的索引结构来定位移动对象的位置。然而传统的移动对象时空索引技术不能同时有效地支持对移动对象的过去、现在和将来位置的查询,这是由空间数据的复杂性和移动对象的动态易变属性造成的。本文提出的TEBx(Time Entropy Bx)混合索引结构,在Bx树索引结构的基础上进行了改进,并且增加了建立在叶结点之上的hash辅助索引表来支持对象的频繁更新操作,能够有效地解决上述问题。它简化了索引关键字来增大索引的时间跨度,通过使用线性时间函数来表征移动对象的位置,可以索引移动对象从过去到将来的位置;该索引结构同时引入时间熵,用来表征数据库中移动对象的位置信息随时间增长的衰减度量,故能定期剪除那些存储超过一定期限的对象信息,维持索引结构处于某个稳定的规模以提高系统的索引效率。该索引结构将移动对象的位置存储在一个B+树森林中,它可以有效地支持对移动对象的过去、现在和将来位置的查询:同时它也有效地支持时间跨度较大的时空范围查询和基于时间地点受限的集合查询,例如查询那些在一个时间间隔集合内都位于一个特定的空间区域内的移动对象:并且与Bx树索引结构相比,由于TEBx混合索引结构引入的hash辅助索引表能够有效地支持自底向上的局部更新策略,所以它也具有较高的插入、删除及更新效率。更多还原

【Abstract】 With the arrival of 3G and the popularity of substantive wireless devices that have the locating function, a location-based service (LBS, for short) becomes possible. Accordingly, tracking moving objects in the corresponding position has become increasingly feasible and necessary, so we need some indexing structure that has high efficiency to locate the positions of moving objects. However, the traditional spatial-temporal indexing techniques for moving objects can not simultaneously and efficiently support the query about the past, present and future positions of moving objects, this is induced by the complexity of the spatial data and the dynamic attribute of the moving objects.The TEB~x (Time Entropy B~x) mixed indexing structure proposed in this paper, which being improved based on the B~x-tree indexing structure and adding the Hash auxiliary index-table to support the frequent update of moving objects , can efficiently solve the problem presented above. It simplifies the indexing keyword in order to increase the indexing temporal span, and expresses the positions of moving objects by using the linear function of time, so it can index the positions of moving objects from past to future; at the same time, the indexing structure introduces the time entropy for denoting the decreasing measurement of the positional information of moving objects in database as time increasing, so it can termly prune those positional information of moving objects which being stored beyond a definite period, and maintain the indexing structure on a steady size to improve the indexical efficiency of the system.The TEB~x-mixed indexing structure stores the positions of moving objects in a B~+-tree forest, it can efficiently support the query about the past, present and future positions of moving objects; it also supports the spatial-temporal rang query with the larger temporal span and the queries that select objects based on temporal and spatial constraints, such as queries that retrieve all objects whose positions fall within a spatial range during a set of time intervals at the same time; Compared with the B~x-tree indexing structure, because the Hash auxiliary index-table introduced by the TEB~x-mixed indexing structure can efficiently support the bottom-to-up partial update strategy, so it also has higher insertion, deletion and updating efficiency.更多还原