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

Range Query
Given a set of data points P and a spatial range R, a range query can be
formulated as “searching the data points in P that are located in the spatial
range R”. Note that, in this chapter, each data point has location information,
e.g., a longitude and latitude. Without loss of generality, in this chapter, a
spatial range is represented by a rectangular range.
For instance, in Fig. 1a, given 15 restaurants, marked by gray points,
and a red query range R, the range query is to search for which restaurants
are located in the range R. As shown in Fig. 1a, the result of the range query
is {p 1 , p 2 , p 3 , p 4 , p 5 }.
Fig. 1. Examples of multi-attribute access.
Color image of this figure appears in the color plate section at the end of the topic.
k-NN Query
Given a set of data points P, a query location p = (p x , p y ) and a constant k,
a k -NN query can be formulated as “searching the data points in P that are
the k nearest data points of p”.
For example, in Fig. 1b, given 15 restaurants, a user-specifi ed location p
marked in red and k = 5, a 5-NN query here is to search for the fi ve nearest
restaurants to p. Thus, the search result of this query is {p 4 , p 5 , p 6 , p 7 , p 8 } as
shown in Fig. 1b.
Multi-dimensional Index Techniques
Tree Structures
R-trees, developed for indexing multi-dimensional data, are widely used in
multi-attribute accesses. For instance, given fi fteen checked-in restaurants