External Segment Trees

Blankenagel, Gabriele; Güting, Ralf Hartmut GND

The segment tree is a well known internal data structure with numerous applications in computati.onal geometry. lt allows to maintain dynamically a set of intervals such that the intervals enclosing a query point can be found efficiently (point enclosure search). In this paper we transfer the underlying principle of the segment tree in a non-trivial way to secondary storage and arrive at the EST - an external file structure with the same functionality and the following properties: (1) Point enclosure searches are very efficient - only very few pages are accessed that are not filled to more than 50% with result intervals. (2) A page filling of 50% is guaranteed - on the average it will be around 70%. Although the segment tree represents in the worst case each interval by a logarithmic number of fragments, in practical cases fragmentation remains low and the storage requirements about linear. (3) The EST is balanced and the update algorithms are efficient. (4) Unlike many other file structures for spatial objects the EST has no problems with an arbitrary density, that is, an arbitrarily !arge number of intervals covering any point of the line. Furthermore, the EST can be used as a file structure constructor in the following sense: Let there be a file structure X supporting searches for objects with property x and suppose one needs to maintain a collection of objects with associated (e.g. time) intervals. Then one can build an EST-X structure that supports searches for objects with property x present at time t. This suggests to use the EST as a building block in the implementation of temporal database systems. Other applications include the one-dimensional indexing of collections of spatial objects in two or more dimensions. More generally, this paper shows techniques for mapping internal tree structures with node lists (other examples: range tree, interval tree) to secondary memory. In this context, an intriguing theoretical problem, the cover balancing problem, is solved: Given a tree whose nodes have associated weights partitioned into subtrees whose weights must lie in' a certain range, maintain this partition under weight changes at arbitrary nodes. This is in contrast to classical balancing problems where updates occur only at the leaves.




Blankenagel, Gabriele / Güting, Ralf: External Segment Trees. Hagen 1990. FernUniversität in Hagen.


12 Monate:

Grafik öffnen


Nutzung und Vervielfältigung:
Alle Rechte vorbehalten


powered by MyCoRe