A Triangular Decomposition Access Method for Temporal Data - TD-tree

Stantic, B., Topor, R., Terry, J. and Sattar, A.

In this study, we investigate and present a new index structure, Triangular Decomposition Tree (TD- tree), 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 manage spatio-temporal data.

Cite as: Stantic, B., Topor, R., Terry, J. and Sattar, A. (2011). A Triangular Decomposition Access Method for Temporal Data - TD-tree. In Proc. Australasian Database Conference (ADC 2011) Perth, Australia. CRPIT, 115. Heng Tao Shen and Yanchun Zhang Eds., ACS. 113-122

(from crpit.com) (local if available)