Trace

For an individual user, there is a sequential navigation path of recorded tiles (the sequence of tiles that were requested by this individual. Similarly, we can sequentially investigate all users’ navigation paths for the entire system; this is called the historical access-log information (or simply referred to as trace information).

Access steps

This value indicates the number of steps between two tiles when they are requested sequentially. For example, if “ABCD” are requested sequentially, then the number of access steps between A and B is 1; the number of access steps between A and C is 2; and so on.

Fixed-access mode

A fixed access mode represents tiles that are usually accessed either sequentially or simultaneously. For example, “AB” and “CD” are two fixed-access modes based on typical historical access-log information [24].

Matching radius

A large access step value indicates a small correlation; thus, the matching radius denotes the largest access steps between tiles. When tiles' access steps are larger than the matching radius, their correlations are zero.

Hotspot tiles

Based on Zipf's law, only a small portion of the total tiles will be requested repeatedly [10,11]; these tiles are the hotspot tiles. To avoid invalid prefetching and reduce cache pollution, GUDC prefetches and caches only those hotspot tiles that meet the following restriction [20]: (1) where K is the total number of all tiles (the tile set), N is the total number of hotspot tiles (a subset of the tile set), α is the Zipf distribution parameter and h is the steady-state cache hit ratio. The top N tiles can be selected as the hotspot tiles set by sorting all tiles based on their popularity from the trace information (or simply by computing the total number of accesses for each tile based on trace information).

In the next two sections, we will propose a simple correlation expression model first, and then, discuss a more complex model based on tiles’ fixed access modes.

Simple model

To construct a correlation expression model to represent the typical features mentioned above, a matching degree model is proposed that follows a conditional prefetching probability algorithm.

Denote T = {t₁,t₂,⋯,t_N} as the set of all hotspot tiles that will be accessed by all clients in GIS. Each element in T is labeled with a natural number [1, N], where N is the total number of hotspot tiles. Then, let Q = (q₁,q₂,⋯,q_L) denote all the traces chronologically recorded by system after running for a long period, where q_k ∈ [1,N] denotes the label of the k-th most-requested tile (i.e., q_k = i (k = 1,⋯,L) indicates that the k-th requested tile is t_i (i = 1,⋯,N)) and L is the total number of requests to all hotspot tiles.

If during a certain period t_i is requested and—after x-steps—t_j is also requested, then we denote that there is an x-step matching from t_i to t_j. Then, corresponding matching weights and matching steps can be denoted as w_x and d_x, respectively, where t_i,t_j ∈ T and d_x = x, w_x−1 > w_x (i,j ∈ [1,N], i ≠ j). If we denote n as the matching radius, then x ≤ n.

Moreover, for ∀t_i ∈ T (i ∈ [1,N]), we can obtain G_i sub-vectors Q_k(i) = (q_k0,q_k1,q_k2,⋯,q_kn) (q_kx ∈ [1,N], k ∈ [1,G_i], x ∈ [0,n]), where q_k0 = i. Obviously, each sub-vector Q_k(i) indicates which tiles are requested after t_i and indicates their access steps with t_i. Thus, the matching degrees from t_i to t_j based on a specific sub-vector Q_k(i) can be stated as follows: (2) where (3) and their corresponding matching steps E_k(i,j) and matching times F_k(i,j) can be stated as follows: (4) (5)

Considering the full set of sub-vectors , the total matching degrees M(i,j) from t_i to t_j can be stated as follows: (6) where and V_k(i,j) = (v_k0(i,j),v_k1(i,j),v_k2(i,j),⋯,v_kn(i,j)) is the matching factor vector based on the sub-vector Q_k(i), and W = (w₀,w₁,w₂,⋯,w_n) represents the vector of matching weights. Then, (7) and (8) where D = (d₀,d₁,d₂,⋯,d_n) represents the matching steps vector, and the mathematical expression V(i,j)∙D is a dot product between vector V(i,j) and vector D.

Eq (6) provides the explicit probability of t_i and t_j being requested simultaneously. Eq (7) yields the access distance between t_i and t_j when they are requested during a short period, and Eq (8) represents the total number of times they are requested simultaneously. Therefore, (9) indicates the total prefetch probability for t_j when t_i is requested (in other words, the probability that t_j will be requested next).

A higher matching degree M(i,j) and/or a lower number of matching steps E(i,j) between t_i and t_j denotes a higher probability of t_j being requested either simultaneously or immediately after t_i is requested. In addition, a larger number of matching times F(i,j) can indicate a higher correlation between t_i and t_j. Therefore, Eq (9) can satisfy the three obvious conclusions presented previously concerning the correlations of tiles, and it can be used both to compute the correlations among tiles and to predict the next user request based on global users’ behavior. Thus, for ∀t_i ∈ T, we have (10) from which we can find the element that best predicts the corresponding tiles when t_i is requested.

Complex model

Furthermore, many studies show that the access to tiles tends to follow a specific path (navigation path) [21,25], consequently, there are many fixed data access modes [26] and we can make predictions using only the last requested tile or we can employ knowledge of these fixed access modes to obtain a more rigorous and accurate forecast. A simple example is shown in Table 1, where the trace comes from typical historical access-log information [24].

Download:

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

Table 1. An example of using different conditions to make predictions.

https://doi.org/10.1371/journal.pone.0170195.t001

Similarly, for any fixed access mode that ends with t_i, (11) yields a conditional prefetch probability for t_j when a series of tiles were requested sequentially based on the fixed access mode A_k(i) over a short time period, where indicates that the last requested tile is t_i, a_kl ∈ [1,N] (l ∈ [1,a_k], a_k ≤ n, k ∈ [1,C_i]), a_k is the length of the fixed access mode A_k(i), and C_i is the total number of all fixed access modes that end with t_i.

Thus, for ∀t_i ∈ T, we can obtain a conditional prefetch probability matrix for all tiles based on all possible fixed access modes that end with tile t_i. The matrix can be notated as follows: (12) where represents the set of all fixed access modes that end with t_i. Here, P_s(i,T) denotes a specific row of P(A(i),T) when its fixed access mode A_k(i) has only one element(i).

Tile prefetching strategy

As shown in Table 1, the purpose of tile prefetching is to find the best choice to anticipate the user's next movement. Eq (12) shows how to compute the conditional prefetching probabilities for all tiles. Thus, tile prefetching strategies can be stated as follows:

1. Step 1: Sequentially record the indexes of all tiles requested by all users. After the system has been running for a sufficiently long time, these indexes constitute a historical record denoted as trace Q_all.
2. Step 2: Obtain the set of hotspot tiles set T based on trace Q_all using Eq (1). Then, delete all the labels of unpopular tiles from Q_all. The result is a hotspot tiles trace Q.
3. Step 3: Sequentially record the index of the most recently requested n tiles and denote them as Q_s = (q_s1,q_s2,⋯,q_sn), where is the tile being requested.
4. Step 4: Based on trace Q, obtain the fixed access mode set A(q_sn) and then compute the prefetching probability matrix P(A(q_sn),T) for all tiles based on Eq (12).
5. Step 5: Let denote the fixed access modes matching indicator of tile based on the fixed access mode , where is the number of fixed access modes that end with . Then, s_k(q_sn) () can be shown as follows:

(13)

Eq (13) indicates that if we can find a certain fixed access mode from the current access states Q_s then its corresponding fixed access modes matching indicator can be assigned to 1; otherwise, we assign it to zero. Here is a simple example that can be found from the trace discussed above [24]. If we assume that the current access state Q_s = (ABCD), then the tile currently being accessed is D (the last element in Q_s). Further, assume that all the fixed access modes of D are A(D) = ((D),(AD),(ABD),(ABCD)). Thus, from Eq (13), we obtain S(D) = (1,0,0,1). Then, using Eq (12) and Eq (13), we can calculate the total conditional prefetching probability, which is stated as follows: (14)

Eq (14) shows the total conditional prefetching probabilities based on all the fixed access modes A(q_sn) that are a dot product between vector S(q_sn) and matrix P(A(q_sn),T). Therefore, the largest element from P_f(q_sn,T) will have the highest probability of being requested next by all users, and we can prefetch its corresponding tile (i.e., if the second item is the largest element in P_f(q_sn,T), then prefetch t₂).

1. Step 6: Add Q_s to the end of Q and update Q and P(A(q_sn),T).
2. Step 7: Repeat Steps 3–7 when the system receives a new request.
3. Step 8: The tile prefetching algorithm is complete.

Moreover, if we denote the abovementioned method as a 1-step data prefetching strategy, then the m-steps data prefetching strategy seeks to obtain m tiles that have higher total conditional prefetching probabilities based on Eq (14). Thus, we can use the m-steps data prefetching strategy to prefetch more tiles to reduce the computational load and the number of scheduling times.

Tile replacement strategy

Due to the limited high-speed cache space on servers, another important factor in achieving a high cache-hit rate is to remove the most appropriate data to free cache space on the server using a data replacement strategy. Many classical data replacement algorithms such as FIFO, LRU, and least frequently used (LFU) are widely used in numerous fields [27,28,29] and Google [7], NASA [8] and NGISs [9] have all used the LRU algorithm to achieve good performance in their server systems. The authors of [30] proposed the Lowest Value First Cache Replacement for Geospatial Data (GDLVF), a type of lowest value-first cache replacement algorithm for geospatial data caching that comprehensively considers the influence of many factors, including not only access time and access frequency but also the size of the data size and its location. However, research shows that we can achieve a high hit rate even with a simple LRU technique if we simply group the cache queues [31].

The above analysis is still lacking in that we should consider not only the data itself but also the relationships within the data. Therefore, this article provides a method that comprehensively considers both the global users’ behaviors and all tiles’ relationships based on a unified algorithm model for scheduling tile replacement.

Similar to the tile prefetching strategy, after obtaining trace Q, we can schedule tile replacement using the following steps:

1. Step 1: Sequentially record the indexes of the last n cached tiles and denotes the set as Q_c = (q_c1,q_c2,⋯,q_cn), where is the tile being prefetched and stored into the high-speed cache.
2. Step 2: Obviously, the last-cached data must be the last-requested data. Thus, we have = and A(q_cn) = A(q_sn). Set P_c(A(q_cn),T) = P(A(q_sn),T)(q_cn ∈ [1,N]) and delete the columns from P_c(A(q_cn),T) in which the corresponding tiles are not cached (i.e., if tile t_i is not stored in the high-speed cache buffer, then delete the i-th column). Thus, the corresponding tiles of P_c(A(q_cn),T) are the only tiles stored in the high-speed cache buffer.
3. Step 3: Similar to Step 5 in the previous section, calculate S(q_cn) based on tile and Q_c. Then, using Eqs (12) and (13), we can obtain a total conditional caching replacement probability, which can be stated as follows:

(15)

Eq (15) yields the total conditional caching replacement probabilities based on all fixed access modes; therefore, by finding the smallest one (which has the lowest probability of being requested next by all users) and deleting its corresponding tiles from the high-speed cache buffer, we can save cache space (i.e., if the second item is the smallest element in P_c(q_cn,T), delete t₂ from the cache buffer).

1. Step 4: Repeat Steps 1–4 when the system prefetches and caches a new tile.
2. Step 5: The tile caching replacement algorithm is complete.

Using the same logic as the tile prefetching strategy, we can also delete m tiles from high-speed cache buffer based on an m-step cache replacement strategy.

Algorithm analysis

A theoretical analysis shows that GUDC must compute the total conditional prefetching probability matrix for all tiles based on the full trace information Q. Therefore, GUDC has an initial time complexity of O(N³L). Because there are large numbers of datasets (large N) and a plethora of trace information, Q (large L), it is impossible to calculate the conditional prefetching probability matrix in real time; consequently, we must dynamically count and compute matching degrees, matching weights and matching steps for each segment of all the trace information while the system is running. Subsequently, the total conditional prefetching probability matrix can easily be computed by adding all these items based on Eq 6, Eq 7 and Eq 8 after sufficient trace information has been obtained.

Simulation design

To illustrate the performance of the proposed algorithm in this paper, we selected our method and some typical methods for comparison:

1. the global user-driven model for tile prefetching proposed in this article, GUDC;
2. The method described in [14], which adopts a fair allocation scheme called the proportional distribution election scheme for the United States Congress and a replication strategy for distributed high-speed caching based on spatial and temporal locality (DCST);
3. The method described in [18], which computes the transition probabilities between tiles and prefetches the most likely neighbors using a type of previous k movements algorithm (PKM);
4. The method described in [19], which uses a basic Markov Chain model to cache optimum tiles, called the Basic Markov method (BM);
5. The method described in [20], which calculates the popularity of all tiles and prefetches those tiles with higher probabilities based on Zipf 's law, called the Zipf Law (ZL) method;
6. The method described in [21] that uses a Zipf-like law based on a Markov Chain model to cache optimum tiles, called the Zipf-like Markov method (ZM);

Among these methods, GUDC and DCST can be used to predict requests from multiple users, while all the others are designed to predict only a single user’s behavior. Therefore, comparisons will be made only between GUDC and DCST for multi-user behaviors, and among GUDC, DCST, BM, ZL and ZM based on single user’s behavior.

Based on the analyses discussed above, tile prefetching strategies can be employed on both the server side and client side. Therefore, GUDC will also be implemented as a client-side prefetch method and compared with other client-side algorithms such as (RAP) [17].

Because the Zipf-like distribution parameter α can vary significantly, from 0.60 to 1.03 [33], these experiments adopted values of 0.600, 0.750, 0.815, 0.971 and 1.03 for α in simulating requests for tiles using GlobeSIGht [11] and to demonstrate the adaptability of the proposed method to the behavior of different users.

For the proposed method, another factor that affects performance is the prefetching steps mentioned at the ends of the previous two sections. Because the best choice for the matching radius is approximately 2.5 to 5, these experiments adopted a prefetching step value of 3, which the means that GUDC will prefetch 3 more tiles whenever a certain tile is requested. We also considered some other choices for the prefetch step value; the corresponding tests are shown below.

Furthermore, to validate the adaptability of the proposed method to different parameters, we conducted some comparative experiments using different matching radii (which vary from 1 to 14), different prefetching steps (which vary from 1 to 10), and different cache replacement strategies (which include the GUDC method, the FIFO algorithm and the LRU algorithm).

Data sources

The experiments are driven by trace data simulated by accessing SRTM90 (the 90-meter-resolution global terrain data files from the Shuttle Radar Topography Mission) data. All tile requests obey a Zipf-like distribution and are accessed through GlobeSIGht [11], which is an earth observation system similar to Google Earth or NASA World Wind. The requests to servers also obey a Poisson distribution [32].

This study selects some tiles of a certain area of China as the objects to be accessed. The datasets include between 55,242 and 663,552 tiles; however, most requests focus on subsets of the hotspot tiles due to Zipf's law.

The traces include two parts: one is used for training (to compute and find the user-driven model for tile prefetching) and the other is used to test the model validity. Each part of the complete traces includes approximately 2–20 million requests for all the hotspot tiles.

The dataset statistics and the number of requests contained in the traces are summarized in Table 2.

Download:

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

Table 2. The datasets parameters used in the experiments.

https://doi.org/10.1371/journal.pone.0170195.t002

The workflow of experiments

The steps to validate the global user-driven cache algorithm were as follows:

1. Using the first portion of the trace information, a correlation matrix and tile popularities were computed;
2. Tiles with higher popularity were prefetched and cached in advance, based on the available cache space;
3. The second part of the trace information was used as a simulation of users’ requests for all hotspot tiles. During the simulation, certain tiles are prefetched and cached; simultaneously, and other tiles in the cache are replaced to save cache space using the various scheduling algorithms mentioned above;
4. For GUDC, the correlation matrix is updated based on the second part of the trace to follow changes in users’ behaviors;
5. For all simulated accesses, the total number of requests hit in the cache was counted, and finally, the cache-hit ratio was calculated.
6. Moreover, the total number of disk accesses was also counted. Then, disk access ratios were computed.

Experimental results and discussion

There are three kinds of prefetching modes: multi-user mode, single-user mode and client-side mode.

Multi-user mode is a global mode that predicts a user's next movement based on the behavior of all users rather than the behavior of a single user.

Fig 1 gives the performances for GUDC, DCST and the No-Prefetching strategy (NP), based on the multi-user mode and measured by the CHR, where the distribution parameter α = 0.600. All these algorithms are driven by the global user behavior. GUDC and DCST created an initial cache based on their own algorithm rules. Among these algorithms, GUDC uses the tile replacement strategy proposed in this article to delete tiles from the high-speed cache buffer to save cache space, while DCST, based on its algorithm strategy, uses the LRU strategy to delete tiles from the high-speed cache buffer. NP simply caches the tile being accessed; it never prefetches tiles in advance. NP uses the LRU and FIFO strategies to delete tiles from the high-speed cache buffer.

Download:

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

Fig 1. Comparative CHRs obtained from different prefetching algorithms based on multi-user mode.

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

As shown in Fig 1, the performance of all algorithms improves as the number of cached tiles increases because a greater number of cached tiles increases the possibilities for cache hits. However, due to DCST's cache space saving method, the hit-rate changes only negligibly when the cached tile ratio is above 36% (when α = 0.600). In this case, GUDC's performance exceeds that of DCST by approximately 15% when the cached tile ratio is less than 36%, and expands to 27.5% when the cached tile ratio is increased. In addition, GUDC provides obvious performance advantages over the traditional algorithms of FIFO and LRU ranging from 38.7% ~ 51.9% under all experimental conditions.

Single-user mode is very different from multi-user mode because it considers only the behavior of one particular user to predict the next movement based on the user’s current observation location.

Fig 2 shows the performances of GUDC, DCST, ZM, ZL and BM in single-user mode as measured by the CHR, where the distribution parameter is α = 0.815. GUDC and DCST are driven by global user behavior, and the others are driven by a single user’s behavior. All the algorithms in this experiment except GUDC used the LRU cache replacement strategy.

Download:

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

Fig 2. Comparative CHRs obtained from different prefetching algorithms based on single-user mode.

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

As shown in Fig 2, just as in the first experiment (Fig 1), the performance of all algorithms improves as the number of cached tiles increases. In addition, GUDC achieves a better performance than ZM (by approximately 11.4%), ZL (by approximately 30.7%), and BM (by approximately 110.5%). In this case, DCST achieves a higher CHR than ZM, ZL and BM when the cached tile ratio is less than 42% (when α = 0.815), but—for the same reason—its performance advantages diminish as the cached tile ratio increases.

Finally, to investigate GUDC’s performance when implemented as a client-side prefetching and caching scheme, a comparative experiment was performed based on client-side cache mode. The performance comparison of different algorithms is shown in Table 3.

Download:

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

Table 3. A performance comparison of various algorithms based on the client-side prefetching mode.

https://doi.org/10.1371/journal.pone.0170195.t003

Due to the limited cache space, algorithms based on client-side cache mode can cache only a limited number of tiles. RAP removes 75% of the oldest tiles from the cache to save cache space; therefore, it has a minimum cache space occupancy ratio. After normalizing cache space to the same benchmark, the performances based on this normalized cache space is computed and shown in the 4th column, which indicates that GUDC achieves the best performance, improving on RAP (which is designed specifically for client-side cache mode) by approximately 10.6%.

To demonstrate the changes in GUDC's performance based on different Zipf-like distributions, a comparison is shown in Fig 3 in which the distribution parameter α changed substantially, from 0.600 to 1.030 (the maximum interval is [0.600–1.03]).

Download:

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

Fig 3. Comparative CHRs obtained from GUDC based on different global user behaviors.

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

As shown in Fig 3, the performance of GUDC improves as the distribution parameter α increases because a larger distribution parameter represents a more concentrated access distribution and, therefore, requires fewer hotspot tiles to be cached. As the distribution parameter increases, the performance improves by an average of approximately 18.5% each time the distribution parameter α increases by approximately 10%.

Furthermore, if we denote (CHR_i-CHR₁)/CHR₁ as the performance improvement of GUDC with different data sizes, Fig 4 illustrates the experimental results using different cached tile ratios (Cr). In Fig 4, CHR₁ represents the first performance value based on the first data size and CHR_i indicates the performance value resulting from other data sizes.

Download:

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

Fig 4. Comparative CHRs obtained from GUDC based on different data sizes.

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

From Fig 4, it is apparent that the performance improves stably and that a smaller cached tile ratio increase the rate of performance improvement. Through testing and analysis, we found that GUDC can cache more hotspot tiles under the same cached tile ratio as the data size increases. Then, GUDC obtains a higher cache-hit probability, which stably improves the performance as the data size increases. At the same time, comprehensively considering the experimental results in Fig 1 and Fig 3, which show that a smaller cached tile ratio results in lower CHRs as well as that smaller data size result in lower CHRs, it is more difficult to improve GUDC’s performance further because it is very high already.

In contrast, the performance can be improved by increasing the data size, but the same cached tile ratio will lead to a larger cache space demand as well as increased computational complexity because a more massive hotspot dataset must be computed. Thus, in future work, we plan to investigate a way of grouping the tiles to reduce the computational cost while still maintaining GUDC's performance.

Additionally, it is obvious that increasing the number of prefetching steps means more tiles will be cached each time; consequently, we can improve the probabilities of preparing data for the next move in advance. Fig 5 shows the contrast in GUDC's performances with different numbers of prefetching steps (from approximately 1 to 10 tiles, corresponding to 1 to 10 prefetching steps).

Download:

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

Fig 5. Comparative CHRs obtained from GUDC using different prefetching steps.

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

Fig 5 shows that the performance can be improved by increasing the number of prefetching steps when the cache space is relatively small, but results in only negligible changes when the number of steps expands beyond 3. The experiment results show that GUDC can accurately represent short-term burst demands among the tiles; therefore, the algorithm achieves better performance using a small number of prefetching steps that reduces the computational complexity. Even a single step is sufficient to obtain a high performance when a large high-speed cache space is available.

Tile prefetching and cache replacement are two factors that can help optimize GIS performance. Most algorithms focus only on the prefetching model while using traditional methods to calculate cache replacement. To evaluate the performance of GUDC's cache replacement algorithm, we performed a comparative experiment using the GUDC cache replacement algorithm, the FIFO replacement strategy, and the LRU replacement strategy, as shown in Fig 6.

Download:

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

Fig 6. Comparative CHRs obtained from GUDC using different cache replacement strategies.

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

Similar to the experiment in Fig 5, the performance can be improved by using GUDC cache replacement strategy when the cache space is relatively small. For the same reasons, being able to accurately follow short-term bursts to avoid incorrectly deleting tiles from the cache that will be requested next, has a particularly heavy impact on performance when the cache space is relatively small. From the experimental results shown in Fig 6, we can use the GUDC cache replacement algorithm when the cache space is small or the LRU cache replacement algorithm when the cache space is large to simultaneously reduce computational complexity and obtain high performance.

Because the matching radius, n, is another important parameter that can be used to determine the numbers of related tiles, we performed a comparative experiment using different matching radii to compute the matching degrees. This approach results in different total conditional prefetching probability matrix for making predictions and prefetching. A comparison of the results is shown in Table 4, where the distribution parameter α = 0.600 and the cached tile ratio was 18%.

Download:

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

Table 4. Comparative CHRs and disk access ratio based on different matching radius.

https://doi.org/10.1371/journal.pone.0170195.t004

The 2^nd column in Table 4 lists the disk access ratio performance, which is the ratio of the total number of disk accesses (which occurs when the cache is missed and during active prefetching) to the total number of requests from users, and presents the resource cost of the proposed algorithm. The 3rd column shows the CHR performances. Obviously, a lower disk access ratio indicates fewer disk accesses as well as reduced resource consumption. Table 4 sows that the algorithm achieves its best performance based on the designed matching radius (where n = 5). Although only small changes occur in the CHRs as the matching radius varies from 1 to 14 (the typical navigation depth is approximately 5 to 10 [17]), the resource cost of the algorithm based on the designed matching radius is the lowest: it reduces the disk access ratio by approximately 4.38%.

Furthermore, to compare the resource costs of different algorithms, a comparative experiment was also conducted using GUDC, DCST and two traditional algorithms. The experimental results are shown in Fig 7.

Download:

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

Fig 7. Comparative disk access performance obtained from different algorithms.

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

As Fig 7 shows, GUDC and DCST achieve better disk access ratios than do the two traditional algorithms. Due to limited cache space and maintaining a higher cache hit ratio, GUDC must continually update the cached tiles by prefetching tiles from disk, while DCST simply stores tile being requested into the cache and never actively prefetches data from the disk. Considering the experimental results shown in Fig 1 and Fig 7, the performance gap in disk access ratio can be reduced by increasing the size of the high-speed cache space, which also narrows the CHR performance gap. Moreover, GUDC can continue to reduce disk access ratio by increasing high-speed cache space until, at some point it can be ignored. In contrast, DCST’s disk access ratio cannot be reduced further by increasing the high-speed cache size.