Mobile Intelligence

9.3 AIR INDEXES FOR NONSPATIAL DATA

9.3.1 Tree-Based Index

The tree-based air index is adopted from the tree-structured index in a traditional disk-based environment [1]. To organize the index of data items to be broadcast with the form of tree, the unique identifier of each data item is used as a key for index tree. The index tree keeps the arrival time of each data item on the wireless broadcast channel, unlike the tree keeping the locations of disk records in the disk-based environments. Figure 9.3 illustrates an example of an index tree for 81 data items to be broadcast, white circles mean the index nodes of the index tree and a gray square means a set of three data items. Every leaf node in the index tree keeps attribute keys of three data items and offset values to them in units of buckets as shown Figure 9.4.

Figure 9.3 Index tree for an example.

The two indexing schemes based on the index tree, that is, (1, m) indexing and distributed indexing scheme, are depicted in Figure 9.4. For (1, m) indexing, the entire index tree is interleaved with every (1/m) fraction of data items and all nodes in the index tree are placed on the wireless channel according to their level as shown in Figure 9.4(a). For the distributed indexing scheme based on the index tree, a part of the index tree is interleaved with the data items associated with it. For the organization of the distributed indexes, ...