Query- adaptive data space partitioning using variable-size storage clusters

All spatial access methods decompose the data space into a number of subspaces or cells. The size of a cell is determined by the capacity of a single disk page. Here we present considerations on data space partitions which use large multi-page storage clusters of variable size rather than single pages. Its main motivation is given by real complex geographical objects ranging from 100 Bytes to 10 KBytes in storage size. For such objects it does not make sense to insist on the one-page-per-cell paradigm. The problem of determining “good” multi-page storage clusters is attacked by introducing a cost model. In the ideal case an expected query is satisfied by accessing only one storage cluster of appropriate size. To get near to this optimum we adapt the data space partition to query ranges. We call this approach a query driven partitioning strategy. Initial evaluation studies show the feasibility of this approach.