(last updated June 17, 1998)
STLT: Small Tree bulk inserted into Large Tree
A lot of recent work has focussed on bulk loading of data into multidimensional index structures in order to efficiently construct such structures for large datasets. Previous work on bulk loading data focussed at building index structures it from scratch, while the problem of bulk insertions into existing index structures has been largely overlooked. In this paper, we address this new problem with particular focus on R-trees. We propose a new technique, which as opposed to the current technique of inserting data one by one, bulk-inserts entire new datasets into an active R-tree. This technique is called STLT (for Small-Tree-Large-Tree). Our experimental results indicate that the quality of the resulting tree constructed by STLT in terms of query performance is acceptable and in many cases even preferable over that created by the traditional tree insertion approach.
Some previous work (including the Code Base) is done by students in UMich.