Index allocation for data broadcasting

Details Index allocation for data broadcasting Index allocation for data broadcasting

1995-05-08

2002-12-10

Dinh, Dung C. (Department: 2153)

Electrical computers and digital processing systems: multicomput

Computer-to-computer protocol implementing

Computer-to-computer data streaming

C455S003010

Reexamination Certificate

active

06493762

ABSTRACT:

I. BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to broadcasting data in a wireless mobile computing environment.
2. Related Art
Mobile computing, referring to the activity of using personal digital assistants, such as palmtops and notebook computers, to access a large number of databases via wireless networks, is an emerging technology. A significant amount of research effort has been directed towards exploring various aspects of mobile computing, such as energy saving, cache management, query processing and data allocation. Applications such as using palmtops to access airline schedules, stock activities, traffic conditions and weather information on the road are expected to become increasingly popular. It is noted, however, that several mobile computers, such as desktops and palmtops, use small batteries for their operations and are not directly connected to any power source. As a result, energy saving is a key issue to resolve before one can anticipate an even wider acceptance of mobile computers.
In general, a mobile server is expected to concurrently serve hundreds or even thousands of clients. In large part, because the cost of broadcasting is independent of the number of users, periodic broadcasting is the prevalent method for information dissemination in a wireless communication environment. When a palmtop is actively listening to a channel, its CPU is in an active mode to examine data packets so as to determine if they match the predefined patterns. Such CPU operations for data examination consume much more power than those for simply receiving data. Therefore, to achieve energy savings it is highly desirable to let the palmtop stay in the doze mode most of the time and only enter the active mode when it is necessary. As a consequence, it is advantageous to use indexed data organization to broadcast data over wireless channels so that those mobile units can be guided to the data of interest efficiently and only need to be actively listening to the broadcasting channel when the relevant information (indexes or data) is present. The structure of an index tree determines the index probing scenario for data access under such an indexed broadcasting.
A conventional index tree is given in
FIG. 1
a
, and its corresponding broadcasting sequence is shown in
FIG. 1
b
. Suppose that record R
5
is the record to be accessed. Then, after being routed to the root index, I, the request will probe I and a
2
, and then reach R
5
. Clearly, using this index tree, a request to any record will take two index probes. Note that the number of index probes is proportional to the amount of time that a mobile unit has to stay in the active mode.
Typically, conventional wireless servers provide a symmetric balanced index tree with essentially the same fanouts for all index nodes. One possible reason for this is that in a conventional file system (one that is not used in conjunction with wireless mobile computing) the cost of executing an index probe for data access is almost negligible as compared to other CPU and I/O operations. Thus little overall performance improvement is obtained by minimizing the number of index probes. Such a cost model, however, does not hold in the context of wireless mobile computing, in which the cost for a mobile unit to listen to the indexed broadcasting message is one of the major sources for power consumption. Hence, reducing the average number of index probes will result in a lower power consumption.
It is noted that in most databases the access frequencies of different data records are usually different from one another. This phenomenon is termed data access skew.
II. SUMMARY OF THE INVENTION
In light of the above, the present invention provides a system and method for broadcasting data in accordance with predicted usage. In accordance with the method, the predicted usage of data records within a given set is determined. The broacast order is then determined based on the predicted usage and the data records are broadcast in the order determined.
In the preferred embodiments, two kinds of systems are considered: one in which variant index fanouts are not allowed (i.e., fixed fanout has to be used), and the other in which variant index fanouts are allowed. For the case of fixed index fanouts, a first method (method 1) for the optimal index tree construction that minimizes the average cost of index probes is provided. For the case of variant index fanouts, a second method (method 2) for building index trees with variant fanouts is provided.
The first method uses access frequencies of data records to build a fixed fanout index tree. Exploiting data access skew, the index tree built by the method could be imbalanced. Thus, in cases where variant fanouts are allowed the second method is preferred. In the second method, the number of fanouts of each index is determined as a function of the access frequencies of those nodes (data or indexes) that the index node points to.
After an index tree is built, the mobile unit can locate the data of interest, according to the index tree, with the minimal probing cost. It is noted that the average cost of index probes can be significantly reduced not only by employing an imbalanced index tree that is designed in accordance with data access skew, but also by exploiting variant fanouts for index nodes.
These, and other features and advantages of this invention will become apparent from the following detailed description of the invention taken in conjunction with the accompanying drawings.


REFERENCES:
patent: 4467411 (1984-08-01), Fry et al.
patent: 5204958 (1993-04-01), Cheng et al.
patent: 5479657 (1995-12-01), Toyonaga et al.
patent: 63-239540 (1988-05-01), None
Gidlow A.C. “Data Services on PCN,” IEEE Collq (1995).*
Berman et al. “Information/Communication and Dispatching Strategies for Networks with Mobile Servers,” IEEE Transactions on System, Man and Cybernetics, Jan. 1990.

Affiliated with

Also associated with

Rating

Index allocation for data broadcasting does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Index allocation for data broadcasting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Index allocation for data broadcasting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2924740