# RSIMS: Large-Scale Heterogeneous Remote Sensing Images Management System
## 2 Materials and Methods
### RSIMeta: Metadata Management of Large-Scale Images with Heterogeneous Structures
#### 2.2.2 Remote Sensing Images Index and Retrieval Based on Hilbert Curve  
Based on Hilbert curve, we first divide the global world (\(-180\), \(-90\), \(180\), \(90\)) into multi-level grids from \(0\) to \(32\). The level \(0\) grid is the biggest grid covering the whole world. The size of the grid in Level \(k\) is \(\left(360/2^{k},\ 180/2^{k}\ \right)\). To distribute remote sensing images across different database servers, we adopt the level \(3\) Hilbert grids as the basic reference grid system, shown as Figure 4. All the remote sensing images intersecting with the same Hilbert grid are stored in the same database. The black dotted line in Figure 4. is the path along which the Hilbert curve connect all the grids. These grids are encoded from \(000\) to \(333\) expressed with quaternary system, and all the remote sensing images are encoded with the level \(3\) Hilbert codes (denoted by \(C_{0}\)) based on their center coordinates. Remote sensing images encoded with different codes can be stored in different databases which would improve the capacity scalability and I/O concurrency. The amount of remote sensing images in a single grid may still be too large. For better retrieval efficiency, the remote sensing image in a single grid is further encoded into a longer Hilbert code (denoted by \(C_{1}\)). After that, complex spatial intersection operation can be transformed into simple string code matching. The structure of two-tier distributed spatial index is shown as Figure 5.  
The cost of Hilbert code computation is key to the efficiency of distributed spatial index building. To speed up the process, we implemented the Hilbert code calculating algorithm based on the state-transition matrix, which is described in detail below. As shown in Figure 6, Hilbert curve have four types of basic shapes, which are encoded respectively as \(T_{1}\), \(T_{2}\), \(T_{3}\), \(T_{4}\). All Hilbert curves are constructed from these four basic shapes recursively. To describe the construction rules clearly, we encode the sub-grids respectively as \(G_{1}\), \(G_{2}\), \(G_{3}\), \(G_{4}\) based on their related locations. Figure 4: Basic global Hilbert grids. Figure 5: Structure of two-tier distributed spatial index. Suppose that \(T_{p}\) is the type of Hilbert curve that connecting four grids \((g_{k}^{1},g_{k}^{2},g_{k}^{3},g_{k}^{4})\) in \(level_{k}\), and \(T_{c}\) is the type of Hilbert curve connecting four grids \((Grid_{k-1})\) in \(level_{k-1}\) which are generated by subdividing one of the above four grids. The rules of Hilbert curve construction are listed as below:  
1. \(T_{c}\) is same as \(T_{p}\) if \(Grid_{k-1}\) are generate from \(g_{k}^{2}\) or \(g_{k}^{4}\);
2. \(T_{c}\) is generated from rotating \(T_{p}\) 90 degrees clockwise if \(Grid_{k-1}\) are generate from \(g_{k}^{1}\);
3. \(T_{c}\) is generated from rotating \(T_{p}\) 90 degrees counterclockwise if \(Grid_{k-1}\) are generate from \(g_{k}^{3}\);  
Based on the above rules, we can get the following curve-transition matrixes, shown as Figure 7. By looking up these matrixes directly, the time complexity of calculating the Hilbert code of sub-grid is O(1). Based on the matrixes, Hilbert code computing algorithm is described as the following pseudo codes. The Hilbert code of a grid is computed recursively from higher level to lower level. Because the time complexity of every step is O(1), the total time complexity of Algorithm 1 is O(n). ```
functionHilbertCode(x,y,k)/ \"\"\" params: x: the longitude value of a point, \(-180\leq x\leq 180\) y: the latitude value of a point, \(-90\leq y\leq 90\) k: the level of Hilbert grids, \(0\leq k\leq 32\)\"\"\" hcode, htype = 0, T1 whilek > 0: m, n = HilbertGrid(k,x,y) mb, nb = binary(m), binary(n) mk, nk = mb & (2 \(\ll k\)), nb & (2 \(\ll k\)) grid_idx = mk^2 + nk  ck = query_code_QM(lltype), grid_idx) hcode = hcode <= 2 1  ck htype = query_type(M|lltype), grid_idx) k = k - 1 return hcode
```  
**Algorithm 1** Hilbert code computing  
Figure 6: Basic shapes of Hilbert curve.