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

First, in Fig. 6a, each grid is also given a Hilbert value and each solid
point represents a data point. Note that the green area represents a query
rectangle. For instance, the data point P is located in Grid 41 because the
grid's Hilbert value is 41. In Fig. 6b, each rectangle is given a Hilbert value.
For instance, Grid 1 in Fig. 6a overlaps with the rectangles {0, 14} so that
<1, {0, 14}> is stored in the KeyTable as shown in Fig. 6c. We could get the
rectangle information through the KeyTable and the multi-attribute access
can retrieve the data effi ciently.
The decision of (M, m) and the order of the Hilbert-curve will affect the
effi ciency of the range query. Thus, we decided to dynamically generate the
values of (M, m) and the order. We knew that (M, m) infl uences the size of the
rectangles and the order decides the grid size. We observed the relationship
between the response times and the parameters (M, m), and o. As shown
in Table 1, this is the average length and width of rectangles of ten million
data size and the length of grids with different order; the average length and
width of (M, m) = (250, 125) is closed to the grid length of order 7. According
to the range query response times of the KR + -index, the range query with
fi xed (M, m) = (250, 125) had a better response time (i.e., 1.2 seconds) when
order o = 7. Notice that, for the same range query with fi xed (M, m) = (250,
125), the response time is 1.6 when o = 6. Similarly, for the same range
query with fi xed (M, m) = (250, 125), the response time is 1.9 when o =
8. We found that the closer the rectangle size and the grid size, the better
the response time for that range query. Thus we proposed a new method
that automatically determines the size of the parameters. It fi rst decides a
small value of (M, m), and evaluates the average size of the rectangles, then
calculates the closest grid size generated by order. The objective function of
o can be expressed as mino(|len(o)-avgLen(M)| + |len(o)-avgWid(M)|).
Thus, it determines the (M, m) and order automatically.

Table 1. The relationships between the parameters of the KR + -index.

(a) Average length and width of rectangles
of KR + -index.

(b) The length and width of grids of different
order.

M m Avg. len. Avg. wid.
50 25 1128.4283 2656.2368
100 50 4928.2417 4671.1948
250 125 6941.6216 6280.1025

order len.

6 15625

7 7812.5

8 3906.25

Range Query

Multi-dimensional range queries are commonly used in location based
applications. Algorithm 1 is the pseudo code for a range query in HBase and
Cassandra ( p l , p h ) is the range for the query, p l is the lower bound and p h is
the upper bound. The Hilbert curve splits the space into grids, where each