In this study, we investigate and present a new index structure, Triangular Decomposition Tree (TDtree), which can efficiently store and query temporal data in modern database applications. TD-tree is based on spatial representation of interval data and a recursive triangular decomposition of this space. A bounded number of intervals are stored in each leaf of the tree, which hence may be unbalanced. We describe the algorithms used with this structure. A single query algorithm can be applied uniformly to different query types without the need of dedicated query transformation. 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 is demonstrated to be superior to its best known competitors. Also, presented concept can be extended to more dimensions and therefore applied to efficiently mage spatio-temporal data.

Presented at Conferences

  • Twenty-Second Australasian Database Conference (ADC 2011) (2011)

    Perth, Australia