Mobile Caching for Location-Based Services

Location-based services (LBS) are services that answer queries based on the locations with which the queries are associate; normally the locations where the queries are issued. With a variety of promising applications, such as local information access (e.g., traffic reports, news, and navigation maps) and nearest neighbor queries (e.g., finding the nearest restaurants) (Barbara, 1999; Ren & Dunham, 2000; D. L. Lee, Lee, Xu, & Zheng, 2002; W. C. Lee, Xu, & Zheng, 2004), LBS is emerging as an integral part of daily life. The greatest potential of LBS is met in a mobile computing environment, where users enjoy unrestricted mobility and ubiquitous information access. For example, a traveler could issue a query like “Find the nearest hotel with a room rate below $100" from a wireless portable device in the middle of a journey. To answer such a query, however, three major challenges have to be overcome: • Constrained Mobile Environments: Users in a mobile environment suffer from various constraints, such as scarce bandwidth, low-quality communication, frequent network disconnections, and limited local resources. These constraints pose a great challenge for the provision of LBS to mobile users. • Spatial Data: In LBS, the answers to a query associated with different locations may be different. That is, query results are dependent on spatial properties of queries. For a query bound with a certain query location, the query result should be relevant to the query as well as valid for the bound location. This requirement adds additional complexity to traditional data management techniques such as data placement, indexing, and query processing (D. L. Lee, 2002). • User Movement: The fact that a mobile user may change its location makes some tasks in LBS, such as query scheduling and cache management, particularly tough. For example, suppose that a mobile user issues a query “Find the nearest restaurant” at location A. If the query is not scheduled timely enough on the server, the user has moved to location B when he or she gets the answer R. However, R is no longer the nearest restaurant at location B. Caching has been a commonly used technique for improving data access performance in a mobile computing environment (Acharya, Alonso, Franklin, & Zdonik, 1995). There are several advantages for caching data on mobile clients: • It improves data access latency since a portion of queries, if not all, can be satisfied locally. • It helps save energy since wireless communication is required only for cache-miss queries. • It reduces contention on the narrow-bandwidth wireless channel and off-loads workload from the server; as such, the system throughput is improved. • It improves data availability in circumstances where clients are disconnected or weakly connected because cached data can be used to answer queries. However, as discussed above, the constrains of mobile computing environments, the spatial property of location-dependent data, and the mobility of mobile users have opened up many new research problems in client caching for LBS. This chapter discusses the research issues arising from caching of location-dependent data in a mobile environment and briefly describes several state-of-the-art solutions.