  Efficient evaluation of multi-dimensional range queries in a main-memory
database is an important, but difficult task. State-of-the-art techniques rely
on optimised sequential scans or tree-based structures. For range queries with
small result sets, sequential scans exhibit poor asymptotic performance. Also,
as the dimensionality of the data set increases, the performance of tree-based
structures degenerates due to the curse of dimensionality. Recent literature
proposed the Elf, a main-memory structure that is optimised for the case of
such multi-dimensional low-selectivity queries. The Elf outperforms other
state-of-the-art methods in manually tuned scenarios. However, choosing an
optimal parameter configuration for the Elf is vital, since for poor
configurations, the search performance degrades rapidly. Consequently, further
knowledge about the behaviour of the Elf in different configurations is
required to achieve robust performance. In this thesis, we therefore propose a
numerical cost model for the Elf. Like all main-memory index structures, the
Elf response time is not dominated by disk accesses, refusing a straightforward
analysis. Our model predicts the size and shape of the Elf region that is
examined during search. We propose that the response time of a search is linear
to the size of this region. Furthermore, we study the impact of skewed data
distributions and correlations on the shape of the Elf. We find that they lead
to behaviour that is accurately describable through simple reductions in
attribute cardinality. Our experimental results indicate that for data sets of
up to 15 dimensions, our cost model predicts the size of the examined Elf
region with relative errors below 5%. Furthermore, we find that the size of the
Elf region examined during search predicts the response time with an accuracy
of 80%.
