Computing Continuous Skyline Queries without Discriminating between Static and Dynamic Attributes

Authors: Ibrahim Gomaa, Hoda M. O. Mokhtar

Abstract:

Although most of the existing skyline queries algorithms focused basically on querying static points through static databases; with the expanding number of sensors, wireless communications and mobile applications, the demand for continuous skyline queries has increased. Unlike traditional skyline queries which only consider static attributes, continuous skyline queries include dynamic attributes, as well as the static ones. However, as skyline queries computation is based on checking the domination of skyline points over all dimensions, considering both the static and dynamic attributes without separation is required. In this paper, we present an efficient algorithm for computing continuous skyline queries without discriminating between static and dynamic attributes. Our algorithm in brief proceeds as follows: First, it excludes the points which will not be in the initial skyline result; this pruning phase reduces the required number of comparisons. Second, the association between the spatial positions of data points is examined; this phase gives an idea of where changes in the result might occur and consequently enables us to efficiently update the skyline result (continuous update) rather than computing the skyline from scratch. Finally, experimental evaluation is provided which demonstrates the accuracy, performance and efficiency of our algorithm over other existing approaches.

Keywords: Continuous query processing, dynamic database, moving object, skyline queries.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1339636

References:

[1] O. Wolfson, B. Xd, S. Chamberlai, and L. Jiang, "Moving Objects Databases: Issues and Solutions," Proceedings of the 10th International Conference on Scientific and Statistical Database Management, pp.111-122, 1998.
[2] S. Borzonyi, D. Kossmann, and K. Stocker, “The Skyline Operator,” Proc. Int’l Conf. Data Eng., pp. 421-430, 2001.
[3] R. Benetis, C. Jensen, G. Karciauskas, and S. Saltenis, “Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects,” Proc. Int’l Symp. Database Eng. & Applications, pp. 44-53, 2002.
[4] H. Mokhtar, J. Su, and O. Ibarra, “On Moving Object Queries,” Proc. 21st ACM PODS Symp. Principles of Database Systems, pp. 188- 198, 2002.
[5] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An Optimal and Progressive Algorithm for Skyline Queries,” Proc. 2003 ACM SIGMOD Int’l Conf. Management of Data, pp. 467-478, 2003.
[6] Liu, Jinfei, et al. "Finding pareto optimal groups: group-based skyline." Proceedings of the VLDB Endowment 8.13 (2015): 2086-2097.
[7] H. Zhiyong, L. Hua, O. Beng Chin, and K. H. T. Anthony, "Continuous Skyline Queries for Moving Objects." vol. 18: IEEE Educational Activities Department, pp. 1645-1658, 2006.
[8] E. El-Dawy, Eman, Hoda MO Mokhtar, and Ali El-Bastawissy. "Directional skyline queries." Data and Knowledge Engineering. Springer Berlin Heidelberg, 2012. 15-28.
[9] El-Dawy, Eman, Hoda M.O. Mokhtar, and Ali El-Bastawissy. "Multi-level continuous skyline queries (MCSQ)." Data and Knowledge Engineering (ICDKE), 2011 International Conference on. IEEE, 2011.
[10] Li, He, and Jaesoo Yoo. "An efficient scheme for continuous skyline query processing over dynamic data set." Big Data and Smart Computing (BIGCOMP), 2014 International Conference on. IEEE, 2014.
[11] Zhang, Boliang, Shuigeng Zhou, and Jihong Guan. "Adapting Skyline Computation to the MapReduce Framework: Algorithms and Experiments." DASFAA Workshops. 2011.‏
[12] Park, Yoonjae, Jun-Ki Min, and Kyuseok Shim. "Parallel computation of skyline and reverse skyline queries using mapreduce." Proceedings of the VLDB Endowment 6.14 (2013): 2002-2013.
[13] K. Raptopoulou, A. Papadopoulos, and Y. Manolopoulos, “Fast Nearest-Neighbor Query Processing in Moving-Object Databases,” GeoInformatica, vol. 7, no. 2, pp. 113-137, 2003.
[14] Iwerks, Glenn S., Hanan Samet, and Ken Smith. "Continuous k-nearest neighbor queries for continuously moving points with updates." Proceedings of the 29th international conference on Very large data bases-Volume 29. VLDB Endowment, 2003.‏
[15] Tao, Yufei, and Dimitris Papadias. "Time-parameterized queries in spatio-temporal databases." Proceedings of the 2002 ACM SIGMOD international conference on Management of data. ACM, 2002.
[16] T. T. El-midany, A. Elkeran, and H. Tawfik, “A Sweep-Line Algorithm and Its Application to Spiral Pocketing,” vol. 2, no. 1, 2002.
[17] Hoda M. O. Mokhtar and J. Su.” A Query Language for Moving Object Trajectories”, Proceedings of the International Scientific and Statistical Database Management Conference (SSDBM), University of California, Santa Barbara, June 27-29, 2005.
[18] Hoda M. O. Mokhtar and J. Su. “Universal Trajectory Queries for Moving Object Databases”, Proceedings of IEEE International Conference on Mobile Data Management, Berkeley, CA, January 19-22, 2004.