Valid scope computation for location-dependent spatial query in mobile broadcast environments

ABSTRACT

Wireless data broadcast is an efficient and scalable means to provide information access for a large population of clients in mobile environments. With Location-Based Services (LBSs) deployed upon a broadcast channel, mobile clients can collect data from the channel to answer their location-dependent spatial queries (LDSQs). Since the results of LDSQs would become invalid when mobile client moves to new locations, the knowledge of valid scopes for LDSQ results is necessary to assist clients to determine if their previous LDSQ results can be reused after they moved. This effectively improves query response time and client energy consumption. In this paper, we devise efficient algorithms to determine valid scopes for various LDSQs including range, window and nearest neighbor queries along with LDSQ processing over a broadcast channel. We conduct an extensive set of experiments to evaluate the performance of our proposed algorithms. While the proposed valid scope algorithm incurs only little extra processing overhead, unnecessary LDSQ reevaluation is significantly eliminated, thus providing faster query response and saving client energy.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 3: C. Gotsman and M. Lindenbaum. On the Metric Properties of Discrete Space-Filling Curves. IEEE Transactions on Image Processing, 5(5):794--797, 1996.
• 4: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 5: T. Imielinski , S. Viswanathan , B. r. Badrinath, Data on Air: Organization and Access, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.353-372, May 1997 [doi>10.1109/69.599926]
• 6: Wang-Chien Lee , Baihua Zheng, DSI: A Fully Distributed Spatial Index for Location-Based Wireless Broadcast Services, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.349-358, June 06-10, 2005 [doi>10.1109/ICDCS.2005.26]
• 7: Mesquite Software. CSIM 18, http://www.mesquite.com.
• 8: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 9: Yufei Tao , Dimitris Papadias, Time-parameterized queries in spatio-temporal databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564730]
• 10: U.S. Census Bureau. Topologically Integrated Geographic Encoding and Referencing System (TIGER/Line). http://www.census.gov/geo/www/tiger/.
• 11: Jianliang Xu , Wang-Chien Lee , Xueyan Tang, Exponential index: a parameterized distributed indexing scheme for data on air, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990084]
• 12: Jianliang Xu , Baihua Zheng , Wang-Chien Lee , Dik Lun Lee, The D-Tree: An Index Structure for Planar Point Queries in Location-Based Wireless Services, IEEE Transactions on Knowledge and Data Engineering, v.16 n.12, p.1526-1542, December 2004 [doi>10.1109/TKDE.2004.97]
• 13: Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872812]
• 14: Baihua Zheng , Dik Lun Lee, Semantic Caching in Location-Dependent Query Processing, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.97-116, July 12-15, 2001
• 15: Baihua Zheng , Wang-Chien Lee , Dik Lun Lee, Spatial Index on Air, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.297, March 23-26, 2003
• 16: B. Zheng, J. Xu, W.-C. Lee, and D. L. Lee. Energy-Conserving Air Indexes for Nearest Neighbor Search. In Proceedings of EDBT, Heraklion, Crete, Greece, Mar 14-18, pages 48--66, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Performance

Keywords:
data broadcast, location-dependent spatial query, valid scope