Temporal Indexing Technique Based on Structural Summary
Guo Huan, Tang Yong, and Ye Xiaoping
Related Articles |
With extensive applications of temporal data management technology, temporal index has become one important way to make efficient query and management for temporal data. Now, B+-tree is still the most widely used index structure in commercial databases. So, in order to make effective operation on temporal data in existing databases, it is necessary to research B+-tree based temporal index structure. A structural summary based temporal indexing structure—CMap-tree is proposed, which maps time interval into one-dimensional point when reserving the lexicographic order of time intervals and uses B+-tree as its basic storage structure. Firstly, a main memory structural summary is introduced, and by storing necessary structural summary information of nodes, invalid nodes visited during temporal operations (temporal inserting, querying and updating) have been reduced in greatest degree. Secondly, the concept of temporal matrix for time intervals is proposed, and then based on the temporal matrix, detailed analysis of the resulting set corresponding to each temporal relation is discussed. Then, based on the structural summary, temporal inserting, querying and updating algorithms of CMap-tree are discussed. Finally, the performance of CMap-tree is systemically analyzed and compared with that of other competitors in terms of space utilization, querying and updating performance. Extensive experiments show that CMap-tree has obvious advantages.