MobiSys 2004: Second International Conference on Mobile Systems, Applications, and Services, June, 2004, Boston, USA
  MobiSys Home   Organizers   Invitation   Tech Session   Registration  
  Workshops   Poster/Demo/Video   Authors/Speakers   Hotel/Travel   Invitation to Student Volunteer Program  

Exponential Index: A Parameterized Distributed Indexing Scheme for Data on Air

Jianliang Xu, Hong Kong Baptist University; Wang-Chien Lee, Penn State University; Xueyan Tang, Nanyang Technological University, Singapore

Wireless data broadcast has received a lot of attention from industries and academia in recent years. Access efficiency and energy conservation are two critical performance concerns in a wireless data broadcast environment. To improve the efficiency of energy consumption on mobile devices, traditional disk-based indexing techniques such as B+-tree have been extended to index broadcast data on a wireless channel. However, existing designs are mostly based on centralized tree structures. Most of these indexing techniques are not flexible in the sense that the trade-off between access efficiency and energy conservation is not adjustable based on application specific requirements. We propose in this paper a novel parameterized index, called the exponential index, which can be tuned to optimize the access latency with the tuning time bounded by a given limit, and vice versa. The proposed index is very efficient because it facilitates replication naturally by sharing links in multiple search trees and thus minimizes storage overhead. Experimental results show that the exponential index not only achieves better performance than the state-of-the-art indexes but also enables great flexibility in trade-offs between access latency and tuning time.