Many new applications, such as multimedia databases, employ the so-called feature transformation which transforms important features or properties of data objects into high-dimensional points. Searching for 'similar' or 'non-dominated' objects based on these features is thus a search of points in this feature space. To support efficient query processing in these high dimensional databases, high-dimensional indexes are required to prune the search space and efficient query processing strategies employing these indexes have to be designed. Based on an analysis of typical advanced database systems - such as multimedia databases, electronic market places, and decision support systems - the following four challenging characteristics of complexity are detected: high-dimensionality nature of data, re-usability of existing index structures, novel (more expressive) query operators for advanced database systems and efficient analysis of complex high-dimensional data. Therefore, the general goal of this thesis is the improvement of the efficiency of index based query processing in high-dimensional data spaces and the development of novel query operators. The first part of this thesis deals with similarity query processing techniques. We introduce a new approach to indexing multidimensional data that is particularly suitable for the efficient incremental processing of nearest neighbor queries. The basic idea is to split the data space vertically into multiple low- and medium-dimensional data spaces. The data from each of these lower-dimensional subspaces is organized by using a standard multi-dimensional index structure. In order to perform incremental NN-queries on top of index-striping efficiently, we first develop an algorithm for merging the results received from the underlying indexes. Then, an accurate cost model relying on a power law is presented that determines an appropriate number of indexes. Moreover, we consider the problem of dimension assignment, where each dimen.