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

prefi x naming, for effi cient index maintenance and query processing.
Although the experiment of MD-HBase shows that the proposed indexing
method is effi cient for multi-dimensional data, it has some constraints.
Before describing these constraints, we have discovered a characteristic
of cloud managements for data access through experiments. A trade-off
exists between the number of points for getting one key and the number of
keys for scanning; a reduction in the number of points for getting one key
results in an increase in the number of keys for scanning and vice versa.
The way of splitting the space of the Quad tree and k-d tree is fi xed, which
may make some nodes store zero points. In addition, the Quad tree and the
k-d tree cannot balance the number of stored points for each node, because
they do not restrict the minimum number of points in one space. Therefore,
if we regard one node as one key, it will make the keys store unbalanced
data points, especially as the data is not uniform. Figure 11 is a Quad tree
example of space splitting for MD-HBase. According to the data points in
the map, the Quad tree will split the whole space into three. The red line
shows the splitting results, and each black grid has its Z-ordering value. For
instance, the Z-ordering value of (0,0) is 000000 and (1,0) is 000010. Then,
the key of each region split by the red line is the prefi x of the Z-ordering
value of its sub-regions. Consequently, there are 10 keys, 000000, 000001,
000010, 000011, 0001*, 0010*, 0011*, 01*, 10* and 11*. However, there may
be no data points in some regions. As mentioned above, the Quad tree and
k-d tree cannot deal with multiform distribution data effi ciently.
Fig. 11. A key formulation in MD-HBase.
Color image of this figure appears in the color plate section at the end of the topic.
Conclusions
We proposed a scalable multi-dimensional index, KR + -index, based on the
existing CDMs, such as HBase and Cassandra. It supports effi cient multi-
dimensional range queries and nearest neighbor queries. We use R + to