计算机工程 ›› 2008, Vol. 34 ›› Issue (24): 46-48.doi: 10.3969/j.issn.1000-3428.2008.24.016

• 软件技术与数据库 • 上一篇    下一篇

基于R*-tree的时空数据库索引VC-tree

张桂杰,岳丽华,金培权   

  1. (中国科学技术大学计算机系,合肥 230027)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-12-20 发布日期:2008-12-20

VC-tree: Spatial-temporal Database Index Based on R*-tree

ZHANG Gui-jie, YUE Li-hua, JIN Pei-quan   

  1. (Department of Computer, University of Science and Technology of China, Hefei 230027)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-12-20 Published:2008-12-20

摘要: 在时空数据的索引结构中,HR-tree可以高效处理时间片查询,但对时间段查询效率低下,同时存在存储冗余。3D-tree索引的效率较低,双树结构使索引维护较为困难,且磁盘访问开销大。该文提出一种新的基于R*-tree的索引结构VC-tree,便于管理维护,可以高效满足时空查询,并满足有效时间内的未来查询。

关键词: 时空数据库索引, R-tree索引, HR-tree索引, VC-tree索引

Abstract: The Historical R-tree(HR-tree) is a spatial-temporal access method. Since all objects are indexed by a single tree, the size and height of the tree is expected to be larger than that of the corresponding HR-tree at the query timestamp. However, the space requirements of HR-trees are still prohibitive in practice, because for most typical datasets HR-trees almost degenerate to independent R-tree, one for each timestamp. Their performance deteriorates very fast for interval queries as the interval length increases. And 3D-tree is another spatial-temporal access method. The retrieval of objects according to their spatial-temporal relationships with others, demands access to both indexes and, in a second phase the computation of the intersection set between the two answer sets. Access to both indexes is usually costly and, in many cases, most elements of the two answer sets are not found in the intersection set.

Key words: spatial-temporal database index, R-tree, HR-tree, VC-tree

中图分类号: