Advanced indexing technique for temporal data
Advanced indexing technique for temporal data
复制标题
DOI：
10.2298/csis101020035s
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Bela Stantic;R. Topor;Justin Terry;A. Sattar
中科院分区：
文献类型：
--
作者：
Bela Stantic;R. Topor;Justin Terry;A. Sattar
在现代数据库应用中，对时间相关数据的有效访问和管理的需求得到了充分的认识和研究。现有的访问方法大多源于空间R树索引技术家族。这些技术尤其不适合处理涉及开放间隔的数据，这在时态数据库中很常见。这是由于节点之间的重叠和数据库中发现的巨大死区。在这项研究中，我们描述了一种名为“三角分解树”(TD-Tree)的新方法。TD-Tree的基本思想是通过依赖于区间的几何解释的虚拟索引结构和导致不平衡二叉树的空间划分方法来管理时间区间。我们证明了使用虚拟索引可以有效地操作不平衡二叉树。我们还表明，单一查询算法可以统一地应用于不同的查询类型，而不需要专门的查询转换。除了针对不同的查询类型使用单一查询算法和更好的空间复杂性相关的优势外，TD-tree的经验性能也被发现优于其最著名的竞争对手。
The need for efficient access and management of time dependent data in modern database applications is well recognized and researched. Existing access methods are mostly derived from the family of spatial R-tree indexing techniques. These techniques are particularly not suitable to handle data involving open ended intervals, which are common in temporal databases. This is due to overlapping between nodes and huge dead space found in the database. In this study, we describe a detailed investigation of a new approach called “Triangular Decomposition Tree” (TD-Tree). The underlying idea for the TD-Tree is to manage temporal intervals by virtual index structures relying on geometric interpretations of intervals, and a space partition method that results in an unbalanced binary tree. We demonstrate that the unbalanced binary tree can be efficiently manipulated using a virtual index. We also show that the single query algorithm can be applied uniformly to different query types without the need of dedicated query transformations. In addition to the advantages related to the usage of a single query algorithm for different query types and better space complexity, the empirical performance of the TD-tree has been found to be superior to its best known competitors.