(3) The event is stored at this logical leaf node. Thus, each local leaf
is responsible for storing all the events detected in its sub-region.
Each local leaf node has b parents, where b is a tunable system parameter.
Each leaf node computes a histogram of the event values it has; it then splits
up the histogram into b equal parts, and passes these parts to its b parents.
Thus, in Figure 9 where b is 2, the leaf node would pass up the histogram for
temperature values between 0 and 49 to one parent, and the histogram for
values 50 to 99 to another parent. Through hashing the name of the index
together with the appropriate range, the leaf node locates its parents. In this
way, each parent node is responsible for 1/b of the value range, but serves four
times the geographic area covered by the child. Higher-levels of the hierarchy
306
Chapter 12 Data Management in Sensor Networks
Second??’level parents
First??’level
Leaf node [0,99]
[0,49]
[75,99]
[50,74] [0,99]
[50,99]
parent
Fig. 9. DIFs multiple roots structure [16].
are built up recursively until the whole b hierarchies are constructed. The toplevel
of this hierarchy can contain many roots, each of which is responsible for
a small part of the value range, but which covers the entire geographic region.
Given a range query for events within a temperature range say [50, 60],
the originating node first picks the set of root nodes whose individual ranges
cover the query range, and starts traversal.
Pages:
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493