Spatial Index Schemes for Cloud Environments - Geographical Information Systems: Trends and Technologies - page 55

do not overlap each other, which has the benefi t of reducing searching time.
The reason is that, compared with R-trees, we do not search duplicated
results using R + -trees.
Quad-trees (Finkel and Bentley 1974) are another common tree structures
for indexing multi-dimensional data. In quad-trees, each internal node has
exactly four children. However, quad-trees are not balanced trees because
a region is split into four sub-regions until the number of data points in the
region is less than or equal to a given parameter M. For instance, given the
data in Fig. 2a, Fig. 3 shows a quad-tree with M = 3.

Linearization

Linearization is a well-known technique for indexing multi-dimensional
data by transforming it into one-dimensional data. One of the most popular
methods of linearization is using space-fi lling curves, such as a Hilbert curve
and Z-ordering. Given two-dimensional data, this method fi rst divides the
map into 2 n × 2 n non-overlapping grids, where n is a parameter, and assigns
a number for each grid according to the order of traversing all the grids.
Note that the number of each grid is regarded as a key. Figure 4 illustrates an
example of linearization using a Hilbert curve with 2 1 × 2 1 grids. In Fig. 4, the
map is divided into four grids, and the keys of these grids are represented
by 0, 1, 2 and 3 according to a Hilbert curve. However, using space-fi lling
curves to index data may not be effi cient. Take check-in records indexing as
an example. If a value of n is set to be lower, it induces a larger grid size, and
the grid would possibly cover more check-in records distributed in its area.
Given a range query, all check-in records located in the grids overlapping

Fig. 4. A Hilbert curve on grids of a map.

Fig. 3. Quad-tree with M = 3.

Color image of these figures appear in the color plate section at the end of the topic.