'TRP-tree Running in Main Memory'

Student thesis: Master Thesis and HD Thesis

  • Beata Nitkiewicz
  • Michal Panczyk
10. Term, Master Knowledge and Data Engineering (Continuing Education Programme (Master))
'As the branch of business, where locations based services matter, grows, the demand for reliable and fast spatio temporal databases capable of indexing dynamical data rises. The number of data structures able to handle this requirements is significantly small, thus the pressure on researchers grows to work on the reliable solutions. One of the idea to improve the performance is to move the traditional databases in to the main memory. As the memory chips prices are falling the idea is starting to become reality.
In this paper we investigate how the TPR-tree, as a data structure originally implemented to the disk oriented environment, behaves in the main-memory. We verify, wide-spread thesis of memory access time as the first-ordered bottleneck for in-memory indexes, by running experiments on the TPR-tree. Furthermore we stress that performance of the index structure running in main-memory is measured in different way and different indicators need to be considered. Experimental analysis leads us to the conclusion that the TPR-tree is to CPU heave structure and the simplest methods of improvements are achieved by limiting the number of needed computations. In order to demonstrate the path for the future analyses we introduce three different improvements for the update algorithms: lazy delete, bottom-up delete and new penalty insert. '
Publication dateAug 2006
ID: 61068335