299
Jinbao Li, Zhipeng Cai, and Jianzhong Li
Geographic Hash Tables
We have said that the essence of a data-centric storage system is captured
at its interface, which supports a put() operation that stores data by name
within the network, and a get() operation that retrieves data by name. In the
following discussion, keys are used to represent a whole named data or part
of it.
Geographic Hash Tables (GHTs) is an implementation of this interface for
sensor networks. In a GHT, event names are randomly hashed to a geographic
location (i.e., an x, y coordinate). This mapping is multi-to-one. Then, a
put() operation stores an event at the node which is the closest to the hashed
location, and a get() operation retrieves one or more events from that node.
Implicitly, a GHT specifies a set of queries that it allows. The simplest
kind of query it allows is an enumeration query, a list of all events matching
a key k. It can also trivially support any statistic (e.g., count, sum, average)
defined on that enumeration. Applications can determine which parts of an
event name are used to compute the geographic hash value. This choice can
crucially a?®ect the performance of the overall system, as well as the set of
supported queries, of course. For example, an application can hash events by
sensor type so that all temperature sensor readings are stored at one node.
Alternatively, an application may choose to hash sensor values to di?®erent
locations so that temperature readings with a value of 10?—¦C can be stored at
a di?®erent node than, say readings of 20?—¦C.
Pages:
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482