Efficient valid scope computation for location-dependent spatial queries in mobile and wireless environments

ABSTRACT

In mobile and wireless environments, mobile clients can access information with respect to their locations by submitting Location-Dependent Spatial Queries (LDSQs) to Location-Based Service (LBS) servers. Owing to scarce wireless channel bandwidth and limited client battery life, frequent LDSQ submission from clients must be avoided. Observing that LDSQs issued from similar client positions would normally return the same results, we explore the idea of valid scope, that represents a spatial area in which a set of LDSQs will retrieve exactly the same query results. With a valid scope derived and an LDSQ result cached at the client side, a client can assert whether the new LDSQs can be answered with the maintained LDSQ result, thus eliminating the LDSQs sent to the server. As such, contention on wireless channel and client energy consumed for data transmission can be considerably reduced. In this paper, we design efficient algorithms to compute the valid scope for common types of LDSQs, including nearest neighbor queries and range queries. Through an extensive set of experiments, our proposed valid scope computation algorithms are shown to significantly outperform existing approaches.

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: 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
• 4: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 5: Ken C. K. Lee , Wang-Chien Lee , Hong Va Leong, Nearest Surrounder Queries, Proceedings of the 22nd International Conference on Data Engineering, p.85, April 03-07, 2006 [doi>10.1109/ICDE.2006.104]
• 6: Ken C. K. Lee , Hong Va Leong , Antonio Si, Semantic Data Broadcast for a Mobile Environment Based on Dynamic and Adaptive Chunking, IEEE Transactions on Computers, v.51 n.10, p.1253-1268, October 2002 [doi>10.1109/TC.2002.1039851]
• 7: Ken C.K. Lee , Josh Schiffman , Baihua Zheng , Wang-Chien Lee, Valid scope computation for location-dependent spatial query in mobile broadcast environments, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458245]
• 8: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 9: 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
• 10: 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]
• 11: U.S. Census Bureau. Topologically Integrated Geographic Encoding and Referencing System. U.S. Census Bureau -TIGER/Line.
• 12: 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]
• 13: 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