Evaluating uncertain location-based spatial queries

ABSTRACT

Location-Based Spatial Queries (LBSQ) are becoming more and more useful in location-based services such as those provided by cell-phones, Wireless LAN and GPS technologies. They support the access to information resources by taking into account the spatial context of the user when submitting the query, and the spatial location of the searched resources (instances). In fact, in a LBSQ the key-selection condition is generally a constraint on the distance of the resources in the database (instances) from the user location. One deficiency of current approaches is the fact that they do not manage the uncertainty that often characterizes the knowledge of either the user location or the searched instances. A model for representing and evaluating uncertain Location-Based Spatial Queries is proposed in which besides location uncertainty also the spatial condition can be imprecise. A two-step evaluation procedure of LBSQs is outlined based on a filter and on a refinement phase.

REFERENCES

• 1: Alastair R. Beresford , Frank Stajano, Location Privacy in Pervasive Computing, IEEE Pervasive Computing, v.2 n.1, p.46-55, January 2003 [doi>10.1109/MPRV.2003.1186725]
• 2: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: G. Bordogna, M. Pagani, G. Pasi, G. Psaila, Flexible location-based spatial queries in "Theoretical Advances and Applications of Fuzzy Logic and Soft Computing", Oscar Castillo, Patricia Melin, Oscar Montiel Ross, Roberto Sepulveda Cruz, Witold Pedrycz, Janusz Kacprzyk Eds, ISBN: 3540724338, Sprinter Verlag, 42, Advances in Soft Computing series, (2007), 36--45.
• 4: Bordogna G., Pasi G.: A semantics for Soft selection conditions in Fuzzy Databases based on a Fuzzy Inclusion, in Proc. of IFSA03 (2003).
• 5: Bosc P., and Prade H.: An Introduction to the Fuzzy Set and Possibility Theory-based Treatment of Flexible Queries and Uncertain and Imprecise Databases, in Uncertainty Management in Information Systems: from Needs to Solutions, A. Motro and P. Smets eds, Kluwer, (1997), 285--324.
• 6: Bosc P., Buckles B. B., Petry F. E., Pivert O.: Fuzzy Databases, in Fuzzy Sets in Approximate Reasoning and Information Systems, J. C. Bezdek, D. Dubois and H. Prade eds., Kluwer Ac. Pub., (1999), 403--468.
• 7: Bosc P., Pivert O.: A Formal Framework for Representation-Based Querying of Databases Containing Ill-known Data, in Proc. of the IIA'99 SOCO'99, (1999).
• 8: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 9: Reynold Cheng , Yuni Xia , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter, Efficient indexing methods for probabilistic threshold queries over uncertain data, Proceedings of the Thirtieth international conference on Very large data bases, p.876-887, August 31-September 03, 2004, Toronto, Canada
• 10: De Caluwe R.: Fuzzy and Uncertain Object-Oriented databases, Concepts and Models, World Scientific, (1997).
• 11: Dubois D., Prade H.: Tolerant Fuzzy Pattern matching: an Introduction, in Fuzziness in Database Management Systems, P. Bosc and J. Kacprzyk eds., Physica Verlag, (1994).
• 12: Gedik B., Liu L.: Mobiyes Distributed processing of continuously moving queries on moving objects in a mobile system, in Proc. of EDBT, (2004).
• 13: Marco Gruteser , Dirk Grunwald, Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking, Proceedings of the 1st international conference on Mobile systems, applications and services, p.31-42, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1189037]
• 14: Haibo Hu , Jianliang Xu , Wing Sing Wong , Baihua Zheng , Dik Lun Lee , Wang-Chien Lee, Proactive Caching for Spatial Queries in Mobile Environments, Proceedings of the 21st International Conference on Data Engineering, p.403-414, April 05-08, 2005 [doi>10.1109/ICDE.2005.113]
• 15: Sergio Ilarri , Eduardo Mena , Arantza Illarramendi, Location-Dependent Queries in Mobile Contexts: Distributed Processing Using Mobile Agents, IEEE Transactions on Mobile Computing, v.5 n.8, p.1029-1043, August 2006 [doi>10.1109/TMC.2006.118]
• 16: Dik Lun Lee , Jianliang Xu , Baihua Zheng , Wang-Chien Lee, Data Management in Location-Dependent Information Services, IEEE Pervasive Computing, v.1 n.3, p.65-72, July 2002 [doi>10.1109/MPRV.2002.1037724]
• 17: Petry F. E., Fuzzy Databases, Kluwer, (1996).
• 18: Pforser D., Jensen C.: Capturing the uncertainty of moving-objects representations. in Proc. of SSDBM, (1999).
• 19: Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
• 20: Vila M. A., Cubero J. C., Medina J. M., Pons O.: A Conceptual Approach for Dealing with Imprecision and Uncertainty in Object-Based data Models, Int. J. of Intel. Syst., 11(10), (1996), 791--806.
• 21: Michael Alan Caplinger , Michael Lee Campbell , Michael Anthony Capstick, Cover story: they know where you are, IEEE Spectrum, v.40 n.7, p.20-25, July 2003 [doi>10.1109/MSPEC.2003.1209608]
• 22: Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha, Updating and Querying Databases that Track Mobile Units, Distributed and Parallel Databases, v.7 n.3, p.257-387, July 1999 [doi>10.1023/A:1008782710752]
• 23: Xu J., Zheng B., Lee W., Lee D., Energy Efficient Index for Querying Location_Dependent Data in Mobile Broadcast environment, in proc. of ICDE, (2003).
• 24: 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]
• 25: Zheng B., Xu J., Lee W., and Lee D., Energy-Conserving Air Indexes for NN Search, E. Bertino et al. Eds.: EDBT 2004, LNCS 2992, Springer-Verlag, (2004), 48--66.

INDEX TERMS

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

General Terms:
Languages

Keywords:
minkowski sum, uncertain location-based spatial queries