Storage of multidimensional arrays based on arbitrary tiling

Abstract

Storage management of multidimensional arrays aims at supporting the array model needed by applications and insuring fast execution of access operations. Current approaches to store multidimensional arrays rely on partitioning data into chunks (equally sized subarrays). Regular partitioning however, does not adapt to access patterns, leading to suboptimal access performance. We propose a storage approach for multidimensional discrete data (MDD) based on multidimensional arbitrary tiling. Tiling is arbitrary in that any partitioning into disjoint multidimensional intervals as well as incomplete coverage of n-D space and gradual growth of MDDs are supported. The proposed approach allows the storage structure to be configured according to user access patterns through tunable tiling strategies. We describe four strategies and respective tiling algorithms and present performance measurements which show their effectiveness in reducing disk access and post-processing times for range queries.