DAPR-tree: a distributed spatial data indexing scheme with data access patterns to support Digital Earth initiatives

Figures & data

Figure 1. More scientific exploration is needed on how data access patterns impact and improve the existing data indexing scheme.

Figure 2. Data balance, topology balance and access balance strategies for data indexing in a distributed computing environment (numbers in data structure represent the access possibility of data node or index node).

Figure 3. Distributed access pattern R-tree (DAPR-tree) introduces the data access possibility to traditional distributed indexing structure.

Table

Algorithm 1. GreedyPartition

Input: number of partitions (n); sampled data list d (d1, d2, d3 … dr), r is the sample size;

Output: Partition results

{ // Determine the strips number in each dimension

s = $[\sqrt{\mathit{r}/\mathit{n}}]$ // Get the entire multi-dimensional region with given feature list space = spatialUniverse(d); // Determine the strips in x dimension X_Strips = greedyStrip (s, space, d, x,); for i from 1 to s do   // Determine the strips in y dimension of on the given column   Partitions = Algorithm 2: greedyStrip (s, X_Strips [i], d, y) end for return Partitions

}

Algorithm 2. GreedyStrip

Input: strip number (s); strip region (strip); sampled data list d (d1, d2, d3 … dr); strip dimension

Output: Partitions in the given strip dimension

{ //sort the data list in strip dimension

f = sort (d) //traverse data and strips for i from 1 to r do  for j from 1 to s do   if strip (j) is not full then    merge feature (i) with strip (j)    calculate merging penalty = sum $\left({\displaystyle \frac{\sqrt{{\displaystyle \frac{1}{N}{\sum }_{i=1}^N{(x_i-\mu )}^2}}}{\mu }}\right)$ (detailed in section 3.1)   end if  end for

assign i to the strip with a minimum penalty  remove i from f end for

}

Figure 4. The distribution and spatial overage of GEOSS Clearinghouse true dataset (base map provided by NASA ‘Blue Marble’ through OGC: Web Map Service).

Table 1. A summary of experimental data.

Type	Data source	Feature number	Description
Data access records	GEOSS clearinghouse	2.03 million access records	Extracted from the GEOSS system operation log-file
Indexing dataset	GEOSS clearinghouse	129, 989 data records	Accessed through private OGC: CSW protocols
Indexing dataset (synthetic)	Synthetic	1.2 billion data records	Generated using GEOSS Clearinghouse data distribution and coverage

Figure 5. Data query performance with real-world queries.

Figure 6. Data query performance with random data queries.

Figure 7. Data query performance with mixed data queries (50% real-world queries + 50% random queries).

Figure 8. DAPR-tree performances using different local indexing schemes.