A Novel Geo-Spatial Image Storage Method Based on Hilbert Space Filling Curves

摘要

Massive Geo-Spatial image data play an increasing important role in mapping, resource and environmental research recently, usually it is stored on external storage for its massive data volume within some image files or spatial database, where image storage organization is still a major bottleneck of range query performance. In contrast to the one-dimensional data, the multi-dimensional data such as Geo-spatial image is far more complex, since there is no obvious storage method that serves all purposes. The image data blocks' are stored as separate documents on external storage. Due to the external hard disk storage facility is one-dimensional, and the spatial order of image blocks has a direct impact on the performance of range queries. Several Space Filling Curves (SFC) have been proposed, and the most prominent ones include the Z-order (also known as Morton encoding), the Gray code and Hilbert's curve. In fact the multidimensional interval in range queries can be transformed into several one-dimensional intervals. The preserving spatial proximity in SFC help the image blocks keep possible spatial proximity if it is stored according to SFC. Our previous storage experiment has shown that node sequencing distance in curve for each two spatial adjacent nodes is essential for range query performance, especially for distributed system. In the analysis of Hilbert's curve, we find that Hilbert's curve has high frequency distribution of short sequencing distance in curve for each two spatial adjacent nodes, it is very conducive to efficient regional access, while there exists some super large sequencing distance for spatial adjacent nodes, and those nodes leads to Hilbert curve's average adjacent node distance is larger than ordinary sequence and Z-line order. According to the above experiment, we present a novel geo-spatial storage method based on Hilbert SFC in this paper, and the method use the benefits of Hilbert SFC such as recursive attribute and preserving proximity, but have some adjustments to Hilbert SFC. We stored additional 2~(n-1) specific nodes in n-th curve according to our definition, and this method lead to good query performance than existing method. The merit of this method is that it can be used in massive geo-spatial image and has the balance of retrieval efficiency and storage overhead.