Global Positioning System Reference
In-Depth Information
false-positives and the number of sub-queries. We observe that the KR
+
with
M = 1250 and m = 625 is slower than with M = 2500 and m = 1250 since the
former has more sub-queries, and the KR
+
with M = 5000 and m = 2500 is
slower than with M = 2500 and m = 1250 owing to the former having more
false-positives. Thus, the KR
+
with arguments about M = 2500 and m = 1250
is closest to the target of the trade-off between the number of false-positives
and the number of sub-queries. The
k
-NN query has the same effect with
the range query in the Hilbert curve and KR
+
, but it is slower than the range
query because it may need to resize the distance of searching rectangles and
query again as the number of location points is less than k.
Table 4 and Table 5 show the range query and
k
-NN query on HBase.
We compare KR
+
with the Hilbert curve and also with no index. As there
Table 2.
Cassandra-Range Query (second).
km
2
1·1
5·5
10·10
20·20
40·40
KR
+
: M1250 m625
0.118
0.696
1.221
2.003
4.899
KR
+
: M2500 m1250
0.007
0.036
0.206
0.642
1.734
KR
+
: M5000 m2500
0.234
0.776
1.454
1.665
3.748
Hilbert: order4
4
7.8
7.2
7
9.4
Hilbert: order5
5
8.9
9.1
9.1
11.3
Hilbert: order6
7.6
13.7
13.5
13.7
19.8
Scan DB
105
110
127
155
203
Table 3.
Cassandra-
k
-NN Query (second).
k
10
50
100
KR
+
: M1250 m625
0.675
1.387
1.668
KR
+
: M2500 m1250
0.039
0.088
0.657
KR
+
: M5000 m2500
0.433
0.944
1.329
Hilbert: order4
8
11.201
14.35
Hilbert: order5
10.348
15.455
19.349
Hilbert: order6
14.6
18.866
24.545
Scan DB
105
110
127
Table 4.
HBase-Range Query (second).
km
2
1·1
5·5
10·10
20·20
40·40
KR
+
: M1250 m625
1.446
5.172
6.290
10.713
13.114
KR
+
: M2500 m1250
1.019
2.656
6.481
12.810
18.552
KR
+
: M5000 m2500
3.508
5.129
10.895
14.998
21.617
Hilbert: order4
44.65
47.93
50.04
52.16
56.47
Hilbert: order5
48.82
50.99
54.77
59.83
67.12
Hilbert: order6
54.10
57.31
62.50
66.32
79.51
Scan DB
135.06
134.99
135.08
134.84
135.01
Search WWH ::
Custom Search