In traditional database systems, such range queries are supported using
pre-computed multiple-dimensional indices. Such indices trade-o?® some initial
pre-computation cost to achieve a significantly more e?±cient querying
capability. We discuss the design of a distributed index structure called Distributed
Index for Multidimensional data (DIM) [24, 16] for supporting multidimensional
queries in sensor networks.
307
Jinbao Li, Zhipeng Cai, and Jianzhong Li
The key to resolve multiple-dimensional range queries e?±ciently is data
locality: events with comparable attribute values are stored nearby. The basic
insight underlying DIM is that data locality can be obtained by a localitypreserving
geographic hash function. The geographic hash function finds a
locality-preserving mapping from the multi-dimensional space to a 2-d geographic
space. This mapping is inspired by k??’d trees [2]. Moreover, each node
in the network self-organizes to claim part of the attribute space for itself (we
say that each node owns a zone), so the events falling into that space are
routed to and stored at that node. Intuitively, a zone is a sub-division of the
geographic extent of a sensor field (Figure 10).
101
100
00
1110
1111
110
011
010
Fig. 10. Zone of sensor network [24].
A zone is defined by the following constructive procedure. Consider a rectangle
R on the x??“y plane. Intuitively, R is the bounding rectangle that contains
all the sensors within the network.
Pages:
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495