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

grid has one grid key. The algorithm fi rst computes the coordinate of grids
overlapping the range query by the function Compute Coordinate Of Grid().
Grid Keys is the set of grid keys contained in the query range. For each
coordinate of grid c , the function ComputeContainGridKeys() computes
the corresponding grid keys via the Hilbert curve and adds it to the list,
GridKeys. Then, according to the key table, we could fi nd the rectangle keys
in the query range. Lines 5-8 fi nd the queried key and lines 9-10 fetch the
points in the corresponding key. The function GetContainPoint() returns
the queried data by fi rst retrieving points from Cassandra and HBase with
key k and then fi ltering out some points that are not in the query range.
As shown in Fig. 6, taking the green block as the range query, we will
show an example of how range query works. Use the query range to get the
geographic coordinates of the overlapping grids {(0, 0), (0, 1), (0, 2), (1, 0),
(1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}, then get the Hilbert values of each geographic
coordinate {0, 3, 4, 1, 2, 7, 14, 13, 8}. Second, get the keys of the rectangles
through the KeyTable such that grid 0 maps to rectangle {0}, grid 1 maps to
rectangles {0, 14}, grid 2 maps to rectangles {0, 8, 14}, etc. Thus, we can get
the queried rectangle keys {0, 8, 14}, by joining the rectangle sets obtained