Global Positioning System Reference
In-Depth Information
fi nds the rectangles which overlap with the input square. It is designed by
our method for defi ning the key in the rectangles. Lines 6-8 fi nd the grid
keys which overlap the squares, and line 11 returns the rectangles which
overlap grids through checking the KeyTable.
As shown in Fig. 6, take
p
as the query point, k = 3 and given an initial
dist=0. First, we will get a rectangle 36 through the KeyTable with a square
range of length 2·dist and then insert the location points {p
9
, p
10
, p
11
} of
rectangle 36 into K. In that location points are ordered by the distance
from
p
. Second, resize the dist to the minimum distance of k-th/|K|-th
location points in K from
p
, the dist=dist(3rd location point in K,
p
) in this
example. The algorithm continues the fi rst and second step; it will add the
rectangle 55 into Rect
next
and add the location points in rectangle 55 into K.
The algorithm is stopped by dist(3rd location point in K, p) ≤ dist, and we
get the fi rst three location points {p
10
, p
9
, p
8
} in K as the query result.
Experiments
In this section, we show the experiments about the time of range query
and
k
-NN query in HBase and Cassandra with different methods: scan
databases, Hilbert curve and our method, KR
+
, and compare the KR
+
HBase
with MD-HBase (Nishimura et al. 2011).
We implement our experiments using HBase 0.20.6 with Hadoop 0.20.2
and Cassandra 0.8.2 as the underlying system. We have 8 machines, each
consisting of 2 virtual machines, 2GB memory and 500GB HDD and 64bit
Ubuntu 8.04.4. The arguments in our experiments with (M, m) = (1250, 625),
(2500, 1250) and (5000, 2500) of KR
+
are about 352, 176 and 88 rectangles
respectively. The number of grids is divided into 24 × 24, 25 × 25 and 26
× 26. The ranges of the range query are 1 km × 1 km, 5 km × 5 km, 10 km
× 10 km, 20 km × 20 km and 40 km × 40 km. The
k
-NN query with k = 10,
50, 100. The datasets have 440,912 GPS location points collected by our
Search WWH ::
Custom Search