7. Structure Duplication [16].
303
Jinbao Li, Zhipeng Cai, and Jianzhong Li
4.4 Hierarchical Search Structures
A system can be useful in sensor networks where users do not know a priori
what to look for, but can use low-overhead queries to drill-down to phenomena
of interests, such as regions where the temperature is/was unusually high.
Consider a system that allows users to e?±ciently search for such patterns by,
for example, asking a sequence of questions such as ???What was the average
temperature in area X an hour ago???? and then ???What was the average temperature
in sub-area A of area X in the last 10 minutes of that hour????. An
important leverage point for the design of such systems is that the answers to
such questions can be approximate.
The DIMENSIONS system [16, 6] is a data-centric storage system designed
to handle such queries. It builds upon prior work that describes approximate
querying of large datasets using wavelet coe?±cients of the data. While an
extended treatment of wavelets is beyond the scope of this book, we briefly
introduce wavelet encoding of data sets to give the readers an intuitive understanding
of what is possible with the DIMENSIONS system. Consider a
vector V = [5, 6, 4, 4]. The simplest wavelet transform of this vector takes elements
pairwise and computes averages recursively. Table 4 shows this process,
where each level of averaging constitutes a di?®erent resolution.
Pages:
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488