Herman Haverkort
R-Trees with bounded query time
R-trees are multi-purpose data structures for storing
multi-dimensional data. Their popularity is due to the simplicity of
the structure and the good query times which are achieved in
practice. However, the query times can depend a lot on the algorithm
used to construct the tree, the data which is stored, and the queries
asked. Traditional research into R-trees has been focussed on
developing sophisticated heuristic algorithms, which are then compared
to two or three other algorithms in a limited, not always realistic,
test setting.
As a result, R-trees are in general likely, but not guaranteed to
answer queries quickly. Theoretical and experimental research done so
far provides only limited insight in the circumstances under which an
R-tree could perform very poorly, and how we could avoid this
behaviour.
In my talk, I will give a brief introduction about R-trees. I will
give a few (theoretical) examples of input data which may lead to long
worst-case query times. I will show how these examples inspired us to
design new R-tree algorithms for two- and three- dimensional data,
that yield bounded, sometimes even near-optimal, worst-case query
times.
Dietmar Lammers
Last modified: Fre Jan 10 14:02:20 CET 2003