Mobile Intelligence

9.4 AIR INDEXES FOR SPATIAL DATA

To support various spatial queries in traditional database systems, indexing techniques for spatial data have been proposed such as R-tree, R*-tree, quad-trees, and k–d-trees [8–10, 25]. However, they cannot be easily adopted in wireless data broadcast because of their nonlinear structure not matching with linear access pattern of mobile clients. Recently, some air indexes have been proposed for processing spatial query in wireless broadcast environment [15–17, 22].

9.4.1 Tree-Based Index

In Ref. [24], window query processing is studied on indexes of tree structure. However, the technique proposed in Ref. [24] cannot support kNN query.

9.4.2 Space Partition-Based Indexes

D-tree is a binary search tree based on Voronoi Diagram (VD) to support nearest neighbor (NN) query [26]. It recursively partitions the VD into two subspaces until every space has a region and holds information on the polylines of the subspaces. This makes the size of D-tree big, leading to Bcast lengthened and access time deteriorated. Also, D-tree cannot easily extend to kNN query.

Grid partition index is a hybrid index combining VD and grid to efficiently support NN query by reducing the search space [27]. In the index, VD is partitioned into grid cells to map a query point to a grid cell. The scheme has two-leveled indexes: the upper level built on the grid and the lower level built on data items being potential NNs and facilitating the access to them.

9.4.3 Space Filling Curve-Based ...