Method and apparatus for indexed data broadcast

Abstract

In some embodiments, the present invention provides a method for scheduling an indexed data broadcast such that both mean access time and mean tuning time are reduced to a practical minimum. In one embodiment of such a method, data items are first scheduled for broadcast. Such data items are advantageously scheduled such that: (1) all data items to be broadcasted are equally spaced; and (2) when indexed with appropriate “indexing keys,” the indexing information can be efficiently stored and broadcasted. In one embodiment, a schedule having a mean access time about 1.5× that of the theoretical minimum is provided. The indexing information is advantageously arranged in a way that allows for efficient delivery thereof to clients to apprise them of the broadcast schedule of the data items. The indexing information is advantageously arranged in a tree structure referred to herein as an “indexing tree.” Indexing information is advantageously stored at internal nodes of the indexing tree and data items are stored at the leaf nodes of the tree. The leaf nodes comprising the scheduled data items fall within “subtrees” of the various internal nodes of the indexing tree. Information indicative of the index keys of data falling within a subtree of a given internal node is stored at that node. According to a schedule, indexing information of the internal node is broadcasted, so that a client who is “tuned in” to the broadcast is apprised of the data that will be broadcasted as a subtree of the node. If desired data is not included in the subtree, it is safe for the client to stop listening to the broadcast (i.e., “sleep”) until such time as that portion of the broadcast is completed. By advantageously providing, in addition to the indexing information, the time at which the first internal node outside of the subtree will be broadcasted, the client can set an internal alarm and sleep until the set time.