Range-based skyline queries in mobile environments

Xin Lin*, Jianliang XU, Haibo HU

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

41 Citations (Scopus)


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.

Original languageEnglish
Article number6081864
Pages (from-to)835-849
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number4
Publication statusPublished - Apr 2013

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • Location-based services
  • moving objects
  • query processing
  • skyline queries


Dive into the research topics of 'Range-based skyline queries in mobile environments'. Together they form a unique fingerprint.

Cite this