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

from the former steps. Finally, use the rectangle keys to retrieve data in the
CDMs and then prune the unqualifi ed data to get the query result.
k -NN Query
k -NN query is also commonly used in location based applications. Algorithm
3 shows the k -NN query algorithm in HBase and Cassandra, where K stores
the result of k nearest neighbors, QueryRect stores the rectangles which
could be scanned, dist is the range for the rectangle search, Rect scanned
stores the rectangles that have been scanned, and the data structure of
QueryRect is a queue. The k -NN query has two main parts: 1) set a range
dist to search for rectangles which overlap a square range with centroid
p and edge length 2·dist; 2) pick the nearest rectangle of p that is not scanned
and add the nearest points in this rectangle into K. The algorithm keeps
repeating steps 1 and 2 until the distance of the k-th nearest point and
p is less than or equal to dist. Part 1) in Algorithm 3 is in lines 6-11, where
RectInRegion() is used to fi nd the rectangles in the square range and line 9
pushes the rectangles that have not been scanned into QueryRect; 2) is in
lines 12-18, where line 12 pops the nearest rectangle, and line 14 will add
the points of R into K. The function RectInRegion( c , dist) in Algorithm 4