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

use an R + -tree (Sellis et al. 1987) to divide the data, and the rectangles in
the leaf nodes of the tree index are treated as dynamic grids. The reasons
for using an R + -tree are described as follows. First, we could get a balance
between the grids sizes and the times of grid accesses by adjusting the two
parameters, M and m, of the R + -tree. Second, compared with other variants
of the R-tree, the leaf nodes do not overlap each other, and thus it is a benefi t
as there is no redundant retrieval of the same data from different keys and
it is easy to defi ne different keys for each rectangle of a leaf node. Moreover,
the second challenge is how to design the key names of these grids to
support effi cient queries on BigTable management systems. We observed
the characteristics of CDMs as follows: a CDM has a fast key-value search
and it is fast to Scan keys which are in a dictionary order. Based on these
characteristics, we propose an approach to defi ne the key name of a grid to
support effi cient queries. In the experiment, we implement the proposed
index on two well-known CDM systems, HBase and Cassandra, and we
compare the performance of the proposed index with the existing index
methods. The experimental results demonstrate that our proposed index
outperforms the existing index methods via skewed data. We summarize
the contributions of this chapter as follows:
• We propose an effi cient multi-dimensional index structure, the KR + -
index, on CDMs to support effi cient multi-attribute accessing of
skewed data.
• Based on the KR + -index, we define new efficient spatial query
algorithms, range query and k -NN query.
• The experimental results show that the proposed KR + -index
outperforms competitors.
The remainder of the chapter is organized as follows. First, we illustrate
the background of multi-attribute access, multi-dimensional indexes and
Hilbert curves in section “Background”. We next propose the KR + -index in
section “The Multi-dimensional Index Structure”. In section “Experiments”,
we evaluate the performance of the proposed KR + -index for multi-attribute
accessing of CDMs. In section “Related Work”, we illustrate the existing
CDMs, traditional index techniques, and some cloud indexes on CDMs.
Finally, we conclude the chapter in section “Conclusions”.
Background
Multi-attribute Access
For multi-dimensional data searching, multi-attribute access is used to
restrict multiple attributes at the same time. For instance, Range Query and
k -NN Query are common queries of multi-attribute access and are widely
used in location-based services.