3.1 Description of APSA

We first provide some basic definitions of objects used by the algorithm.

First, let F = {f₁, f₂,…, f_N} be the set of natural files, which includes all of the original small geospatial image data files (for brevity, we henceforth refer to small geospatial image data files simply as small files). Each element in F is labeled with a natural number [1, N], and N is the total number of small files. The natural numbers [1, N] can then be defined as a natural file vector I_o = (1,2,⋯, N) based on the natural sequence of these files.

Let C = {c₁, c₂,…, c_m} denote the set of storage nodes, where m is the total number of all storage nodes. For simplicity, each of the N small files is stored in m storage nodes on average (an uneven grouping can be transformed into an even grouping by copying select small files that have higher request rates; this process is demonstrated in section 4, and a related experiment is detailed in section 5.4).

Finally, let be the set of grouped storage files. Each group of small files will be stored in one of the storage nodes, and each small file in F will belong to one and only one group. In other words, the element in is a group of n small files that will be stored in the ith storage node, c_i. Here, m × n = N, and n is called the storage length.

Furthermore, for (i ∈ [1, m]), if we assume that the small files are labeled by t_i1, t_i2,⋯, t_in in F and are denoted by T_i = (t_i1, t_i2,⋯, t_in) (t_ij ∈ [1, N], i ∈ [1, m], j ∈ [1, n]), then T = (T₁, T₂, ⋯, T_m)^T = (t_ij)_m×n defines the map from set F to set , and each T_i is a restriction of T on . Therefore, the map denotes a storage distribution rule that defines how the small files are assigned to storage nodes on average. If the storage distribution vector is denoted by I=(t₁₁,t₁₂,⋯,t_1n,t₂₁,t₂₂,⋯,t_2n,⋯,t_m1,t_m2,⋯,t_mn), then the APSA key can be converted to construct an N × N permutation matrix, B, that satisfies the condition I = I_oB. We can then achieve our goal of distributing all small files across all storage nodes on average.

3.2 Access correlation matrix

To construct B (or to find an optimal T), we must analyze the historical access log information [20], which reflects the small files’ access patterns and can be used to compute the relationships among the small files.

Let denote the chronological access sequence of small files that is obtained from the historical access log information recorded by the server of the Digital Earth system. The vector A = (a₁, a₂,⋯, a_M) can then be defined as the geospatial data file access vector. Here, M is the total number of accesses to all small files in F, and the natural number a_i ∈ [1, N] (i = 1,2,⋯, M) denotes the label of the ith requested file from F (i.e., a_i = k (i = 1,…, M), which indicates that the ith requested file is f_k (k ∈ [1, N])).

Because the storage length is n, we divide A into several n-element sub-vectors; then, A can be written as A = (S₁, S₂, ⋯, S_l), where S_i = (a_i1, a_i2, ⋯, a_in) (a_ij ∈ [1, N], 1 ≤ i ≤ l, 1 ≤ j ≤ n) is an n-element sub-vector in A and l is the total number of n-element sub-vectors. The set of all sub-vectors of vector length n is denoted by S = {S_k: k ∈ [1, l]}. For ∀S_k ∈ S, let denote the set of all n elements of sub-vector S_k. We can then define the access correlation function for all small files as shown in Eq (2); this function represents the relationship between any pair of small files: (2)

Here, denotes the access correlation between f_i and f_j during a short period of access time. Therefore, indicates whether the geospatial data files f_i and f_j are both likely to be requested within a short period of time. If = 1, then we consider that f_i and f_j have one storage conflict, and we define the following: (3) R_S(i, j) represents the total number of storage conflicts between f_i and f_j. A larger value of R_S(i, j) indicates a higher level of storage conflict or a higher total concurrent access probability (TCAP) between the small files f_i and f_j, corresponding to a higher probability that these files will be assigned to different storage nodes to achieve a higher total parallel access probability (TPAP) in the case that they are requested simultaneously.

For all small files in F, we can obtain an N × N matrix based on S as follows: (4)

Here, R_S is called the access correlation matrix and represents the concurrent access correlations among the small files. This matrix has the following properties (as proven in the appendices):

1. R_S is a symmetric matrix, i.e., R_S^T = R_S;
2. ;
3. ; and
4. .

Here, P(f_i) is the concurrent access probability of f_i in S, and P_S(f_j|f_i) is the conditional probability that f_j will belong to the same S to which f_i belongs.

3.3 Mathematical model of APSA

Let T_i = (t_i1, t_i2, ⋯, t_in) be an arbitrary row vector in T. Then, according to T_i, we can store n geospatial data files in the ith storage node c_i. If any file in is requested, then is requested (in other words, the storage node c_i is busy and is unable to serve any other clients), and denotes the concurrent access probability of the set of small files . On the basis of the 3rd property of R_S stated in section 3.2, we can define the following: (5)

Similarly, if denotes the conditional probability of the set of small files (representing the probability that if any file in is requested, the other files in will be requested within a short period of time), then on the basis of the 4th property of R_S stated in section 3.2, we can define the following: (6)

Eqs (5) and (6) define the relationship among R_S, the access patterns and the concurrent access probabilities of the small files. For simplicity, let and ; then, Eqs (5) and (6) can be rewritten as follows: (7) (8)

Furthermore, according to the definition of the map , the TCAP can be defined as in Eq (9): (9)

By combining (7), (8) and (9), we obtain the following: (10) where (11)

Eq (10) describes the explicit relationship between the objective function and both R_S and T. As mentioned above, the goal of APSA is to achieve parallel access to geospatial data files, which requires a TPAP that is as high as possible. Therefore, the goal of APSA can be restated as the attempt to obtain the lowest possible TCAP, and we can conclude that is proportional to H(R_S, T). Therefore, the mathematical model of APSA can be defined as follows: (12)

If we obtain an optimal T according to Eq (12), then we also obtain an optimal B. However, this is a typical NP-hard problem, and the traversal search method is impractical because of the extremely large amount of calculation time required. Therefore, the goal of the algorithm must be modified to obtain a reasonable solution. This modification is discussed in the next section.

4.1 Preprocessing of F

Large numbers of small files are stored in the Digital Earth system, and therefore, we must process a large collection of natural files. For example, for the 90-meter-resolution global terrain data files from the Shuttle Radar Topography Mission (SRTM90), the length of I_o will be 3,538,890 and the size of R_S will be 3538890×3538890. However, as indicated by the geospatial DAP, only approximately 20% of these files will be requested [21–23]. Therefore, we only need to process a subset of the data, which allows us to reduce the size of R_S.

To satisfy the requirements for storing all N small files in m storage nodes on average, we can copy certain geospatial data files that have higher request rates and assign new labels to the copies (to expand the scale of F and I_o).

4.2 Preprocessing and reordering of R_S

The historical access log information is produced by the Digital Earth system after a long period of operation, and from this information, we can obtain A. Then, we can generate R_S using the algorithm described in section 3.2.

To reduce the search scale, we must concentrate non-related elements together to allow the storage distribution rule T to be rapidly sought and obtained. Thus, we can reorder R_S using the RCM ordering algorithm, which was developed based on the CM ordering algorithm [25–26]. We can then obtain a new P, in which most of the nonzero elements are concentrated along the diagonal.

The objective of APSA is to generate grouped geospatial data files and to ensure that these groups have the smallest possible storage conflict, meaning that the value of R_S is zero or near zero. To employ the RCM ordering algorithm to concentrate the non-related elements along the diagonal, we must first preprocess R_S in two steps: 1) denote the largest value of R_S by R_max and search for and obtain R_max from R_S, and 2) ∀R_S(i, j), set R_S(i, j) = R_max – R_S(i, j) (i < j ≤ N).

Afterward, we can use the RCM algorithm to reorder R_S, export the resulting permutation P in reverse order and then export the corresponding matrix P_S (the standard RCM algorithm is used in this paper; therefore, a description of this process is omitted).

4.3 Determination of the optimal T using a locally approaching search algorithm

Several steps are required to obtain the optimal T:

1. Initialize T = (0)_m×n and set k = 1.
2. Let i be the label of the first row in P_S; then, a non-zero length can be obtained: non_zero_len = max{|i − j|, A_ij ≠ 0}.
3. If non_zero_len ≤ n, then for every j ∈ [1, n], let T[k][j] = P(j). Then, delete the n top rows of P_S and delete the first n elements of P. Go to 7).
4. If non_zero_len > n, then take the upper triangular matrix UTM_m = {A_ij, 1 ≤ i ≤ j ≤ non_zero_len}. Let X = (x₁, x₂,⋯⋯, x_n) denote an n-dimensional temporary vector and initialize x₁ = 1, i₁ = 1, and j = 2. Set the basis vector of the local search to B = UTM_m(i₁).
5. While j ≤ n, search for the largest element B(i_j) in B. Then, the label of the jth file is i_j; set x_j = i_j. Update the basis vector of the local search as follows: B = B + UTM_m(i_j). Set B(i_j) = -K_S and j = j + 1.
6. For 1 ≤ j ≤ n, set T[k][j] = P(x_j). Then, delete the n rows of P_S that are defined in the temporary vector X and delete the corresponding n elements of P.
7. Set k = k + 1. If k ≤ m, then return to 2); otherwise, stop.

For the optimal T, n small files are included in each group, i.e., the ith group includes small files labeled as T[i][1], T[i][2], $#x2026;$#x2026;, T[i][n], and the relationship among the files in a given group is as weak as possible. Therefore, the ith group of files can be stored in the ith storage node c_i.

5.1 Contrasting experiments on different algorithms

From the 30-m-resolution global terrain data files from the Shuttle Radar Topography Mission (SRTM30), we selected 10,000 geospatial image data files from a given spatial region for use as the experimental dataset. All available sequences of access log information for the considered SRTM30 datasets are summarized in Table 2 (category 1 and category 2). We determined the optimal T using the first access log information file in category 1, and we then assessed the performance of the various algorithms using the second log file in category 1. Fig 1 presents the results of the comparison at different scales of m.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. Comparison of TPAP results at various scales of m (N = 10,000).

https://doi.org/10.1371/journal.pone.0133029.g001

As shown in Fig 1, APSA and LSA exhibit comparable performance in a small-scale environment, especially when m is less than 8. In this case, only a small number of storage nodes are available, and most of the small files must be stored in the same storage node. Moreover, the majority of clients will request small files according to their navigation paths [22–24], and therefore, LSA, which stores small files in different storage nodes depending on their spatial locations, can satisfy the requirements of parallel I/O.

For a larger number of storage nodes, however, APSA performs better than RSA or LSA, especially when m is larger than 22. The performance of APSA is higher than that of LSA by approximately 10% and higher than that of RSA by approximately 15%, especially for a large number of servers.

Furthermore, we tested the performance of APSA using all log files in category 2, which represented various scales of small files. Fig 2 displays the results of the comparison for various values of N.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 2. Comparison of TPAP results for various values of N (m = 10).

https://doi.org/10.1371/journal.pone.0133029.g002

As shown in Fig 2, as the scale of the geospatial data increases, the performance of LSA exhibits almost no change, and the performance of RSA becomes considerably more unstable and fragmented and even decreases to some extent. By contrast, the performance of APSA improves, exhibiting a sustained increase. The experimental results show that the proposed algorithm offers greater advantages in a large-scale environment (i.e., for a large number of storage nodes).

5.2 Experiments using different types of access log information

It is important to determine whether an algorithm can always provide high performance. To assess the adaptability of the algorithm, we selected four typical access log information files representing the access behavior of end users (clients) at different times. As in the first experiment, we used the first log file from category 1 to determine the optimal T and then used the 2nd through 5th log files of category 1 to test the performance of APSA. The experimental results are shown in Fig 3A–3D).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Comparison of TPAP results for different access log files (N = 10,000) (each plot, A-D, represents a different access log file).

https://doi.org/10.1371/journal.pone.0133029.g003

As shown in Fig 3, comparable performances were obtained when different access log files were used to obtain a feasible solution. In addition, the rate of change in TPAP did not exceed 6%. Thus, this experiment demonstrated that APSA exhibits stable parallel access performance under different conditions.

5.3 Experiments using different geospatial image datasets

To assess the adaptability of the algorithm to different geospatial image datasets, we selected three typical geospatial datasets: SRTM30, SRTM90 and Landsat7 ETM+[29]. In this experiment, the first two log files from categories 1, 3 and 4 were used.

Let TPAP_{SRTM 30} be the performance indicator for SRTM30, let TPAP_{SRTM 90} be the performance indicator for SRTM90, and let TPAP_Landsat7 be the performance indicator for Landsat7. Then, the TPAP change rate (CCAR) can be calculated using Eq (14). The experimental results are shown in Fig 4.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 4. The adaptability of APSA to different datasets (N = 10,000).

https://doi.org/10.1371/journal.pone.0133029.g004

(14)

As shown in Fig 4, CCAR exhibits essentially no change, and the highest rate of change does not exceed 0.4% and thus is generally negligible. Therefore, the experiment shows that APSA demonstrates broad adaptability to different geospatial datasets.

5.4 Experiments based on redundant data storage

To simplify data processing and enhance the efficiency of the algorithm, we assume (as noted in the Appendix (Property 2)) that any given small file will not be repeatedly requested within a short period of time. Nevertheless, in actuality, certain small files do exist that are repeatedly requested within short periods of time.

However, most storage solutions adopt a copy storage strategy for data security; examples of such systems include RAID, which copies and stores each datum to backup disks, and RADOS (Reliable, Autonomic Distributed Object Store), which manages a number of copies on demand [30].

Inspired by this approach, we can copy select geospatial data files that have higher request rates, and then we can store them in different storage nodes with new labels. Let CR be the ratio of the number of copies to the total number of geospatial data files; next, a larger CR obviously implies the generation of more copies. Based on the results of the first experiment, Fig 5 displays a comparison between the original APSA and APSA_b, for which CR is 6.3% (the geospatial data files with the highest access rates are each copied only once). Furthermore, comparisons between the original APSA and variants of APSA_b with different CRs are shown in Fig 6.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 5. The performance improvement achieved using the copy storage strategy (N = 10,000, CR = 6.3%).

https://doi.org/10.1371/journal.pone.0133029.g005

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 6. The performance improvement achieved using the copy storage strategy with various CRs (N = 10,000).

https://doi.org/10.1371/journal.pone.0133029.g006

As shown in Fig 5, the performance of APSA_b is essentially identical to that of APSA for small numbers of storage nodes, especially when m is less than 8. In this case, only a small number of clients can access the system simultaneously (for simplicity, we assume that one storage node can provide service to only one client at a time; in fact, all clients share the resources of the storage node, including CPUs and bandwidth, when they simultaneously request service from the same storage node, but the server may require the same amount of time to serve all end users simultaneously as it does to serve each client sequentially). Therefore, there is only a very small probability that more than one client will attempt to access the same geospatial data file simultaneously, and therefore, the copy storage strategy will not function effectively. However, as the scale of the system increases, the performance improves considerably, especially for an m greater than 22; indeed, the performance can be improved by more than 20%.

Obviously, larger CRs mean more copies, and more copies result in a higher probability that different clients can simultaneously access the same geospatial data files in parallel. Fig 6 shows the corresponding improvement in performance as CR increases. However, achieving continuous improvement in the system performance is difficult once CR reaches a certain size, because some of the small files will be simultaneously accessed at certain times and accessed in a staggered manner at others. This situation cannot be fully resolved using a copy storage strategy alone, and it can only be partially resolved through algorithm optimization to obtain a better solution than that identified by the method introduced in section 4. Such algorithm optimization will be a focus of our future studies.

5.5 Adaptability experiments based on another type of dataset

In this section, we consider another typical type of log file, namely, INS (Instructional Workload) files, to test the adaptability and flexibility of our solution. The INS files used in this experiment were obtained from separate distributed file system application environments at the University of California at Berkeley. Roselli [28] traced two groups of Hewlett-Packard series 700 workstations running HP-UX 9.05. INS data were collected from twenty machines in these groups, which were located in laboratories for undergraduate classes.

As in the experiments presented in section 5.1, we selected 20,000 files for use as the experimental datasets and employed different access log information files to obtain the optimal T and to simulate file access. Thus, we were able to compute TPAP at various storage node scales. All log files for the INS dataset are summarized in Table 2 (category 5). Fig 7 presents the results of a comparison between APSA and RSA on these files (LSA was not used because there was no location relationship among the INS files).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 7. Adaptability experiment based on the INS dataset (N = 20,000).

https://doi.org/10.1371/journal.pone.0133029.g007

As shown in Fig 7, APSA demonstrates higher performance than does RSA (by approximately 18%) when applied to this type of general dataset. However, INS datasets include not only small files but also several large files. Therefore, when end users (clients) access these large files, they will occupy storage node resources for a longer time, and therefore, the performance of APSA will decline sharply (as shown in Fig 8). Nevertheless, the performance of APSA is still higher than that of RSA, by approximately 10%. Furthermore, if we ignore accesses to large files, where LR is the ratio between the minimum length of the ignored sequences and the total sequence length, then the results are as shown in Fig 9 for various LRs. From this figure, it is evident that the performance of APSA can be effectively improved by increasing LR. Recall that, as mentioned in section 1, declustering technologies can be used to satisfy the requirements of parallel I/O in distributed environments; therefore, hybrid storage strategies are required to satisfy the requirements for both small and large files. The development of such a hybrid strategy will be a focus of our future investigations.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 8. Experimental results for another access log file (N = 20,000).

https://doi.org/10.1371/journal.pone.0133029.g008

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 9. The performance improvement at various LRs (N = 20,000).

https://doi.org/10.1371/journal.pone.0133029.g009

Property 1

From Eq (3), it is clear that . Then, we can obtain the following: (A-1)

Therefore, R_S(i, j) = R_S(j, i); that is, R_S^T = R_S, indicating that R_S is a symmetric matrix.

Property 2

Several studies have shown that a chronological access sequence of small files, R, follows a Markov process; such processes are widely used in predictive models [21, 34–35]. In accordance with this model, A = (a₁, a₂,⋯, a_M) can be treated as a Markov chain with a state space I₀ = [1, N], where the number of states is N. Moreover, based on the G-DAPs, we can assume that the service system has been running for a sufficiently long time before we obtain its access log information R that the distribution of the small files in R is stationary. Therefore, A can be regarded as a stationary Markov chain.

Let Π = {π_i: i ∈ I₀} denote the stationary distribution of the pattern of access to F = {f₁, f₂,…, f_N}, let P = (p_ij)_N×N denote the transition matrix, and let p_ij = P(a_k+1 = j|a_k = i) (i, j ∈ I₀, k ∈ [1, M]) be the (i,j)th element of P. We then have Π = ΠP. Thus, ∀j ∈ I₀, we have , and π_i exhibits no relationship with its location. Therefore, for any set of all sub-vectors S_k, ∀i ∈ I₀, the probability that the ith state appears in is as follows: (A-2)

Because of the large number of small files stored in the system, N >> 1, and thus, π_i << 1. Therefore, we find that (1 − π_i)ⁿ ≈ 1 – nπ_i, and thus, Eq (A-2) can be rewritten as follows: (A-3)

Let denote the probability that the ith state appears in only once; then, can be defined as in Eq (A–4): (A-4)

If denotes the probability that the ith state occurs in more than once, then we obtain the following: (A-5)

By combining (A-2), (A-3) and (A-4), we find that (A-6)

Based on the above analysis, π_i << 1, and thus, is negligible. Therefore, the one broad conclusion that can be drawn from this result is that all elements of are different; this conclusion is consistent with actual observations of G-DAPs, which indicate that a given small file will not be requested repeatedly within a short period of time. We can then write the following: (A-7)

Therefore, (A-8)

Eq (A–8) shows that the sum of all elements in R_S is a constant that is equal to (n-1)M. Therefore, if we let K_S = (n − 1)M, then we can write the following: (A-9)

Property 3

According to the analysis presented for Property 2 and Eq (A–3), ∀i ∈ [1, N] and k ∈ [1, l], we can write the following: (A-10)

Let and let ; then, the frequency of in S is as follows: (A-11)

Note that and . Then, we can write the following: (A-12)

Therefore, (A-13)

According to the assumption described with regard to Property 2, namely, that the geospatial information service system has been running for a sufficiently long time, we know that l is also sufficiently large and that . Therefore, we find that (A-14)

Thus, (A-15)

Eq (A–15) shows that the access probability of one small file is proportional to the sum of the elements in the corresponding row (column) of R_S.

Property 4

According to Eq (A–10), we can also write the following: (A-16)

As in the proof of Property 3, because of the large value of l, we have . Using the same analysis presented for Eq (A–11), we can write the following: (A-17)

In combination with Eqs (A–14) and (A–17), Eq (A–16) can be rewritten as follows: (A-18)