MobileCompChap08L08IndexingTechniques

8/8/2019 MobileCompChap08L08IndexingTechniques

1/20

Oxford University Press 2007. All rights reserved. 1

Data Dissemination and Broadcasting

Systems

Lesson 08

Indexing Techniques for Selective Tuning


2/20


Indexing

A method for selective tuning

Indexes temporally map the location of

the buckets


3/20


Index-Based Methods

Index be first sent

It specifies the location of the bucket or

record

Consider a simple example. Let indexbe 20 at the beginning of a broadcast

cycle. It specifies that 20th bucket is of

interest and is sent to the device inresponse to previous subscription.


4/20


Indexing

A technique in which each data bucket,

record, or record block of interest isassigned an index at the previous data

bucket, record, or record block of interest

to enable the device to tune and cache

the bucket after the wait as per the offset

value


5/20


Indexing

At each location, besides the bits for the

bucket in record of interest data, anoffset value may also be specified there

While an index maps to the absolute

location from the beginning of abroadcast cycle, an offset index is anumber which maps to the relative

location after the end of present bucketof interest


6/20


Offset

Offset means a value to be used by the

device along with the present locationand calculate the wait period for tuning to

the next bucket

All buckets have an offset to the

beginning of the next indexed bucket or

item


7/20


Indexing

The server transmits this index at the

beginning of a broadcast cycle as well aswith each bucket corresponding to data

of interest to the device.

A disadvantage of using index is that it

extends the broadcast cycle and hence

increases taccess


8/20


Disadvantage of using index

Extends the broadcast cycle and hence

increases taccess


9/20


(I,m

) indexing

An index Itransmits m times during each

push of a record

An algorithm is used to adapt a value of

m such that it minimizes access(caching) latency in a given wireless

environment which may involve frequent

or less frequent loss of index or data


10/20


(I,m

)

Index format is adapted to with a suitable

m chosen as per the wirelessenvironment

This decreases the probability of missingIand hence the caching of the record of

interest

Ifm is chosen small then the powerdissipated by device is less


11/20


(I,m

)

Ifm decreased, the chances that the

cache be missed go up and the dataaccess latency increases

The value of m therefore needs to beoptimized which can be done by

employing an algorithm as stated earlier


12/20


Distributed Index-based Method

When Index I is repeated m times, the

access latency increases significantlyeven though the cache-miss probability

reduces drastically

Distributed index-based method an

improvement on the (I, m) method


13/20



In this method, there is no need to repeat

the complete index again and again

Instead of replicating the whole index m

times, each index segment in a bucketdescribes only the offset I' of data items

which immediately follow

Each index Iis partitioned into two parts

I' and I


14/20



I consists of unrepeated klevels (sub-

indexes), which do not repeat and Iconsists of topjrepeated levels (sub-

indexes)


15/20


Flexible Indexing Method

Provides dual use of the parameters (e.g.,

use ofIseg orIrec in an index segment totune to the record or buckets of interest) or

multi-parameter indexing (e.g., use of

Iseg, Irec, orIb in an index segment to

tune to the bucket of interest)


16/20


Temporal Addressing

A technique used for pushing in which

instead of repeating Iseveral times, atemporal value is repeated before a data

record is transmitted

There can be effective synchronization of

tuning and caching of the record of

interest in case of nonuniform timeintervals between the successive bits


17/20


Broadcast Addressing

A broadcast address similar to IP or

multicast address

Each device or group of devices can be

assigned an address

The devices cache the records which

have this address as the broadcasting

address in a broadcast cycle


18/20


Summary

A technique in which each data bucket,

record, or record block of interest isassigned an index at the previous data

bucket, record, or record block of interest

to enable the device to tune and cache

the bucket after the wait as per the offset

value


19/20


Summary

Index I based, (I, m) based, distributed

index based and flexible indexingmethods

Temporal and broadcast address

methods in place of the index


20/20


End of Lesson 08Indexing Techniques for Selective Tuning

Documents

MobileCompChap08L08IndexingTechniques