Efficient Evaluation of Imprecise Location-Dependent Queries
Open Access
- 1 April 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 586-595
Abstract
In location-based services, it is common for a user to issue a query based on his/her current position. One such example is "find the available cabs within two miles of my current location". Very often, the query issuers' locations are imprecise due to measurement error, sampling error, or message delay. They may also want to protect their privacy by providing a less precise location. In this paper, we study the efficiency of queries that return probabilistic guarantees for location data with uncertainty. We classify this query into two types, based on whether the data (1) has no uncertainty (e.g., shops and restaurants), or (2) has a controlled degree of uncertainty (e.g., moving vehicles). Based on this classification, we develop three methods to improve the computational and I/O performance. The first method expands the query range based on the query issuer's uncertainty. The second idea exchanges the roles of query and data. The third technique exploits the fact that users may only be interested in answers with probabilities higher than some threshold. Experimental simulation over a realistic dataset reveals that our approaches improve the query performance significantly.Keywords
This publication has 13 references indexed in Scilit:
- Protecting Location Privacy with Personalized k-Anonymity: Architecture and AlgorithmsIEEE Transactions on Mobile Computing, 2007
- Preserving User Location Privacy in Mobile Data Management Infrastructures2006
- Querying imprecise data in moving object environmentsIEEE Transactions on Knowledge and Data Engineering, 2004
- Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data2004
- They Know Where You AreIEEE Spectrum, 2003
- Evaluating probabilistic queries over imprecise data2003
- Location privacy in pervasive computingIEEE Pervasive Computing, 2003
- Querying the uncertain position of moving objects1998
- The Grid FileACM Transactions on Database Systems, 1984
- R-trees1984