Object and query transformation: Supporting multi-dimensional queries through code reuse

The complexity of deploying high-performance spatial structures in transactional DBMS environments has motivated researchers to experiment with the idea of reusing the effort invested in developing a traditional indexing scheme. To enable reuse, the design of a spatial access method must employ a form of object transformation that maps extended objects in the original space into points of a dual space. If these points are further transformed into one-dimensional keys, they can be indexed by any traditional scheme for exact-match retrieval, e.g. B +-trees. This paper investigates the performance of two generations of object transformation schemes in both low- and high-dimensional spaces. The first-generation object transformation provides relatively good performance in low-dimensional spaces. But, as the number of dimensions grows, its performance deteriorates quickly. The second generation scheme applies a query transformation that refines an idea, introduced in connection with the design of LSD-trees, of limiting the search space by taking into account properties of the actual data set. The refined secondgeneration scheme enables a rapid deployment of a spatial access method while achieving performance comparable to that of advanced monolithic schemes