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

Table 5. HBase- k -NN Query (second).

k 10 50 100

KR + : M1250 m625 2.13 3.558 7.729

KR + : M2500 m1250

1.679 2.896 8.354

KR + : M5000 m2500 6.732 80.24 14.2

Hilbert: order4 54.282 60.04 67.31

Hilbert: order5 57.354 64.13 73.52

Hilbert: order6 67.492 70.458 77.341

Scan DB 135.12 135.250 135.22

is no indexing, it needs to scan all of the data then fi lter out points which
do not match the query. The Hilbert curve is also uniform dividing with
order 4, 5, 6. As we have seen, the no index method has performs badly
due to scanning all of the data. The Hilbert curve is much better than no
index both for range query and k -NN query. When the order is 4, the time
for the range query of 1 × 1 km is 44.6s, and the time for the range query of
40 km × 40 km km is 56.4s. When the order is 4 and k = 10, the time for the
k -NN query is about 54.2s. With the same evaluation of Cassandra, KR + is
faster than the Hilbert curve and when M = 2500, m = 1250 the KR + will get
the best performance. The KR + with M = 2500 and m = 1250 of range query
for 1 km × 1 km is about 1.01s and k -NN query for k = 10 is about 1.67s.
Finally, we compare KR + with MD-HBase for skewed data and uniform
data. Figure 8a and b show range query and k -NN query for uniform data.
KR + slightly improves the effi ciency compared with MD-HBase for uniform
data. KR + with M = 2500 and m = 1250 for 1 km × 1 km range query is about
1.2s and k -NN is about 2.0s when k = 10. In addition, with skewed data,
Fig. 9a and b show that KR + is much faster than MD-HBase. KR + could
balance the number of false-positives and the number of sub-queries so
that it improves the effi ciency of range query and k -NN query markedly.
KR + for range query 1 km × 1 km is about 1.0s and k -NN query when k =

30

18

KR+: o4 M2500 m 1250
MD-HBase

KR+: o4 M2500 m 1250
MD-HBase

25

15

20

12

15

9

10

6

5

3

0

0

100 400 1600 10 50 100

range(km 2 ) k

Fig. 8. Uniform data distribution.

Color image of this figure appears in the color plate section at the end of the topic.