Article ID Journal Published Year Pages File Type
397611 Information Systems 2006 17 Pages PDF
Abstract

The continuous broadcast of data together with an index structure is an effective way of disseminating data in a wireless, mobile environment. The availability of an index allows a reduction in the tuning time and thus leads to lower power consumption for a mobile client. This paper considers scheduling index trees in multiple channel environments in which a mobile client can tune into a specified channel at one time instance. Let T be an n-node index tree of height h representing multi-dimensional index structure to be broadcast in a c  -channel environment. We describe two algorithms generating broadcast schedules that differ in the worst-case performance experienced by a client executing a general query. A general query is a query which results in an arbitrary traversal of the index tree, compared to a simple query in which a single path is traversed. Our first algorithm schedules any tree using minimum cycle length and it executes a simple query within one cycle. However, a general query may require O(hc)O(hc) cycles and thus result in a high latency. The second algorithm generates a schedule of minimum cycle length on which a general query takes at most O(c)O(c) cycles. For some queries this is the best possible latency.

Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
, , ,