Spatial queries in high-dimensional spaces have been studied extensively. Among them, nearest neighbor queries are important in many settings, including spatial databases (Find the k closest cities) and multimedia databases (Find the k most similar images). Previous analyses have concluded that nearest-neighbor search is hopeless in high dimensions due to the notorious "curse of dimensionality". We show that this may be overpessimistic. We show that what determines the search performance (at least for R-tree-like structures) is the intrinsic dimensionality of the data set and not the dimensionality of the address space (referred to as the embedding dimensionality). The typical (and often implicit) assumption in many previous studies is that the data is uniformly distributed, with independence between attributes. However, real data sets overwhelmingly disobey these assumptions; rather, they typically are skewed and exhibit intrinsic ("fractal") dimensionalities that are much lower than their embedding dimension, e.g. due to subtle dependencies between attributes. We show how the Hausdorff and Correlation fractal dimensions of a data set can yield extremely accurate formulas that can predict the I/O performance to within one standard deviation on multiple real and synthetic data sets.

Nearest neighbor queries are important in many settings, including spatial databases (find the k closet cities) and multimedia databases (find the k most similar images). Previous analyses have concluded that nearest neighbor search is hopeless in high dimensions, due to the notorious "curse of dimensionality". However, their precise analysis over real data sets is still an open problem. The typical and often implicit assumption in previous studies is that the data is uniformly distributed, with independence between attributes. However, real data sets overwhelmingly disobey these assumptions; rather, they typically are skewed and exhibit intrinsic ("fractal") dimensionalities that are much lower than their embedding dimension, e.g., due to subtle dependencies between attributes. We show how the Hausdorff and correlation fractal dimensions of a data set can yield extremely accurate formulas that can predict I/O performance to within one standard deviation. The practical contributions of this work are our accurate formulas which can be used for query optimization in spatial and multimedia databases. The theoretical contribution is the 'deflation' of the dimensionality curse. Our theoretical and empirical results show that previous worst-case analysis of nearest neighbor search in high dimensions are over-pessimistic, to the point of being unrealistic. The performance depends critically on the intrinsic ("fractal") dimensionality as opposed to the embedding dimension that the uniformity assumption incorrectly implies.

We stress the need of a domain-tailored requirements engineering method for the development of GIS-applications. To this end, we discuss three GIS-application scenarios we have frequently encountered in real life projects. Our investigation reveals that conventional RE-methods like Coad/Yourdon's Object-Oriented Analysis (OOA) are not capable of modelling GIS-specific requirements appropriately. To overcome the deficiencies of conventional OOA we introduce GEOOOA which extends OOA by domain-tailored primitives and allows for a more adequate treatment of GIS-specific requirements. We provide GEOOOA-models of three application scenarios which serve as first validation steps for the usefulness of the approach. Finally, we propose some methodological advices for a proper application of GEOOOA and sketch the GEOOOA-tool environment.

In this paper, we characterize the eciency of spatial access structures in terms of the expected number of data bucket accesses needed to perform a range query. We derive performance formulas for various kinds of range queries like intersection, containment, and enclosure queries with dierent geometric shapes. The formulas exhibit that range query performance in general depends on three parameters: the area sum of the data regions, the perimeter sum, and the number of regions. Only the weights of these parameters vary from shape to shape and query type to query type. To a wide extent, our results prove the conjecture that window queries are representative for range queries in general.

During the last decade various spatial data structures have been designed and compared against each other with respect to their performance. Still missing is a lower bound result, e.g. an optimal spatial data clustering, which would allow for the absolute comparison of the performance of the well-known data structures with the optimum. In this paper, we address the static situation where the data is known in beforehand. An optimal data clustering for this setting will also provide a lower bound for the dynamic situation where the input data is not known in advance and the data structure is built up by iterated insertions. Using as performance measure the expected number of data bucket accesses needed to perform a window query, the static clustering problem turns into a classical optimization problem. For the special case of bucket capacity cb = 2 the optimization problem is solvable in polynomial time, whereas for cb 3 it is NP-hard. In experiments using simulated annealing heuristics...

In this paper, we motivate four different user defined window query classes and derive a probabilistic model for each of them. For each model, we characterize the efficiency of spatial data structures in terms of the expected number of data bucket accesses needed to perform a window query. Our analytical approach exhibits the performance phenomena independent of data structure and implementation details and whether the objects are points or non-point objects.