Space-time Database Update Strategy Based On The Tpr, ~ *-tree Index

Spatio-Temporal Database (STDB) is new field in computer science, specially, every kind of indices have been researched and used in applications. As location based services grow in popularity and the number of mobile devices that needs to be tracked multiplies, it is possible (and likely) that an index will process hundreds of thousands of updates each update cycle. Needless to say the importance of index scalability under frequent updates is paramount.A large number of modern predictive spatio-temporal access methods have evolved from the R-Tree proposed by Guttman. However, despite of the R-Tree's popularity, many researchers have criticized its performance under frequent updates.In this thesis, we first review the STDB and the indces that have been or been being researched. Specially, wo focus on the two most important R-Tree based indices, i.e. TPR-Tree and TPR*-Tree. We will concentrate on the operations and the corresponding performance. Their deletion and insertion, which involve from those of R-Tree, have to traverse the tree for several times, resulting in the worst performace in frequent updates. Activated by this, we propose our solution which is called Improved Update TPR*-Tree(IU-TPR*-Tree, for short).We studied the contribution of Lee et al. on bottom-up update strategy and developed it to be used on TPR*-Tree to reduce I/O and CPU Time. In the new algorithm, wo uses four auxiliary strctures to memory some necessary information to reduce traversals, leading to better update performace. We show empirically that on average the IU-TPR*-Tree incurs nearly thirty percent less disk I/Os per update and processes updates twenty percent as fast as its top-down counter-part.The main contributions of this thesis:i) In order to have a good performance in frequent updates, we add four auxiliary structures to the TPR*-Tree update strategy.ii) We have to issue a hybrid update(a bottom-up deletion and a top-downinsertion) when a complete bottom-up update cannot take effect. But it iseffective.iii) Use a actively tighten mechanism.