Range-Based Skyline Queries in Mobile Environments
- 15 November 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 25 (4) , 835-849
Abstract
Skyline query processing for location-based services, which considers both spatial and nonspatial attributes of the objects being queried, has recently received increasing attention. Existing solutions focus on solving point- or line-based skyline queries, in which the query location is an exact location point or a line segment. However, due to privacy concerns and limited precision of localization devices, the input of a user location is often a spatial range. This paper studies a new problem of how to process such range-based skyline queries. Two novel algorithms are proposed: one is index-based (I-SKY) and the other is not based on any index (N-SKY). To handle frequent movements of the objects being queried, we also propose incremental versions of I-SKY and N-SKY, which avoid recomputing the query index and results from scratch. Additionally, we develop efficient solutions for probabilistic and continuous range-based skyline queries. Experimental results show that our proposed algorithms well outperform the baseline algorithm that adopts the existing line-based skyline solution. Moreover, the incremental versions of I-SKY and N-SKY save substantial computation cost, especially when the objects move frequently.Keywords
This publication has 23 references indexed in Scilit:
- Privacy-aware location data publishingACM Transactions on Database Systems, 2010
- Casper*ACM Transactions on Database Systems, 2009
- Z-SKY: an efficient skyline query processing framework based on Z-orderThe VLDB Journal, 2009
- Location-Dependent Skyline Query2008
- Computational Geometry2008
- Progressive skyline computation in database systemsACM Transactions on Database Systems, 2005
- Skyline with presorting2004
- An optimal and progressive algorithm for skyline queries2003
- Shooting Stars in the Sky2002
- On the Average Number of Maxima in a Set of Vectors and ApplicationsJournal of the ACM, 1978