Location-Based Information Access in Pervasive Computing Environments

Project Overview

Location-based services (LBSs) have emerged as one of the killer applications for mobile computing and wireless data services. These LBSs are critical to public safety, transportation, emergency response, and disaster management, while providing great market values to companies and industries. Efficient processing of location-based spatial queries (LBSQs), which refer to a set of spatial queries that retrieve information based on the current locations of mobile users, is crucial to the provision of LBSs. Due to the unrestricted mobility of users in the pervasive computing environments, the LBSQs is distinct from the traditional spatial queries. For example, a traveler may issue a query "find me the three nearest restaurants". The answer to this query is dependent on the location where the traveler receives the query results.

The goal of this research project is to investigate new ways of indexing and caching spatial data to support processing of LBSQs in pervasive computing and to validate the methods obtained from this project via analysis, implementation, and simulations. The emphasis of the project is on methods that are particularly suitable for wireless data broadcast. A list of LBSQs, including point query, planar point query, window query, nearest neighbor (NN) search, k nearest neighbor (KNN) search, continuous nearest neighbor (CNN) search, spatial join, and complex queries is studied in this project. Fundamental issues faced by all the spatial indexes and caching schemes (such as large index search space, large index size, linear streaming property of wireless data broadcast, continuous movement and requests of mobile users, and cache replacement/invalidation) are tackled. Query processing algorithms and new mobile caching mechanisms have been developed in support of various spatial queries for mobile users.

Several efficient indexes have been developed for location-based query processing. A new index structure for planar point queries, called D-tree, is developed based on the divisions that form the boundaries of the regions [ICDE'03, TKDE'04b]. Another  new index method, called the grid-partition index, has been developed based on the nice properties of Voronoi Diagram to efficiently support NN search in both on-demand access and periodic broadcast modes of mobile computing [EDBT'04, VLDBJ]. While the above studies are focused on specific queries, two new spatial indexes, namely, Hilbert Curve Index (HCI) and Distributed Spatial Index (DSI), are developed to support multiple LBSQs at the same time. HCI is the first general-purpose spatial index for wireless data broadcast [PerCom'03, Mobiquitous'04, WINET'04a]. On the other hand, DSI is based on a linear yet fully distributed structure that facilitates multiple search paths to be naturally mixed together by sharing links [ICDCS'05]. This index has an excellent performance on general LBSQs and is very resilient in error-prone wireless communication environments. Most recently, Nearest Surrounder (NS) search, a new type of spatial query which searches the nearest surrounding spatial objects around a query point, has been identified and studied. In this study, angle-based bounding properties (in addition to the conventional consideration of the distance-bound properties) are exploited to develop new algorithms for NS search [ICDE'06].

A LBSQ issued by a mobile user may be processed at the server and the result is returned to the user via a wireless connection. However, this returned result may become invalid when a user changes location. To address this problem, a solution is to return along with the query result some auxiliary information that describe a region where the result remains valid. Valid scopes, which can be seen as implicit properties associated with a query result. is an important new concept we developed. Valid scope has been naturally employed in our research to develop mobile caching mechanisms for location-based services [WINET'04b]. We are continuing to explore this concept for mobile caching. More recently, a new mobile caching scheme, called proactive cache, has been developed to cache spatial objects and an R-tree in client memory to support general LBSQs [ICDE'05].

An overview of the research challenges and issues addressed in this project has been published in the IEEE Pervasive Computing Magazine [PVC] and also presented as a tutorial in IEEE ICDE’04.

This research is supported in part by the National Science Foundation under Grant No. IIS-0328881.

Current Members

Graduated Members

Collaborators

Publication

1. C.K. Lee, W.-C. Lee, and H.V. Leung, Nearest Surrounder Search, IEEE International Conference on Data Engineering (ICDE’06), Atlanta, GA, April 2006, to appear. [pdf]

2. B. Zheng, J. Xu, W,-C. Lee, D.L. Lee, Grid-Partition Index: A Hybrid Method for Nearest-Neighbor Queries in Wireless Location-Based Services, Very Large Data Base Journal (VLDBJ), to appear. [pdf]

3. W.-C. Lee and B. Zheng, DSI: A Fully Distributed Spatial Index for Wireless Data Broadcast, IEEE International Conference on Distributed Computing Systems (ICDCS’05), Columbus, OH, June, 2005, pp. 349-358. [pdf]

4. B. Liu, W.-C. Lee, and D.L. Lee, Distributed Caching of Multi-dimensional Data in Mobile Environments, the Sixth International Conference on Mobile Data Management (MDM’05), Ayia Napa, Cyprus, May 9-13, 2005, pp. 229-233. [pdf]

5. H. Hu, J. Xu, W.S. Wong, B. Zheng, D.L. Lee, and W.-C. Lee, Proactive Caching for Spatial Queries in Mobile Environments, IEEE International Conference on Data Engineering (ICDE’05), Tokyo, April, 2005, pp. 403-414. [pdf]

6. W.-C. Lee and B. Zheng, A Fully Distributed Spatial Index for Wireless Data Broadcast, IEEE International Conference on Data Engineering (ICDE’05), Tokyo, April, 2005, pp. 417-418. (Poster). [pdf]

7. J. Xu, B. Zheng, W,-C. Lee, D.L. Lee, The D-tree: An Index Structure for Planar Point Queries in Location-Based Wireless Services, IEEE Transaction on Knowledge and Data Engineering (TKDE), Volume 16, No. 12, December, 2004, pp. 1526-1542. [pdf]

8. B. Zheng, W.-C. Lee, and D.L. Lee, Spatial Queries in Wireless Broadcast Systems, ACM Wireless Networks Journal (WINET), Volume 10, Issue 6. November 2004, pp. 723-736. [pdf]

9. B. Zheng, W.-C. Lee, and D.L. Lee, On Semantic Caching and Query Scheduling for Mobile Nearest Neighbor Search, ACM Wireless Networks Journal (WINET), Volume 10, Issue 6. November 2004, pp. 653-664. [pdf]

10. B. Zheng, W.-C. Lee, and D.L. Lee, Search Continuous Nearest Neighbors on the Air, the First International Conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous'04), Boston, MA, August 22-26, 2004, pp. 236-245. [pdf]

11. B. Zheng, J. Xu, W.-C. Lee, and D.L. Lee, Energy-Efficient Air Indexes for Location-Based Wireless Services, International Conference on Extending Database Technology (EDBT’04), 2004, pp. 48-66. [pdf]

12. B. Zheng, W.-C. Lee, and D.L. Lee, Spatial Index on Air, IEEE International Conference on Pervasive Computing and Communications (PerCom’03), Dallas-Fort Worth, Texas, March 23-26, 2003 pp. 297-304. [pdf]

13. B. Zheng, W.-C. Lee, and D.L. Lee, Selecting the Best Valid Scopes for Wireless Dissemination of Location-dependent Data, ACM Symposium on Applied Computing (SAC’03), Melbourne, Florida, March 9-12, 2003, pp. 860-865. [pdf]

14. J. Xu, B. Zheng, W.-C. Lee, and D.L. Lee, Energy Efficient Index for Querying Location-Dependent Data in Mobile Broadcast Environments, International Conference on Data Engineering (ICDE’03), Bangalore, India, March 5 - March 8, 2003, pp. 239-250. [pdf]

15. B. Zheng, W.-C. Lee, and D.L. Lee, Search K Nearest Neighbors on Air, International Conference on Mobile Data Management (MDM'03), Australia, January 21-24, 2003, pp. 181-195. [pdf]

16. D.L. Lee, W.-C. Lee, J. Xu, and B. Zheng, Data Management in Location-Dependent Information Services: Challenges and Issues, IEEE Pervasive Computing, Vol. 1, No. 3, July-Sept. 2002, pp. 65-72. [pdf]