Abstract:  

Most of the existing spatial indices are constructed using a single hierarchal index structure; hence a large number of index pages (nodes) are most likely to be inspected during spatial query execution. Since spatial queries usually fetch spatial objects based on their spatial position in the space, it is significant that spatial objects are clustered in such a way that pertinent objects to a query are fetched quickly. This paper presents a method for partitioning the whole space into set of small subspaces. Then, an index structure for each subspace (called the Multi Small Index) is built. This makes it is easy to quickly retrieve spatial objects that are relevant to the query in question using their corresponding small spatial index structures and ignoring other irrelevant indices. To evaluate our new approach, we conducted a set of experimental studies using a collection of real-life spatial datasets (TIGER data files) with diverse sizes and different object sizes, densities and distributions, as well as various query sizes. The results show that (using small query sizes) our proposed structure (Multi Small Index) outperforms the original R-tree (Single Big Index) structure, achieving nearly 50% saving in disk access.