A Hybrid Index Technique for Power Efficient Data Broadcast.
The intention of power conservative indexing techniques for wireless data broadcast is to reduce mobile client tune-in time while maintaining an acceptable data access time. In this paper, we investigate indexing techniques based on index trees and signatures for data disseminated on a broadcast channel. Moreover, a hybrid indexing method combining strengths of the signature and the index tree techniques is proposed. Different from previous studies, our research takes into consideration of two important data organization factors, namely, clustering and scheduling. Cost models for the three indexing methods are derived for various data organization accommodating these two factors. Based on our analytical comparisons, the signature and the hybrid indexing techniques are the best choices for power conservative indexing of various data organization on wireless broadcast channels.
Introduction
Due to resource limitations in a mobile environment, it is important to efficiently utilize wireless bandwidth and
battery power in mobile applications. Wireless broadcasting is an attractive approach for data dissemination in a
mobile environment since it tackles both bandwidth efficiency and power conservation problems [BI94, IVB96,
SRB97, HLL98c]. On one hand, data disseminated through broadcast channels allows simultaneous access by
an arbitrary number of mobile users and thus allows efficient usage of scarce bandwidth. On the other hand,
the mobile computers consume less battery power when passively monitoring broadcast channels than actively
interacting with the server by point-to-point communication.
Three criteria are used in this paper to evaluate the data access efficiency of broadcast channels:
ffl Access Time: the average time elapsed from the moment a client 1 issues a query to the moment when all the
requested data frames are received by the client,
The author is now with Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada
1 In this paper, we use 'client' or 'mobile client' to refer to a user with a mobile computer.
ffl Tune-in Time: the period of time spent by a mobile computer staying active in order to obtain the requested
data.
Indexing Efficiency: The tune-in time saved per unit of access time overhead for indexing 2 .
While access time measures the efficiency of access methods and data organization for broadcast channels, tune-in
time is frequently used to estimate the power consumption by a mobile computer. Indexing efficiency, which
correlates the access time and tune-in time, is used to evaluate the efficiency of indexing techniques in terms
of minimizing the tune-in time while maintaining an acceptable access time overhead. In other words, a power
conservative indexing technique has to balance out the index overhead (in terms of access time increased) and the
time saved in order to maximize the indexing efficiency.
To facilitate efficient data delivery on broadcast channels, scheduling and clustering are frequently used to
select and organize data for broadcast. Broadcast scheduling policies determine the content and organization of
data broadcasting based on aggregate user data access patterns. Broadcast disk [AAFZ95] is one of the well-known
broadcast scheduling methods. In contrast, flat broadcast refers to the broadcast scheduling where each
data frame is broadcast once in every cycle [HLL98c]. When all frames with the same attribute value are broadcast
consecutively, the data broadcast are called clustered on that attribute 3 . In contrast, the data broadcast are non-clustered
on an attribute when all frames with the same value of that attribute are not broadcast consecutively.
Clustering allows continuous reception of data with a specific attribute value.
Several indexing techniques for broadcast channels have been discussed in the literature[IVB96, LL96b, CYW97,
SV96]. The basic idea behind these techniques is that, by including information about the arriving schedule of
data frames in the broadcast channels, mobile computers are able to predict the arrival time of the requested data
frames and thus, selective tuning in can be realized. Signature and index tree techniques [IVB96, LL96b] represent
two different classes of indexing methods for broadcast channels. According to [IVB96, LL96b], the index
tree method is based on clustered data organization, while the signature methods don't presume a clustered data
organization 4 . Moreover, indexing techniques used in these papers only took flat broadcast into consideration.
In [IVB96] index frames were treated in the same way as a data frame, although a better approach is to separate
index frames from data frames. [LL96b] did not consider the clustered data. Although the authors demonstrated
that the signature size played an important role in terms of data filtering efficiency and access latency, the optimal
signature size was not given.
In this paper, we extend the existing works further. For the index tree method, since the size of an index frame
is normally not equal to that of a data frame, to accurately estimate the access time and the tune-in time, we
separate the index frames from data frames. For the signature method, we derive formulae to estimate the optimal
signature size. In addition, scheduling and clustering are considered together with the index methods. The tune-in
time and the access time cost formulae are developed to cover the cases: i) flat scheduling and clustered; ii) flat
scheduling and non-clustered; and iii) broadcast disks scheduling and clustered. To our knowledge, there is no
systematical study and comparison of the power conservative indexing techniques in the literature which takes both
clustering and scheduling issues into account. In addition, we propose a new indexing method, called hybrid index,
which takes strengths of both index tree and signature methods. Those three index methods are evaluated based
on our criteria, namely, access time, tune-in time and indexing efficiency. Our results show that clustering and
scheduling have major impacts on data organization of wireless data broadcast. We also conclude that the hybrid
and signature methods give superior performance to the index tree method for various broadcast data organization
accommodating the clustering and scheduling factors.
Every indexing technique usually introduces non-zero access time overhead.
3 In this paper, we only consider the case of single attribute indexing and clustering. Issues involving multiple attribute indexing and
clustering are addressed in [HLL98b].
4 Even so, the integrated signature and multi-level signature schemes can benefit from a clustered data organization for broadcast
channels.
The rest of the paper is organized as follows. Section 2 gives an informal introduction of the broadcast channels,
indexing techniques and system parameters used in performance evaluation and comparisons. In Section 3, indexing
techniques based on index tree and signature methods are re-examined by taking the clustering and scheduling
factors into consideration. In Section 4, a hybrid index scheme and corresponding cost models for access time and
tune-in time are developed. Section 5 evaluates the indexing techniques in terms of tune-in time, access time, and
indexing efficiency. Section 6 is a review of related work. Finally, Section 7 concludes the paper.
2 The Data Organization for Wireless Broadcast
In this section, we briefly introduce the concept of broadcast channels and some of the terminologies used. We
assume that a base station is serving the role of an information server which maintains various kinds of multimedia
data, including texts, images, audio/video and other system data. The server periodically broadcasts, on a specific
channel, data of popular demands as a series of data frames to a large client population. These data frames vary in
size and each frame consists of packets which are the physical units of broadcast. The header of a frame contains
signals for synchronization and meta-information such as the type and the length of the frame. Logically the data
frames are classified into two types: record frames and index frames, where record frames contain data items and
index frames contain indexing information such as index tree nodes or signatures for a set of data items. Those
two types of frames are interleaved together in a cycle. The clients retrieve the frames of their interest off the air
by monitoring the broadcast channel. Since a set of data frames is periodically broadcast, a complete broadcast of
the set of data frames is called a broadcast cycle. The organization of data frames in a broadcast cycle is called a
broadcast schedule.
Data organization on the broadcast channels have great impacts on data access efficiency and power consump-
tion. Data frames can be clustered based on attributes. Based on the results in [IVB96], index tree techniques result
in more efficient access for clustered information than non-clustered one. In this paper, we take both clustered and
non-clustered data organization into consideration. Generally speaking, a non-clustered data organization can be
divided into a number of segments, called meta segments [IVB96], with non-decreasing or non-increasing values
of a specific attribute. These meta segments can be considered as clustered and thus the indexing techniques for
clustered data can be applied to them. To facilitate our study, we use the scattering factor M , the number of meta
segments in the data organization, to model the non-clusterness of a data organization 5 .
Since access latency is directly proportional to the volume of data being broadcast, the volume of data in a
broadcast cycle should be limited in such a way that only the most frequently accessed data frames are broadcast
on the channel while the remaining data frames can be requested on demand through point-to-point connections
[HLL98c, AFZ97, SRB97]. The server must determine the set of data frames to be broadcast by collecting statistics
about data access patterns.
Due to some timely events, the client access pattern sometimes shows skewed distributions, which may be
captured by Zipf or Gaussian distribution functions. In this case, scheduling data frames in broadcast disks (refer
to Appendix and [AAFZ95] for detail) can achieve a better performance in terms of the access time and is a very
important technique. As indicated in [AAFZ95], in addition to performance benefits, constructing a broadcast
schedule on multi-disks can give clients the estimated time when a particular data frame is to appear on the
broadcast channel. This is particularly important for selected tune-in, data prefetching [AFZ96b], hybrid pull
and push technique [SRB97, AFZ97], and updates [AFZ96a]. Therefore, the application of the index methods to
broadcast disks is studied in this paper.
The broadcast disks method has better access time when the data frames with the same attribute values are
clustered in one of the minor cycles. By receiving the cluster of data frames together, the mobile computer can
answer the query without continuing to monitor the rest of broadcast cycle. This can be achieved by placing
all of the data frames with the same indexed attribute value as a cluster on the same broadcast disk. The whole
5 To simplify our discussion, we neglect the variance of the meta segment size.
cluster of data frames are brought to the broadcast channel as a unit. Depending on speed of broadcast disks where
this cluster is located, these data frames may appear several times in minor cycles. Thus, the resulting broadcast
cycle is different from the completely clustered broadcast cycle. For broadcast scheduling adopting broadcast
disks without using clustering, we simply consider the resulting broadcast cycle as non-clustered. In that case,
broadcast disks lose their advantages over flat broadcast. Thus, when we consider index techniques for broadcast
disks in the later sections of this paper, we only consider the clustered case. We assume only one broadcast channel
since a channel with large bandwidth is logically the same as multiple channels with combined bandwidth of the
same capacity. Moreover, it incurs smaller overheads of administrating than multiple channels. With the same
token, we assume that index information is disseminated on the same broadcast channel. Finally, we assume that
updates are only reflected between cycles. In other words, a broadcast schedule is fixed before a cycle begins.
D Number of information frames (excluding index frames) in the broadcast cycle
F Number of distinct information frames in the broadcast cycle
Average number of packets in an information frame
S Selectivity of query: average number of frames containing the same attribute value
Scattering factor of an attribute, which is the number of meta segments of the attribute

Table

1. System Parameter Setting

Table

1 gives the parameters which describe the characteristics of a broadcast cycle. The cost models for the
various index methods discussed later in this paper are derived based on these parameters. Although the sizes of
data frames may vary, we assume frames to be a multiple of the packet size. Both access time and tune-in time
are measured in terms of number of packets. Before we develop the cost models for various index methods in
broadcast disks, we derived a theorem 6 for the optimal broadcast scheduling based on multiple broadcast disks
(please refer to Appendix for proof). The broadcast schedules derived from the theorem is used in our analysis
later.
Given the number of data frames to be broadcast, D, the number
of disks, N , the size of disk
and the broadcast frequency 7 of disk i,
broadcasting a data frame d on disk i, 8i fixed inter-arrival time
can achieve the optimal access time. In that case, to retrieve data frame d from disk i, client needs to scan, on an
average, D
frames.
3 Basic Indexing Techniques
In this section we discuss the basic ideas behind the index tree and the signature methods. We describe the
distributed indexing and integrated signature techniques because they are the best methods of their class for single
attribute indexing. The analytical cost models for the access time and the tune-in time for clustered and non-clustered
data broadcast are presented. Moreover, the application of these index techniques to broadcast disks is
also considered. Due to space limitations, we don't give all the derivations of these cost models. Interested readers
can refer to [IVB96] and [LL96b] for more details.
the leaves of an index tree. The access method for retrieving data frames with an index tree technique involves the
following steps:
ffl Initial probe: The client tunes into the broadcast channel and determines when the next index tree is broadcast

The client follows a list of pointers to find out the arrival time of the desired data frames. The
number of pointers retrieved is equal to the height of the index tree.
ffl Retrieve: The client tunes into the channel and downloads all the required data frames.

Figure

1 depicts an example of an index tree for a broadcast cycle which consists of 81 data frames [IVB96].
The lowest level consists of square boxes which represent a collection of three data frames. The index tree is
shown above the data frames. Each index node has three pointers 8 .
a2 a3
Non Replicated
Replicated Part
I

Figure

1. A Full Index Tree
h Height of the whole index tree
t Number of upper levels in the index tree that are replicated
T Number of packets in an index tree node
n Number of search keys plus pointers that a node can hold

Table

2. Parameter Setting for Index Tree Schemes

Table

2 gives the parameter setting for the index tree cost model. To reduce access time while maintaining a
similar tune-in time for the client, the index tree can be replicated and interleaved with the information. Distributed
indexing is actually one index replication and interleaving method. The index tree is broadcast every 1
d of the file
during a broadcast cycle. However instead of interleaving the entire index tree d times, only the part of the index
tree which indexes the data block immediately following it is broadcast. The whole index tree is divided into two
parts: replicated and non-replicated parts. The replicated part constitutes the upper t levels of the index tree and
each node in that part is replicated a number of times equal the number of children it has, while the non-replicated
part consists of the lower and each node in this part appears only once in a given broadcast cycle.
Since the lower levels of an index tree take up much more space than the upper part (i.e., the replicated part of the
index tree), the index overheads can be greatly reduced if the lower levels of the index tree are not replicated. In
this way, access time can be improved significantly without much deterioration in tune-in time.
To support distributed indexing, every frame has an offset to the root of the next index tree. The first node of
each distributed index tree contains a tuple, with the first field as the primary key of the record that was broadcast
last and the second field as the offset to the beginning of the next broadcast cycle. This is to guide the clients that
8 For simplicity, the three pointers of each index node in the lower most index tree level is represented by just one arrow.
have missed the required record in the current cycle to tune to the next broadcast cycle. There is a control index
at the beginning of every replicated index to direct the client to a proper branch in the index tree. This additional
index information for navigation together with the sparse index tree provides the same function as the complete
index tree.
We assume that each node of the index tree takes up T packets and X[h] and X[t], respectively, are the total
number of nodes of the full index tree and the replicated part of the index tree. The number of nodes in the i-th
level of the index tree is denoted as L[i].
In the distributed index tree, each node, p, in the replicated part is repeated as many times as the number of
children that p has. Thus, the root is broadcast L[2] times and nodes at level 2 are broadcast L[3] times etc. For
the index tree in Figure 1, since each node has three children, the root and nodes at level 2, i.e., a 1 , a 2 , and
a 3 , are broadcast 3 and 9 times, respectively. Therefore, in a broadcast cycle, the total number of nodes in the
replicated part is
1. Additionally, the number of index nodes that are located below
the t-th level of the index (i.e., the non-replicated) is, Hence, the total number of index nodes in a
cycle is, which equals to X[h] As a result, the index overhead is
In the above discussion, we assumed that the file is clustered. For a non-clustered broadcast cycle, we can still
apply index tree techniques to each meta segment. Instead of using one index tree for the entire broadcast cycle, an
index tree is created for each meta segment. However, each index tree indexes all the values of the non-clustered
attribute rather than indexing just the attribute values that appear in the current meta segment. For attribute values
that do not appear in the current meta segment, a pointer in the index tree points to the next occurrence of the data
frame with the desired attribute values. Thus, there are M distinct index trees for a broadcast cycle consists of M
meta segments, The total overhead for putting index trees in a broadcast cycle is T
packets.
To simplify the cost models, we average the index tree overhead to each data frame so that the size of a frame
is considered to consist of a data part and an index overhead part. Of course, the actual index tree overhead for
each data frame is different, but from the statistics point of view we can assume that all data frames have the same
average index tree overhead. The average overhead for each data frame is
The replicated index tree part is broadcast every 1=L[t fraction of each meta segment. Therefore, a broadcast
cycle is divided into M \Delta L[t data blocks with replicated index nodes at the beginning of each block. Let P
be the average number of packets for a data frame, the length of each block is
Flat Broadcast: Let us derive the access time and the tune-in time estimates for flat broadcast first. Since each
frame is broadcast once in a cycle, the number of data frames in the broadcast, D, is equal to the number of distinct
frames F . The initial probe period is the time to reach the index frame at the beginning of the next data block and
can be estimated as:
For a clustered broadcast, the scattering factor, and the expected number of data frames before the
arrival of the desired frames is Hence, the access time is:
initial probe time +waiting time before first desired frame arrives
waiting time for retrieving all desired frames in the broadcast
For a non-clustered broadcast cycle (M ? 1), the access time is:
waiting time for retrieving all desired frames in the broadcast
The tune-in time for both clustered and non-clustered broadcast cycle depends on the initial probe, the scanning of
index tree, the extra scanning of index tree in subsequent meta segments, and the retrieval of S data frames. Thus,
the tune-in time of the index technique is upper bounded by:
For a fully balanced indexing tree, the height of the tree, the number of nodes at i-th level, and the number of
nodes in the upper t levels of the index tree are:
F
According to [IVB96], the optimal height of the replicated part of the index tree for a broadcast, denoted as - t, can
be estimated as:
(log
F
while for a non-clustered broadcast cycle, the optimal number of replicated levels - t within a meta segment is:
(log
Broadcast Disks: For broadcast disks, as discussed in Section 2, data frames with the same attribute values are
clustered in one minor cycle. In this case, we can treat each minor cycle of the broadcast disks as a meta segment 9 .
An index tree can be built for each minor cycle. Similar to flat broadcast, the initial probe period, the time to reach
the index frame at the beginning of the next data block, can be estimated as:
where the number of data frames in the broadcast is
and the scattering factor, M , is equal to the
number of minor cycles in the broadcast (i.e., the LCM of the relative frequency of the disks). Hence, the access
time for a clustered broadcast is:
initial probe time +waiting time before first desired frame arrives
waiting time for retrieving all desired frames in the broadcast
Note that in the above equation, based on Theorem 1, the expected number of data frames before the arrival of the
desired frames is
and the optimal number of replicated levels within a minor cycle can be derived from
Equation 2.
9 Note that it is different from the meta segments for a non-clustered flat broadcast, where frames with the same attribute value may be
scattered in several meta segments.
Since all the desired data frames are clustered in one minor cycle, the tune-in time is the same as in flat broadcast
for a clustered broadcast cycle, i.e.,
3.2 The Signature Technique
Signature methods have been widely used for information retrieval. A signature of a data frame is basically
a bit vector generated by first hashing the values in the data frame into bit strings and then superimposing them
together. The signature technique interleaves signatures with their associated data frames in data broadcasting
[LL96b].
To answer a query, a query signature is generated in a similar way as a data frame signature based on the query
specified by the user. The client simply retrieves information signatures from the broadcast channel and then
matches the signatures with the query signature by performing a bitwise AND operation. When the result is not
the same as the query signature, the corresponding data frame can be ignored. Otherwise, there are two possible
cases. First for every bit set in the query signature, the corresponding bit in the data frame signature is also set.
This case is called true match. Second the data frame in fact does not match the search criteria. This case is called
false drop. Obviously the data frames still need to be checked against the query to distinguish a true match from a
false drop.
The primary issue with different signature methods is the size and the number of levels of the signatures. The
access method for a signature scheme involves the following steps:
ffl Initial probe: The client tunes into the broadcast channel for the first received signature.
ffl Filtering: The client accesses the successive signatures and data frames to find the required data. On an
average, it takes half of a broadcast cycle for the client to get the first frame with the required attribute.
ffl Retrieve: The client tunes in to get the successive desired data frames from the channel.
k number of information frames indexed by an integrated signature
p number of bits in a packet
R the size (number of packets) of an integrated signature

Table

3. Parameter Setting for Signature Scheme
The number and the size of the signatures and the average false drop probability of the signatures 10 affect
tune-in time and access time. The average false drop probability may be controlled by the size of the signatures.
The initial probe time is related to the number of signatures interleaved with the data frames. Table 3 defines the
parameters for signature cost models. Estimation of the average false drop probability is given in the following
Lemma [LL96b]:
Given the size of a signature, R, the number of bit strings superimposed
into the signature, s, the average false drop probability for the signature is,
Each data frame may have different false drop probabilities. To simplify the cost model, we use average false drop probability to
estimate the access time and the tune-in time when a large number of queries are sampled (i.e., many data frames are retrieved).
In [LL96b], three signature algorithms, namely simple signature, integrated signature, and multi-level signa-
ture, were proposed and their cost models for access time and tune-in time were given. For simple signatures,
the signature frame is broadcast before the corresponding data frame. Therefore, the number of signatures is
equal to the number of data frames in a cycle. An integrated signature is constructed for a group of consecutive
frames, called a frame group. The multi-level signature is a combination of the simple signature and the
integrated signature methods, in which the upper level signatures are integrated signatures and the lowest level
signatures are simple signatures. Since the three signature algorithms have been extensively compared in the literature
[LL96b, HLL98a], we don't repeat the comparisons here. In the context of this study, simple signature is not
very efficient since it will be generated from only one attribute. Thus, we select the integrated signature method to
compare with the index tree method and the new index methods proposed later in this paper.
A Frame Group
Info
Frame
Info
Frame
Info
Frame
Info
Info
Frame
A Broadcast Cycle
Integrated Signature
Info
Frame
Frame

Figure

2. An Example of the Integrated Signature Technique

Figure

2 illustrates an integrated signature scheme. An integrated signature indexes all of the data frames between
itself and the next integrated signature. The integrated signature method is general enough to accommodate
both clustered and non-clustered data broadcast. For clustered data broadcast, a lot of data frames can be indexed
by one integrated signature. According to Lemma 1, the smaller the number of bit strings s superimposed into
an integrated signature, the lower the false drop probability. The integrated signature generated for a clustered
broadcast cycle has the effect of reducing the number of bit strings superimposed. To maintain a similar false drop
probability for a non-clustered broadcast cycle, the number of data frames indexed by an integrated signature may
be reduced. Determining the number of data frames for signature generation requires further study.
To simplify our discussion, we assume that frames with the same attribute value for an attribute a are evenly
distributed in each meta segment. Consequently, the number of frames with the same attribute value in each meta
segment is dS=Me, where the attribute a has a selectivity S and a scattering factor M . Let k be the number
of data frames indexed by an integrated signature. The number of distinct attribute values used for signature
generation, s, can be estimated as dk=dS=Mee. For frames in a meta segment, the average number of qualified
frames corresponding to a matched integrated signature, called locality of true matches l (1 - l - k), can be
estimated as, l = k=dk=dS=Meee, for frames which are randomly distributed over the file, l is equal to 1.
Flat Broadcast: Next, we derive the access time and the tune-in time for clustered and non-clustered broadcast
cycles. Let SIG be the average signature overhead for each data frame. Then, Once again, we
assume that the expected number of data frames before the arrival of the desired frames is C .
For clustered data broadcast, the access time can be derived as follows:
initial probe time +waiting time before first desired frame arrives
waiting time for retrieving all the desired frames in the broadcast
(R
and the tune-in time is:
true match frames in the broadcast
integrated signatures before the first desired frame
false drop frames before the first desired frame
For a non-clustered broadcast cycle, the access time is:
waiting time for the first desired frame to arrive
waiting time for retrieving all the desired frames in the broadcast
(R
and the tune-in time is:
true match frames in the broadcast
integrated signatures for the retrieval of all the desired frames
false drop frames for the retrieval of all the desired frame
According to Lemma 1, we have, P We differentiate Equation (4) or (5) with respect to R and
let @TUNE=@R equal zero. Then the optimal signature size (number of packets), -
R, can be computed as:
s
s
Broadcast Disks: For broadcast disks, the access time and the tune-in time can also be obtained by Equations
(3) and (4) respectively. Compared with flat broadcast, the difference is in the parameter C , i.e., for flat broadcast
broadcast disks
and
4 The Hybrid Index Approach
Both the signature and the index tree techniques have advantages and disadvantages in one aspect or the other.
For example, the index tree method is good for random data access, while the signature method is good for
sequentially structured media such as broadcast channels. The index tree technique is very efficient for a clustered
broadcast cycle, but the signature method is not affected much by clustering factor. While the signature method
is particularly good for multi-attribute retrieval, the index tree provides a more accurate and complete global view
of the data frames based on its indexed value. Since the clients can quickly search in the index tree to find out the
arrival time of the desired data, the tune-in time is normally very short. Since a signature does not contain global
information about the data frames, it can only help the clients to make a quick decision on whether the current
frame (or a group of frames) is relevant to the query or not. The filtering efficiency heavily depends on the false
drop probability of the signature. As a result, the tune-in time is normally high and is proportional to the length of
the broadcast cycle.
Data Block
a3
Sparse Index Tree
Signature of the following frame group
I
Data Block Data Block
Info
Frame
Info Info Info Info
Frame Frame Frame Frame Frame
Frame
Info Info
Info
Frame
A Broadcast Cycle

Figure

3. The Hybrid of Index Tree and Signature
In this section, we develop a new index method, called hybrid index, which builds on top of signatures a sparse
index tree to provided global view for data frames and their corresponding signatures. A key-search pointer node
in the sparse index tree points to a data block of consecutive frames and their corresponding signatures (refer to

Figure

3).
The index tree is called sparse tree because only upper t levels of the whole index tree are constructed. Ob-
viously, the sparse index tree overhead depends on t. The larger the t, the more precise location information the
sparse tree provides, and the higher the access time overhead. One extreme case is t equals h the number of the
whole index tree levels. The hybrid index evolves to the index tree method. On the other hand, if t equals zero,
the hybrid index method becomes the signature method.
To retrieve information, the client can search the sparse index tree to obtain the approximate location information
about the desired data frames. Since the size of the upper t levels of an index tree is usually small the overhead
for this additional index is very small.
Since the hybrid index technique is built on top of signature method, it retains all of the advantages that a
signature method has. However, the global information provided by the sparse index tree improves tune-in time
considerably. The general access method for retrieving data with this technique now becomes:
ffl Initial probe: The client tunes into the broadcast channel and determines when the next index tree arrives.
ffl Upon receipt of the index tree, the client accesses a list of pointers in the index tree to find out when
to tune into the broadcast channel to get to the nearest location where the required data frames can be found.
ffl Filtering: At the nearest location, a successive signature filtering is carried out until the desired data frames
are found.
ffl Retrieval: The client tunes into the channel and downloads all the required data frames.
4.1 Cost Model Analysis
Based on the above definition of the hybrid indexing method, we derive an estimates of the access time and the
tune-in time. The sparse index tree is the same as the replicated part of the index tree method. The average waiting
time for retrieving one data frame from the broadcast cycle with M meta segments can be expressed as:
where TREE and SIG are the index overheads of the index tree parts and the signature parts of a frame. The
average number of data frames in one data block D[B] can be calculated in a similar way as in the index tree
method, which is D=(M 1]). Thus, the total index tree and signature overheads in a data block are
respectively. Hence, the average initial probe time for the index tree is half of the
data block:
Flat Broadcast: For the clustered broadcast cycle with flat broadcast scheduling, the expected access time for
hybrid indexing method is:
and the expected number of data frames before the arrival of the desired frames C is F=2. If the
broadcast cycle is non-clustered, then there is one sparse index tree for each meta segment. Index tree technique
is applied in each meta segment. Hence, the expected access time is:
For both clustered and non-clustered broadcast cycle with flat broadcast scheduling, the tune-in time primarily
depends on the initial probe of the client to determine the next occurrence of the control index, the access time
for the index tree part which equals to the number of levels t of the sparse index tree, the tune-in time for the
data block B, the selectivity of a query S, and the successive access to M meta segments. Therefore, it is upper
bounded by:
where TUNEB is defined as the tune-in time for filtering data block B with the signature technique. It can be
estimated as follows:
every signature in half the length of the data block
data frames in half the length of the data block B
Broadcast Disks: For broadcast disks, the access time for hybrid indexing method can be obtained by Equation
(7) (i.e., for broadcast disks
and
The tune-in time of broadcast disks is the same as
that of flat broadcast for a clustered cycle (i.e., let Equation (8)).
Note: according to Equation (8), the tune-in time is proportional to M . Hence, the hybrid method is efficient
only for the broadcast cycle with small M . Actually, the sparse index tree introduces overhead for the non-clustered
broadcast cycle with large M . In this case, retrieval based on signatures can result in better tune-in
time. However, the hybrid method supports multi-attribute indexing very well [HLL98b]. For an attribute with
small scattering factor, a sparse index tree can be built to reduce the tune-in time. For an attribute with high
scattering factor, there is no need to build the sparse index tree and the client simply filters out the requested
data frames sequentially and ignores the sparse index tree. We extend the hybrid index with control information,
which includes the size of the sparse index tree and the size of the data block. When a query is specified on a
non-clustered attribute, this control information is used to direct the client to the beginning of the next data block.
Starting there, the client matches the signatures one by one for each data frame in that data block. Hence, the
access time for non-clustered information is the same as Equation (7). In order to skip each of these index trees,
we assume that the client needs to retrieve an index node to get information such as the size of the sparse index
tree and the size of the data block. Therefore, the tune-in time is:
where TUNE Sig is defined to be the tune-in time for the corresponding signature scheme used (i.e., integrated
signature in this paper).
5 Evaluation of Index Methods
In this section, we compare the access time, the tune-in time, and the indexing efficiency of the index tree,
the integrated signature, and the hybrid techniques. We also include the case where no index is used (denoted as
non-index) as a baseline for comparisons. Our comparisons are based on the cost models developed previously.
Orthogonal to the index method, frames can be broadcast based on broadcast disks or flat broadcast. Thus, there
are various combinations to be considered.
For flat broadcast, each data frame appears once in a given broadcast cycle. Therefore, the number of data
frames in the broadcast D equals the number of distinct frames F . For a clustered broadcast cycle (i.e.,
on average, half of a broadcast cycle needs to be scanned before the desired frames arrive (i.e.,
For broadcast disks (M=number of minor cycles), D is greater than F due to frame duplication in the broadcast
cycle. The access time and the tune-in time on different disks i may be different. We denote the average access
probability, the access time, and the tune-in time for frames on disks i as P i , Access i , and Tune i , respectively.
For disk i with frequency f i , the expected number of frames scanned before the arrival of the desired frames, C ,
is given by Theorem 1. Therefore, the estimates for the average access time and tune-in time are:
The study for a non-clustered broadcast cycle is especially important in multi-attribute indexing where cycle
can be clustered on at most one attribute, while query requests on other attributes get a reply via indexes built on
the non-clustered broadcast cycle. For a non-clustered broadcast cycle, M is greater than 1 and the client needs to
scan the entire broadcast to retrieve all the desired frames.
to 200

Table

4. Parameters of the cost models

Table

4 lists the parameter values used in the comparisons. Both access time and tune-in time are measured in
number of packets and are compared with respect to the number of distinct frames in a broadcast cycle which is
varied from 10 3 to 10 6 . We made the following assumption in the comparisons: a frame has capacity
packets and a tree node takes up packets which can contain search keys and pointers, the size of
a packet is are grouped together in an integrated signature, the index tree
is balanced (all leaves are on the same level) and each node has the same number of children. In order to make
comparison, the sparse tree levels t of the hybrid method is set to the same as the replicated tree levels in the index
tree method, which can be obtained via Equation (1).
A broadcast cycle with selectivity S ? 1 is logically equal to a broadcast cycle with selectivity and the
data frame size S times of the original broadcast cycle. Thus, in this paper, we only explore the case where the
query selectivity S is 1.
For broadcast disks, we assume that three disks are adopted (i.e., 3). The sizes of fast, medium, and slow
disk are, respectively, 1=10, 1=2:5, and 1=2 of the total number of frames and the relative spin speeds are 3, 2,
and 1. The aggregate client access probability for each disk is the same (i.e., P
each disk, all data frames have equal average access probability. Therefore, the average access probability for each
data frame is inversely proportional to the size of the disk where the data frame is located. For a non-clustered
broadcast cycle, we vary the scattering factor M (i.e., from 1 to 200) to examine its impact on the performance of
the index methods.
In what follows, we will first evaluate the access time, the tune-in time, and the indexing efficiency of index
methods for clustered broadcast cycle and then for non-clustered broadcast cycle. For the clustered broadcast
cycle, we consider both of the broadcast disks and flat broadcast as broadcast scheduling policies while for the
non-clustered broadcast cycle, we only consider the flat broadcast scheduling.
5.1 The Clustered Broadcast Cycle
In this section we study the access time and the tune-in time of the index methods for a clustered broadcast
cycle.

Figures

4 and 5 depict the access time and the tune-in time comparisons, where the y coordinate is in
logarithmic scale and the access time is the overhead with respect to non-index for broadcast disks scheduling.
First we consider the access time in Figure 4. The curves representing the access time overhead of the hybrid,
the signature, and the non-index methods (denoted as hybrid, sig, and non, respectively) overlap each other for
1.0 2.0 4.0 6.0 8.0 10.0
Access
Time
Number of Frames in Cycle (x 1e+05 Frames)
tree
tree BD sig
sig BD
hybrid
hybrid BD
non

Figure

4. Access Time Overhead Comparisons for Clustered Cycle
flat broadcast. Generally, amongst all broadcast scheduling and indexing methods, the non-index method with
broadcast disks gives the shortest access time which is proportional to the size of a broadcast cycle. For any
particular indexing methods, the access time for broadcast disks (denoted with BD in the figures) is always better
than that for flat broadcast because of the skewed client access pattern.
When we consider flat broadcast only, the access time for the signature and the hybrid methods is similar to
the non-index method as indicated by the overlapping curves in Figure 4 while the access time for the index tree
method gives an obviously worse access time. Compared with the non-index method, the index overhead for the
index methods (especially the signature and the hybrid methods) does not deteriorate the access time much for a
clustered broadcast cycle.
In the broadcast disks method, the broadcast cycle is longer than that scheduled in flat broadcast. Since the
longer the broadcast cycle, the higher the index overhead, all three index methods give a much worse access time
than the non-index BD. The signature method performs better than the hybrid and the tree methods. Since the
index tree is replicated in every minor cycle, its index overhead for broadcast disks is the highest. Thus, the
difference between the index tree method and the other two index methods for broadcast disks is much larger than
that for flat broadcast.
Next, we consider the tune-in time of the index methods. Figure 5 shows that the curves representing the index
tree method (denoted as tree) and the hybrid method are overlapping for both broadcast disks and flat broadcast.
The non-index methods give much worse results than the index methods. This suggests that indexing can improve
client tune-in time considerably. If we focus on the index methods only, the index tree method gives the best tune-in
time and the signature method has the worst tune-in time. Broadcast disks can also improve the tune-in time of
the index methods. As shown in Figure 5, the broadcast disks improve the tune-in time of the index methods and
such improvement for the non-index and the signature methods is more than for others.
In order to investigate the relationship between the tune-in time and the access time, we demonstrate in Figure
6 the indexing efficiency of indexing methods for various sizes of a broadcast cycle. The tune-in time saved and
the access time overhead is calculated with respect to the non-index method for broadcast disks and flat broadcast.
Intuitively, the larger the amount of tune-in time saved per unit access time overhead, the better the index methods.
We can observe that the amount of tune-in time saved per unit of access time overhead increases as the number of
frames in a cycle increases. The figure tells us that the signature method can give the largest amount of tune-in
time saved per unit of access time overhead and the index tree method gives the least amount of saving which is
much less than the other two methods. Indexing broadcast disks results in less amount of tune-in time saved than
1.0 2.0 4.0 6.0 8.0 10.0
Tune-in
Time
Number of Frames in Cycle (x 1e+05 Frames)
tree
tree BD sig
sig BD
hybrid
hybrid BD
non
non BD

Figure

5. Tune-in Time Comparisons for Clustered Cycle1010001.0 2.0 4.0 6.0 8.0 10.0
Indexing
Efficiency
Number of Frames in Cycle (x 1e+05 Frames)
tree
tree BD
sig
sig BD
hybrid
hybrid BD

Figure

6. Indexing Efficiency for Clustered Cycle
the indexing flat broadcast.
In conclusion, when a broadcast cycle is clustered by attributes, the hybrid scheme is the best when the access
time, the tune-in time, and indexing efficiency are considered. If only the tune-in time is considered, then the
index tree scheme shows the best performance. If we consider the indexing efficiency, then the signature is the
most efficient index method. Broadcast disks approach can improve both the access time and the tune-in time
when the client access patterns are skewed, although the improvement in the tune-in time is not as significant as
that in the access time.
5.2 The Non-Clustered Broadcast Cycle
In this section, we investigate the index methods for a non-clustered broadcast cycle (i.e., M ? 1). To examine
the influence of M on the system performance, we fix the number of frames in a cycle to 10 5 and vary M from
1 to 200. The access time overhead is obtained with respect to the non-index method. Figures 7 and 8 illustrate
the results. As expected, the scattering factor has great impact on the access time of the index tree method. Since
there is an index tree corresponding to every meta segment, as M is increased, the index tree overhead increases
Access
Time
Scattering Factor in Broadcast Cycle with 1e+05 Frames
index tree
signature hybrid

Figure

7. Access Time Overhead vs Scattering Factor48121620
Tune-in
Time
Scattering Factor in Broadcast Cycle with 1e+05 Frames
tree sig
hybrid

Figure

8. Tune-in Time vs Scattering Factor
rapidly. For the hybrid method, although there is a sparse index tree for each meta segment, the sparse index tree
overhead is very small and as M increases, the initial probe time for index tree node decreases. Therefore, M has
little influence on the access time in the hybrid method. As shown in Figure 8, the tune-in time of the index tree
and the hybrid methods goes up quickly as M is increased, while the tune-in time of the signature index method
remains the same. Since both the index tree and the hybrid methods need to probe each meta segment for the
possible arrival of the desired frames, the major advantage of the index tree and the hybrid methods, namely, short
tune-in time, disappears when M is greater than 33. However, there is no impact on the signature method for
both the access time and tune-in time when the scattering factor changes. This suggests that the index tree and the
hybrid methods are not applicable to a broadcast cycle with a large scattering factor.
Similar to the previous section, Figure 9 depicts the indexing efficiency with respect to different scattering
factors in a broadcast cycle. The tune-in time saved for the index tree is very low while the tune-in time saved for
the signature method is the highest.
Finally, we use the same parameter settings as in the clustered broadcast cycle case, but we assume that the
broadcast cycle is non-clustered with a scattering factor set to 100 (refer to Figures 10 and 11). The access time
Indexing
Efficiency
Scattering Factor in Broadcast Cycle with 1e+05 Frames
tree
sig
hybrid

Figure

9. Indexing Efficiency vs Scattering Factor1000001e+071e+091.0 2.0 4.0 6.0 8.0 10.0
Access
Time
Number of Frames in Cycle (x 1e+05 Frames)
tree
sig
hybrid

Figure

10. Access Time Comparisons for Non-Clustered Cycle
overhead is obtained with respect to that of the non-index. Similar to the clustered broadcast cycle, the access time
of the index tree method is much worse than that of the other two index methods. The signature method has the
closest access time to the non-index method. Since we assume that M is fixed at 100 for any broadcast length and
there is an index overhead for each meta segment, unlike the clustered cycle, the tune-in time of the index tree and
hybrid methods is not always better than that of the signature method. That is, for small broadcast cycle (i.e., less
than methods have the best tune-in time among the three methods. When the length of a
cycle increases, the tune-in time of the signature method increases quickly due to false drops and becomes worse
than the other methods again. As in the case of clustered cycle, the tune-in time of the hybrid method is always a
little bit worse than that of the index tree method. In Figure 12, we illustrate the indexing efficiency for various
cycle lengths. All index methods display similar interrelation to that in the case of clustered cycle.
For both clustered and non-clustered broadcast cycle, we observe that the tune-in time of the signature schemes
is proportional to the length of the broadcast cycle, while the other two methods have the tune-in time independent
of the length of the broadcast cycle. The reason is that the size of the index tree can be adjusted automatically
according to the length of the broadcast cycle F and the height of the index tree h increases very slowly (n h - F )
2.0 4.0 6.0 8.0 10.0
Tune-in
Time
Number of Frames in Cycle (x 1e+05 Frames)
tree sig
hybrid

Figure

11. Tune-in Time Comparisons for Non-Clustered Cycle110010000
1.0 2.0 4.0 6.0 8.0 10.0
Indexing
Efficiency
Number of Frames in Cycle (x 1e+05 Frames)
tree
sig
hybrid

Figure

12. Indexing Efficiency for Non-Clustered Cycle
and only h affects the tune-in time of the clients.
6 Related Works
The basic idea of constructing index on broadcast data was investigated by a number of projects [IVB94b,
IVB96, LL96b]. To reduce the power consumption of clients, [IVB94a, IVB96] proposed two methods, (1; d)
indexing and distributed indexing. In (1; d) indexing method, the index tree is broadcast d times during one
broadcast cycle. The full index tree is broadcast following every 1
d fraction of the file. All frames have an offset
to the beginning of the next index segment. The first frames of each index segment has a tuple, with the first field
as the attribute value of the record that was broadcast last and the second field as the offset to the beginning of the
next cycle. This is to guide the clients that have missed the required frames in the current cycle and have to tune
to the next cycle. Notice that there is no need to replicate the entire index between successive data segments, the
distributed indexing techniques was developed, it interleaves and replicates index tree with data, in the sence that
most frequently access index part (the upper level of the index tree) is replicated the number of times equal to the
number of children.
The project in [IVB94b] discussed the hashing schemes and a flexible indexing method for organizing broadcast
cycle. In the hashing schemes, instead of broadcasting a separate directory with the information frames, the
hashing parameters are included in the frames. Each frame has two parts: the data part and the control part. The
control part is the "investment" which helps guide searches to minimize the access time and the tune-in time. It
consists of a hash function and a shift function. The shift function is necessary since most often the hash function
is not perfect. In such a case there can be collisions and the colliding frames are stored immediately following the
frame assigned to them by the hashing function. The flexible indexing method first sorts the data in ascending (or
descending) order and then divides the cycle into p segments numbered 1 through p. The first frame in each of the
data segments contains a control part consisting of the control index. The control index is a binary index which ,
for a given key K , helps to locate the frame which contains that key. In this way, we can reduce the tune-in time.
The parameter p makes the indexing method flexible since depending on its value we can either get a very good
tune-in time or a very good access time.
[LL96b] investigated the signature techniques for flat data broadcasting. Three signature methods, simple
signature, integrated signature, and multi-level signature, were proposed and their cost models for the access time
and the tune-in time were given. Based on the models, they made comparisons for the performance of different
signature methods. Work in [LL96a] explored the influencies of caching signatures in the client side to the system
performance. Four caching strategies were developed and the tune-in time and the access time were compared.
With reasonable access time delay, all the caching strategies help in reducing the tune-in time for the two-level
signature scheme.
All those index methods can reduce the power consumption to some extent with a certain amount of access
overhead. However, the index techniques developed previously didn't consider the characteristics of skewed access
patterns.
Recent work in [CYW97] developed an imbalanced index tree on broadcast data. The index tree is constructed
in accordance with data access frequencies in such a way that the expected cost of index probes for data access is
minimized. In contrast to [IVB96], the variant fanouts for index nodes was also exploited. Since the cost of index
probes takes up small part of the overall cost, such imbalanced index tree gives only limited improvement.
To reduce the overall access time, as mentioned in the introduction section, Broadcast disks [ZFA94, AAFZ95]
is an efficient technique which can improve the overall access time for skewed data access patterns. In their later
work, [AFZ96b] studied the opportunistic prefetching from broadcast disks by the client, [AFZ96a] considered
the case when update presents in broadcast disks, and [AFZ97] studied the performance of a hybrid data delivery
in broadcast disks environments, where clients can retrieve their desired data items either by monitoring broadcast
channel (push-based) or by issuing explicit pull request to server (pull-based). These studies indicate that data
prefetching and hybrid data delivery with caching can significantly improve performance over pure pull-based
caching and pure push-based caching. While updates have no great influence on the system performance. [HV97]
further developed an O(log(n)) time-complexity scheduling algorithm which can determines the broadcast frequency
of each data item according to data access patterns for both single and multiple broadcast channels. In their
models, the length of data items is not necessarily of the same. However, no study explores index on broadcast
disks.
7 Conclusion and Future Work
In a mobile environment, power conservation of the mobile clients is a critical issue to be addressed. An efficient
power conservative indexing method should introduce low access time overhead, consume low tune-in time, and
produce high indexing efficiency. Moreover, an ideal index method should perform well under both clustered and
non-clustered broadcast cycle, with different broadcast scheduling policies, such as flat broadcast and broadcast
disks.
In this paper, we evaluate the performance of power conservative indexing methods based on index tree and
signature techniques. Combining strengths of the signature and the index tree techniques, a hybrid indexing
method is developed in this paper. This method has the advantages of both the index tree method and the signature
method and has a better performance than the index tree method. A variant of the hybrid indexing method has been
demonstrated to be the best choice for multiple attributes indexing organization in wireless broadcast environments
[HLL98b].
Our evaluation of the indexing methods takes into consideration the clustering and scheduling factors which may
be employeed in wireless data broadcast. Access time, tune-in time, and indexing efficiency are the evaluation
criteria for our comparisons. We develop cost models for access time and tune-in time of the three indexing
methods and produce numerical comparisons under various broadcast organization based on the formulae.
Through our comparisons for both clustered and non-clustered data broadcast cycles, we find that the index
tree method has low tune-in time only for the clustered broadcast cycles or the non-clustered broadcast cycles
with low scattering factor. The index tree always produces high access time overhead. For a broadcast cycle with
high scattering factor, the signature method is the best choice. Since the signature method needs further filtering
to determine whether a data item really satisfies a query, the tune-in time for signature methods may be high.
However, the variations of data organization for the broadcast channels have very limited impact on performance
of the signature method. Moreover, the access time overhead is low. The hybrid method has the advantages of
both the index tree method and the signature method. It performs well for clustered broadcast cycles or non-clustered
cycles with low scattering factor (i.e., low tune-in time similar to the index tree method and low access
time overhead similar to the signature method). If we only consider the indexing efficiency, the signature method
has the best performance for various broadcast organization.
Finally, through our comparisons for flat broadcast and broadcast disks, we observe that broadcast disks can
reduce the access time for any index methods and the tune-in time for the signature and non-index methods.
As a related study [HLL98b], we have studied the performance of multi-attribute index methods for wireless
broadcast channels. Since the access time and the tune-in time of the index methods may be different for queries
based on different attributes, We have estimated the average access time and tune-in time of the client according
to the queries arrival rate for each attribute.
In the future, we plan to incorporate the index schemes with data caching algorithms to achieve an improved
system performance and obtain a better understanding of the wireless broadcast systems.


Appendix


Broadcast disks were proposed to improve data access efficiency [AAFZ95]. The idea is to divide data frames
to be broadcast into broadcast disks based on their access frequency and then interleave data frames on these disks
into an information stream for broadcast. This imitates multiple disks each spinning at a different speed. The
relative speeds of disks are differentiated by the number of broadcast units 11 on the disks. Data located on a disk
with less broadcast units is scheduled for broadcast more frequently than a disk with many broadcast units. The
relative speeds and broadcast frequency of broadcast disks inversely proportional to the number of broadcast units
on those disks. Thus, data frames with higher demands usually are placed on a higher speed broadcast disk.
The broadcast units on broadcast disks, called chunks, have equal size 12 . The broadcast schedule is generated
by broadcasting a chunk from each disk and cycling through all the chunks sequentially over all the disks. A minor
cycle is defined as a sub-cycle consisting of one chunk from each disk. Consequently, chunks in a minor cycle are
repeated only once and the number of minor cycles in the broadcast equals the least common multiple (LCM) of
the relative frequency.
Unlike traditional disks where the number and the capacity of the disks are fixed by hardware, The broadcast
disks has flexibility in deciding the number, the size, the relative spinning speed, and the data frame placement of
broadcast unit may consist of one or many data frames, e.g., a cluster of data frames with the same attribute value.
In real implementation, chunks can be replaced by variable-sized data frames or a group of data frames.
each disk. Broadcast schedules can be programmed once the data frames, relative speed of each disk, the number
of data frames placed on the disks, and the size of each disk are determined.
c
Chunks
Data Set
Fast
Disks Slow
COLD
a
a
a b
f
A Broadcast Cycle a g
Minor Cycle
b d a c e a b f a c

Figure

13. An Example of a Seven-page, Three-disk Broadcast Program

Figure

13 illustrates an example where seven chunks are divided into three ranges of similar average access
probabilities [AAFZ95]. Each of which will be assigned to a separate disk in the broadcast. In the figure, chunk,
refers to the j th chunk of disk i. Chunks in the first disk are to be broadcast twice as frequently as chunks in
the second one and four times as often as those of the slowest disk.
However, the reason that multi-disk broadcast can achieve better performance than a random broadcast schedule
and the expected access time for retrieving data frames from the broadcast disks were not given in [AAFZ95]. In
the following, we prove Theorem 1 used in the paper.
PROOF: The data frame d is scheduled to broadcast f i times in a cycle, the length of the broadcast (in number of
frames) is D:
Assuming the inter-arrival time for each broadcast of d is D is the number of frames
between two consecutive copies of d. k is the number of frames between the frame where clients begin monitoring
channels and the next copy of d. Therefore, the expected access time for d can be estimated as:D \Delta
(D
will have a minimum
value. Note that D is the number of frames from one broadcast of d to the next broadcast of d. If all the f i
broadcasts of d are equally spaced, then we have As a result, the minimum expected number
of data frames retrieved before the desired one arrives for data on disk with frequency f i , denoted as C , can be
expressed as follows.


--R

Broadcast disks: Data management for asymmetric communications environments.
Dissemination updates on broadcast disks.
Prefetching from a broadcast disk.
Balancing push and pull for data broadcast.
Sleepers and workaholics: Caching strategies for mobile environments.
Indexed sequential data broadcasting in wireless mobile comput- ing
A comparison of indexing methods for data broadcast on the air.

Optimal channel allocation for data dissemination in mobile computing environments.
Efficient algorithms for a scheduling single and multiple channel data broadcast.
Energy efficiency indexing on air.
Power efficiency filtering of data on air.
Data on the air - organization and access
On signature caching of wireless broadcast and filtering services.
Using signature techniques for information filtering in wireless and mobile environments.
Adaptive data broadcast in hybrid networks.

Scheduling data broadcast in asymmetric communication environ- ments
Are disks in the air' just pie in the sky?
--TR
Power efficient filtering of data on air
Sleepers and workaholics
Energy efficient indexing on air
Broadcast disks
Balancing push and pull for data broadcast
Efficient indexing for broadcast based wireless systems
Signature caching techniques for information filtering in mobile enviroments
A study on channel allocation for data dissemination in mobile computing environments
Data on Air
Prefetching from Broadcast Disks
Disseminating Updates on Broadcast Disks
Adaptive Data Broadcast in Hybrid Networks
A Comparision of Indexing Methods for Data Broadcast on the Air
Indexed Sequential Data Broadcasting in Wireless Mobile Computing
Optimal Channel Allocation for Data Dissemination in Mobile Computing Environments
Efficient Algorithms for Scheduling Single and Multiple Channel Data Broadcast
Scheduling Data Broadcast in Asymmetric Communication Environments

--CTR
Quinglong Hu , Wang-Chien Lee , Dik Lun Lee, Indexing techniques for wireless data broadcast under data clustering and scheduling, Proceedings of the eighth international conference on Information and knowledge management, p.351-358, November 02-06, 1999, Kansas City, Missouri, United States
Qingzhao Tan , Wang-Chien Lee , Baihua Zheng , Peng Liu , Dik Lun Lee, Balancing performance and confidentiality in air index, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Jianting Zhang , Le Gruenwald, Prioritized sequencing for efficient query on broadcast geographical information in mobile-computing, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA
Qinglong Hu , Dik Lun Lee , Wang-Chien Lee, Performance evaluation of a wireless hierarchical data dissemination system, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.163-173, August 15-19, 1999, Seattle, Washington, United States
Jianliang Xu , Wang-Chien Lee , Xueyan Tang, Exponential index: a parameterized distributed indexing scheme for data on air, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA
KwangJin Park , MoonBae Song , Chong-Sun Hwang, Adaptive data dissemination schemes for location-aware mobile services, Journal of Systems and Software, v.79 n.5, p.674-688, May 2006
Jianting Zhang , Le Gruenwald, Efficient placement of geographical data over broadcast channel for spatial range query under quadratic cost model, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA
Kwang-Jin Park , Moon-Bae Song , Chong-Sun Hwang, Broadcast-based spatial queries, Journal of Computer Science and Technology, v.20 n.6, p.811-821, November 2005
Wen-Chih Peng , Ming-Syan Chen, Efficient channel allocation tree generation for data broadcasting in a mobile computing environment, Wireless Networks, v.9 n.2, p.117-129, March
Jianliang Xu , Dik-Lun Lee , Qinglong Hu , Wang-Chien Lee, Data broadcast, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
Sunil Prabhakar , Yuni Xia , Dmitri V. Kalashnikov , Walid G. Aref , Susanne E. Hambrusch, Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects, IEEE Transactions on Computers, v.51 n.10, p.1124-1140, October 2002
Chi-Yin Chow , Hong Leong , Alvin T. S. Chan, Distributed group-based cooperative caching in a mobile broadcast environment, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus
index technique;wireless data broadcast;power conservation;signature method