In this paper we propose a new approach for efficiently answering spatial queries (intersections, containments, enclosures) over large databases of multi-dimensional objects (hypercubes). A wide range of applications could benefit of our technique: image retrieval, document indexing, time series, notification systems, and other applications involving multi-dimensional spatial data. Our contribution consists in the definition of an approximation model for multi-dimensional objects and spatial operations, which accelerates the object verification and enables a database organization in clusters, to avoid the exhaustive database scan. The grouping strategy based on access probabilities allows the clustering to behave efficiently against skewed data and/or skewed queries. Performance analysis shows that our approach efficiently copes with large databases with many dimensions. Our method supports incomplete and heterogeneous objects (defined on different dimension subsets) and objects with large extensions on their dimensions.