SCRAP Header

Skyline Query Processing Using Localized Servers

IJEECC Front Page

The literature on skyline algorithms has so far dealt mainly with queries of static query points over static data sets. With the increasing number of mobile service applications and users, however, the need for continuous skyline query processing has become more pressing. A continuous skyline query involves not only static dimensions, but also the dynamic one. In this paper, we examine the spatiotemporal coherence of the problem and propose a continuous skyline query processing strategy for moving query points. First, we distinguish the data points that are permanently in the skyline and use them to derive a search bound. Second, we investigate the connection between the spatial positions of data points and their dominance relationship, which provides an indication of where to find changes in the skyline and how to maintain the skyline continuously.
Keywords:SKY, N-SKY, LBS, SSQ.


  1. J.L. Bentley, H.T. Kung, M. Schkolnick, and C.D. Thompson, “On the Average Number of Maxima in a Set of Vectors and Applications,” J. ACM, vol. 25, no. 4, pp. 536-543, 1978.
  2. M.Berg, O.Cheong, and M.Kreveld, Computational Geometry:Algorithms and Applications, third ed., chapter 7. Springer, 2008.
  3. S. Borzonyi, D. Kossmann, and K. Stocker, “The Skyline Operator,” Proc. Int’l Conf. Data Eng., pp. 421-430, 2001.
  4. Y. Cai and T. Xu, “Design, Analysis, and Implementation of a Large-Scale Real-Time Location-Based Information Sharing System,” Proc. ACM Sixth Int’l Conf. Mobile Systems, Applications, and Services (MobiSys ’08), pp. 106-117, 2008.
  5. J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with Pre-Sorting,” Proc. Int’l Conf. Data Eng., 2003.
  6. C.-Y. Chow, M.F. Mokbel, and W.G. Aref, “Casper*: Query Processing for Location Services without Compromising Privacy,” ACM Trans. Database Systems, vol. 34, no. 4, article 24, Dec. 2009.
  7. B. Fan and H. Ahmed, “A Survey of Mobility Models in Wireless Ad-Hoc Networks,” Wireless Ad-Hoc Networks, Chapter 1, Kluwer Academic, 2006.
  8. Y. Gao and B. Zheng, “Continuous Obstructed Nearest Neighbor Queries in Spatial Databases,” Proc. ACM SIGMOD Int’l Conf. Management of Data, pp. 557-590, 2009.
  9. B. Gedik, K.-L. L, P.S. Yu, and L. Liu, “Processing Moving Queries over Moving Objects Using Motion-Adaptive Indexes ,” IEEE Trans. Knowledge and Data Eng., vol. 18, no. 5, pp. 651-668, May 2006.
  10. H. Hu and D.L. Lee, “Range Nearest-Neighbor Query,” IEEE Trans. Knowledge and Data Eng., vol. 18, no. 1, pp. 78-91, Jan. 2006.