Analysis of two-step index structure for complex spatial objects

An efficient index structure for complex spatial objects is one of the most challenging requirements in non-traditional applications such as geographic information systems (GISs), computer-aided design (CAD), and multimedia databases. In this paper we first propose an extension of an existing index structure called the two-step index structure (TSIS). The TSIS integrates two index structures, one for original objects and the other for their decomposed components. Then, we present a cost model that predicts the performance of the TSIS. In contrast to several earlier investigations on this subject which only considered the filter step, we take into account the performance of the refinement step. Experimental results show that the cost model is accurate, the relative error being below 15%. The performance of our index structure is compared with that of a state-of-the-art index structure by experimental measurements. Our index structure outperforms the state-of-the-art index structure due to its ability to reduce a large amount of storage.