Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Parallel continuous skyline query over high-dimensional data stream windows

  • Published:
Distributed and Parallel Databases Aims and scope Submit manuscript

Abstract

Real-time multi-criteria decision-making applications in fields like high-speed algorithmic trading, emergency response, and disaster management have driven the development of new types of preference queries. This is an example of a skyline search. Multi-criteria decision-making utilizes the skyline operator to extract highly significant tuples or useful data points from extensive sets of multi-dimensional databases. The user’s settings determine the results, which include all tuples whose attribute vector remains undefeated by another tuple. The extracted tuples are commonly known as the skyline set. Lately, there has been a growing trend in research studies to perform skyline queries on data stream applications. These queries consist of extracting desired records from sliding windows and removing outdated records from incoming data sets that do not meet user requirements. The datasets in these applications are extremely large and exhibit a wide range of dimensions that vary over time. Consequently, the skyline query is considered a computationally demanding task, with the challenge of achieving a real-time response within an acceptable duration. We must transport and process enormous quantities of data. Traditional skyline algorithms have faced new challenges due to limitations in data transmission bandwidth and latency. The transfer of vast quantities of data would affect performance, power efficiency, and reliability. Consequently, it is imperative to make alterations to the computer paradigm. Parallel skyline queries have attracted the attention of both scholars and the business sector. The study of skyline queries has focused on sequential algorithms and parallel implementations for multicore processors, primarily due to their widespread use. While previous research has focused on sequential algorithms, there is a limitation to comprehensive studies that specifically address modern parallel processors. While numerous articles have been published regarding the parallelization of regular skyline queries, there is a limited amount of research dedicated specifically to the parallel processing of continuous skyline queries. This study introduces PRSS, a continuous skyline technique for multicore processors specifically designed for sliding window-based data streams. The efficacy of the proposed parallel implementation is demonstrated through tests conducted on both real-world and synthetic datasets, encompassing various point distributions, arrival rates, and window widths. The experimental results for a dataset characterized by a large number of dimensions and cardinality demonstrate significant acceleration.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Data availability

synthetic data: the standard skyline data generator. real data: public repository under creative commons license. We have also uploaded our PRSS algorithm C++ source code on GitHub.

Notes

  1. https://github.com/avionicscode/multicore-prss.

  2. https://github.com/skyline-sdi/sdi-rss.

  3. http://pgfoundry.org/projects/randdataset.

  4. https://doi.org/10.24432/C50K5N.

  5. https://crudata.uea.ac.uk/cru/data//hrg/tmc/.

References

  1. Wang, G., Xin, J., Chen, L., Liu, Y.: Energy-efficient reverse skyline query processing over wireless sensor networks. IEEE Trans. Knowl. Data Eng. 24(7), 1259–1275 (2011)

    Article  Google Scholar 

  2. Reddy, P.C., Babu, A.S.: Survey on weather prediction using big data analystics. In: 2017 Second International Conference on Electrical, Computer and Communication Technologies (ICECCT), pp. 1–6. IEEE (2017)

  3. Chen, J., Lyu, Z., Liu, Y., Huang, J., Zhang, G., Wang, J., Chen, X.: A big data analysis and application platform for civil aircraft health management. In: 2016 IEEE Second International Conference on Multimedia Big Data (BigMM), pp. 404–409. IEEE (2016)

  4. Kertiou, I., Benharzallah, S., Kahloul, L., Beggas, M., Euler, R., Laouid, A., Bounceur, A.: A dynamic skyline technique for a context-aware selection of the best sensors in an iot architecture. Ad Hoc Netw. 81, 183–196 (2018)

    Article  Google Scholar 

  5. De Matteis, T., Di Girolamo, S., Mencagli, G.: Continuous skyline queries on multicore architectures. Concurr. Comput. 28(12), 3503–3522 (2016)

    Article  Google Scholar 

  6. Alami, K., Maabout, S.: Multidimensional skylines over streaming data. In: International Conference on Database Systems for Advanced Applications, pp. 338–342. Springer (2019)

  7. Khames, W., Hadjali, A., Lagha, M.: Skyline computation on multicore architectures: a survey. In: 2020 International Conference on Data Analytics for Business and Industry: Way Towards a Sustainable Economy (ICDABI), pp. 1–6. IEEE (2020)

  8. Tao, Y., Papadias, D.: Maintaining sliding window skylines on data streams. IEEE Trans. Knowl. Data Eng. 18(3), 377–391 (2006)

    Article  Google Scholar 

  9. Zhang, J., Gu, J., Cheng, S., Li, B., Wang, W., Meng, D.: Efficient algorithms of parallel skyline join over data streams. In: International Conference on Algorithms and Architectures for Parallel Processing, pp. 184–199. Springer (2018)

  10. Borzsony, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings 17th International Conference on Data Engineering, pp. 421–430. IEEE (2001)

  11. Liu, R., Li, D.: Dynamic dimension indexing for efficient skyline maintenance on data streams. In: International Conference on Database Systems for Advanced Applications, pp. 272–287. Springer (2020)

  12. Lu, H., Zhou, Y., Haustad, J.: Continuous skyline monitoring over distributed data streams. In: International Conference on Scientific and Statistical Database Management, pp. 565–583. Springer (2010)

  13. Das Sarma, A., Lall, A., Nanongkai, D., Xu, J.: Randomized multi-pass streaming skyline algorithms. Proc. VLDB Endow. 2(1), 85–96 (2009)

    Article  Google Scholar 

  14. Balke, W.-T., Güntzer, U., Zheng, J.X.: Efficient distributed skylining for web information systems. In: Advances in Database Technology-EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14–18, 2004 9, pp. 256–273. Springer (2004)

  15. Alami, K., Maabout, S.: A framework for multidimensional skyline queries over streaming data. Data & Knowl. Eng. 127, 101792 (2020)

    Article  Google Scholar 

  16. Papadopoulos, A.N., Tiakas, E., Tzouramanis, T., Georgiadis, N., Manolopoulos, Y.: Skylines and other dominance-based queries. Synth. Lect. Data Manag. 15(2), 1–158 (2020)

    Article  Google Scholar 

  17. Im, H., Park, S.: Group skyline computation. Inform. Sci. 188, 151–169 (2012)

    Article  MathSciNet  Google Scholar 

  18. Sheng, C., Tao, Y.: On finding skylines in external memory. In: Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 107–116 (2011)

  19. Endres, M., Glaser, E.: Indexing for skyline computation: a comparison study. In: Flexible Query Answering Systems: 13th International Conference, FQAS 2019, Amantea, July 2–5, 2019, Proceedings 13, pp. 31–42. Springer (2019)

  20. Khalefa, M.E., Mokbel, M.F., Levandoski, J.J.: Skyline query processing for incomplete data. In: 2008 IEEE 24th International Conference on Data Engineering, pp. 556–565. IEEE (2008)

  21. Gao, Y., Miao, X., Cui, H., Chen, G., Li, Q.: Processing k-skyband, constrained skyline, and group-by skyline queries on incomplete data. Expert Syst. Appl. 41(10), 4959–4974 (2014)

    Article  Google Scholar 

  22. Zhang, S., Mamoulis, N., Cheung, D.W.: Scalable skyline computation using object-based space partitioning. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pp. 483–494 (2009)

  23. Papadias, D., Tao, Y., Fu, G., Seeger, B.: An optimal and progressive algorithm for skyline queries. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 467–478 (2003)

  24. Sun, S., Huang, Z., Zhong, H., Dai, D., Liu, H., Li, J.: Efficient monitoring of skyline queries over distributed data streams. Knowl. Inform. Syst. 25(3), 575–606 (2010)

    Article  Google Scholar 

  25. Balke, W.-T., Güntzer, U., Zheng, J.X.: Efficient distributed skylining for web information systems. In: Advances in Database Technology-EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14–18, 2004 9, pp. 256–273. Springer (2004)

  26. Lo, E., Yip, K.Y., Lin, K.-I., Cheung, D.W.: Progressive skylining over web-accessible databases. Data Knowl. Eng. 57(2), 122–147 (2006)

    Article  Google Scholar 

  27. Tan, K.-L., Eng, P.-K., Ooi, B.C., et al.: Efficient progressive skyline computation. In: VLDB, vol. 1, pp. 301–310 (2001)

  28. Lee, K.C., Lee, W.-C., Zheng, B., Li, H., Tian, Y.: Z-sky: an efficient skyline query processing framework based on z-order. VLDB J. 19, 333–362 (2010)

    Article  Google Scholar 

  29. Selke, J., Balke, W.-T.: Skymap: a trie-based index structure for high-performance skyline query processing. In: International Conference on Database and Expert Systems Applications, pp. 350–365. Springer (2011)

  30. Lee, J., Hwang, S.-w.: Bskytree: scalable skyline computation using a balanced pivot selection. In: Proceedings of the 13th International Conference on Extending Database Technology, pp. 195–206 (2010)

  31. Koizumi, K., Eades, P., Hiraki, K., Inaba, M.: Bjr-tree: fast skyline computation algorithm for serendipitous searching problems. In: 2017 IEEE International Conference on Data Science and Advanced Analytics (DSAA), pp. 272–282. IEEE (2017)

  32. Hose, K., Vlachou, A.: A survey of skyline processing in highly distributed environments. VLDB J. 21, 359–384 (2012)

    Article  Google Scholar 

  33. Li, X., Wang, Y., Li, X., Wang, Y.: Parallelizing skyline queries over uncertain data streams with sliding window partitioning and grid index. Knowl. Inform. Syst. 41(2), 277–309 (2014)

    Article  Google Scholar 

  34. Im, H., Park, J., Park, S.: Parallel skyline computation on multicore architectures. Inform. Syst. 36(4), 808–823 (2011)

    Article  Google Scholar 

  35. Feng, X., Gao, Y., Jiang, T., Chen, L., Miao, X., Liu, Q.: Parallel k-skyband computation on multicore architecture. In: Asia-Pacific Web Conference, pp. 827–837. Springer (2013)

  36. Chester, S., Šidlauskas, D., Assent, I., Bøgh, K.S.: Scalable parallelization of skyline computation for multi-core processors. In: 2015 IEEE 31st International Conference on Data Engineering, pp. 1083–1094. IEEE (2015)

  37. Buanga, J.P.M., Badibanga, S.N., Ilunga, R.K.: Enhanced parallel skyline on multi-core architecture with low memory space cost. Int. J. Comput. Sci. Issues (IJCSI) 13(5), 153 (2016)

    Article  Google Scholar 

  38. Zeng, Y., Li, K., Yu, S., Zhou, Y., Li, K.: Parallel and progressive approaches for skyline query over probabilistic incomplete database. IEEE Access 6, 13289–13301 (2018)

    Article  Google Scholar 

  39. Zhu, H., Zhu, P., Li, X., Liu, Q., Xun, P.: Parallelization of skyline probability computation over uncertain preferences. Concurr. Comput. 29(18), 4201 (2017)

    Article  Google Scholar 

  40. Papapetrou, O., Garofalakis, M.: Monitoring distributed fragmented skylines. Distrib. Parall. Databases 36, 675–715 (2018)

    Article  Google Scholar 

  41. Wu, P., Zhang, C., Feng, Y., Zhao, B.Y., Agrawal, D., El Abbadi, A.: Parallelizing skyline queries for scalable distribution. In: Advances in Database Technology-EDBT 2006: 10th International Conference on Extending Database Technology, Munich, March 26–31, 2006 10, pp. 112–130. Springer (2006)

  42. Gao, Y., Chen, G., Chen, L., Chen, C.: Parallelizing progressive computation for skyline queries in multi-disk environment. In: Database and Expert Systems Applications: 17th International Conference, DEXA 2006, Kraków, Poland, September 4-8, 2006. Proceedings 17, pp. 697–706. Springer (2006)

  43. Wang, S., Ooi, B.C., Tung, A.K., Xu, L.: Efficient skyline query processing on peer-to-peer networks. In: 2007 IEEE 23rd International Conference on Data Engineering, pp. 1126–1135. IEEE (2006)

  44. Wang, S., Vu, Q.H., Ooi, B.C., Tung, A.K., Xu, L.: Skyframe: a framework for skyline query processing in peer-to-peer systems. VLDB J. 18, 345–362 (2009)

    Article  Google Scholar 

  45. Hose, K.: Processing skyline queries in p2p systems. In: VLDB 2005 PhD Workshop, pp. 36–40. Citeseer (2005)

  46. Li, H., Tan, Q., Lee, W.-C.: Efficient progressive processing of skyline queries in peer-to-peer systems. In: Proceedings of the 1st International Conference on Scalable Information Systems, p. 26 (2006)

  47. Huang, Z., Jensen, C.S., Lu, H., Ooi, B.C.: Skyline queries against mobile lightweight devices in manets. In: 22nd International Conference on Data Engineering (ICDE’06), pp. 66–66. IEEE (2006)

  48. Li, J., Xiong, S., et al.: Efficient pr-skyline query processing and optimization in wireless sensor networks. Wirel. Sens. Netw. 2(11), 838 (2010)

    Article  Google Scholar 

  49. Vlachou, A., Doulkeridis, C., Kotidis, Y.: Angle-based space partitioning for efficient parallel skyline computation. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 227–238 (2008)

  50. Yu, J., Liu, X., Liu, G.-h.: A window-based algorithm for skyline queries. In: Sixth International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT’05), pp. 907–909. IEEE (2005)

  51. Morse, M., Patel, J.M., Grosky, W.I.: Efficient continuous skyline computation. Inform. Sci. 177(17), 3411–3437 (2007)

    Article  MathSciNet  Google Scholar 

  52. Huang, Z., Lu, H., Ooi, B.C., Tung, A.K.: Continuous skyline queries for moving objects. IEEE Trans. Knowl. Data Eng. 18(12), 1645–1658 (2006)

    Article  Google Scholar 

  53. Sacharidis, D., Bouros, P., Sellis, T.: Caching dynamic skyline queries. In: Scientific and Statistical Database Management: 20th International Conference, SSDBM 2008, Hong Kong, July 9-11, 2008 Proceedings 20, pp. 455–472. Springer (2008)

  54. Han, X., Wang, B., Lai, G.: Dynamic skyline computation on massive data. Knowl. Inform. Syst. 59(3), 571–599 (2019)

    Article  Google Scholar 

  55. Zeighami, S., Ghinita, G., Shahabi, C.: Secure dynamic skyline queries using result materialization. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 157–168. IEEE (2021)

  56. Wang, W., Li, H., Peng, Y., Bhowmick, S.S., Chen, P., Chen, X., Cui, J.: An efficient secure dynamic skyline query model (2020). arXiv preprint arXiv:2002.07511

  57. Jin, W., Han, J., Ester, M.: Mining thick skylines over large databases. In: Knowledge Discovery in Databases: PKDD 2004: 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, Pisa, September 20–24, 2004. Proceedings 8, pp. 255–266. Springer (2004)

  58. Xin, J., Wang, G., Chen, L., Zhang, X., Wang, Z.: Continuously maintaining sliding window skylines in a sensor network. In: International Conference on Database Systems for Advanced Applications, pp. 509–521. Springer (2007)

  59. Sarkas, N., Das, G., Koudas, N., Tung, A.K.: Categorical skylines for streaming data. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 239–250 (2008)

  60. Vlachou, A., Nørvåg, K.: Bandwidth-constrained distributed skyline computation. In: Proceedings of the Eighth ACM International Workshop on Data Engineering for Wireless and Mobile Access, pp. 17–24 (2009)

  61. Zhu, L., Tao, Y., Zhou, S.: Distributed skyline retrieval with low bandwidth consumption. IEEE Trans. Knowl. Data Eng. 21(3), 384–400 (2008)

    Google Scholar 

  62. Vlachou, A., Doulkeridis, C., Kotidis, Y., Vazirgiannis, M.: Efficient routing of subspace skyline queries over highly distributed data. IEEE Trans. Knowl. Data Eng. 22(12), 1694–1708 (2009)

    Article  Google Scholar 

  63. Rocha-Junior, J.B., Vlachou, A., Doulkeridis, C., Nørvåg, K.: Efficient execution plans for distributed skyline query processing. In: Proceedings of the 14th International Conference on Extending Database Technology, pp. 271–282 (2011)

  64. Cui, B., Lu, H., Xu, Q., Chen, L., Dai, Y., Zhou, Y.: Parallel distributed processing of constrained skyline queries by filtering. In: 2008 IEEE 24th International Conference on Data Engineering, pp. 546–555. IEEE (2008)

  65. Lee, Y.W., Lee, K.Y., Kim, M.H.: Efficient processing of multiple continuous skyline queries over a data stream. Inform. Sci. 221, 316–337 (2013)

    Article  Google Scholar 

  66. Lee, J., You, G.-W., Hwang, S.-W., Selke, J., Balke, W.-T.: Interactive skyline queries. Inform. Sci. 211, 18–35 (2012)

    Article  Google Scholar 

  67. Xia, T., Zhang, D., Fang, Z., Chen, C., Wang, J.: Online subspace skyline query processing using the compressed skycube. ACM Trans. Database Syst. (TODS) 37(2), 1–36 (2012)

    Article  Google Scholar 

  68. Lee, J., Hwang, S.-W.: Scalable skyline computation using a balanced pivot selection technique. Inform. Syst. 39, 1–21 (2014)

    Article  Google Scholar 

  69. Lee, J., Hwang, S.-W.: Toward efficient multidimensional subspace skyline computation. VLDB J. 23, 129–145 (2014)

    Article  Google Scholar 

  70. Bai, M., Xin, J., Wang, G., Zimmermann, R., Wang, X.: Skyline-join query processing in distributed databases. Front. Comput. Sci. 10(2), 330–352 (2016)

    Article  Google Scholar 

  71. Wang, Y., Wei, W., Deng, Q., Liu, W., Song, H.: An energy-efficient skyline query for massively multidimensional sensing data. Sensors 16(1), 83 (2016)

    Article  Google Scholar 

  72. Yu, B., Choi, W., Liu, L.: Exploring correlation for fast skyline computation. J. Supercomput. 73(11), 5071–5102 (2017)

    Article  Google Scholar 

  73. Huang, Y.-K., Lee, C.-P., Tsai, C.-Y.: Evaluating knn-skyline queries in dynamic road networks. In: 2018 27th Wireless and Optical Communication Conference (WOCC), pp. 1–2. IEEE (2018)

  74. Huang, Y.-K., Chang, C.-H., Lee, C.: Continuous distance-based skyline queries in road networks. Inform. Syst. 37(7), 611–633 (2012)

    Article  Google Scholar 

  75. Rudenko, L., Endres, M.: Real-time skyline computation on data streams with sls: implementation and experiences (2018)

  76. Ren, W., Lian, X., Ghazinour, K.: Skyline queries over incomplete data streams. VLDB J. 28(6), 961–985 (2019)

    Article  Google Scholar 

  77. Guo, X., Li, H., Wulamu, A., Xie, Y., Fu, Y.: Efficient processing of skyline group queries over a data stream. Tsinghua Sci. Technol. 21(1), 29–39 (2016)

    Article  Google Scholar 

  78. Yang, Z., Zhou, X., Li, K., Gao, Y., Li, K.: Progressive approaches to flexible group skyline queries. Knowl. Inform. Syst. 63, 1471–1496 (2021)

    Article  Google Scholar 

  79. Sharifzadeh, M., Shahabi, C.: The spatial skyline queries. In: Proceedings of the 32nd International Conference on Very Large Data Bases, pp. 751–762 (2006)

  80. Son, W., Lee, M.-W., Ahn, H.-K., Hwang, S.-w.: Spatial skyline queries: An efficient geometric algorithm. In: Advances in Spatial and Temporal Databases: 11th International Symposium, SSTD 2009 Aalborg, Denmark, July 8-+10, 2009 Proceedings 11, pp. 247–264. Springer (2009)

  81. Wang, C., Wang, C., Guo, G., Ye, X., Philip, S.Y.: Efficient computation of g-skyline groups. IEEE Trans. Knowl. Data Eng. 30(4), 674–688 (2017)

    Article  Google Scholar 

  82. Huang, Y.-K.: Continuous d\(\varepsilon\)-skyline queries for objects with time-varying attribute in road networks. In: 2017 IEEE 31st International Conference on Advanced Information Networking and Applications (AINA), pp. 439–446. IEEE (2017)

  83. Elmi, S., Min, J.-K.: Spatial skyline queries over incomplete data for smart cities. J. Syst. Architect. 90, 1–14 (2018)

    Article  Google Scholar 

  84. Siddique, M.A., Zaman, A., Islam, M.M., Morimoto, Y.: Multicore based spatial k dominant skyline computation. In: 2012 Third International Conference on Networking and Computing, pp. 188–194. IEEE (2012)

  85. Wang, W., Zhang, J., Sun, M.-T., Ku, W.-S.: A scalable spatial skyline evaluation system utilizing parallel independent region groups. VLDB J. 28, 73–98 (2019)

    Article  Google Scholar 

  86. Chen, L., Lian, X.: Efficient processing of metric skyline queries. IEEE Trans. Knowl. Data Eng. 21(3), 351–365 (2008)

    Article  Google Scholar 

  87. Fuhry, D., Jin, R., Zhang, D.: Efficient skyline computation in metric space. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pp. 1042–1051 (2009)

  88. Tao, Y., Ding, L., Lin, X., Pei, J.: Distance-based representative skyline. In: 2009 IEEE 25th International Conference on Data Engineering, pp. 892–903. IEEE (2009)

  89. Fu, X., Miao, X., Xu, J., Gao, Y.: Continuous range-based skyline queries in road networks. World Wide Web 20(6), 1443–1467 (2017)

    Article  Google Scholar 

  90. Hidayat, A., Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: Continuous monitoring of moving skyline and top-k queries. VLDB J. 31(3), 459–482 (2022)

    Article  Google Scholar 

  91. Lin, X., Xu, J., Hu, H.: Range-based skyline queries in mobile environments. IEEE Trans. Knowl. Data Eng. 25(4), 835–849 (2011)

    Article  Google Scholar 

  92. Wang, W.-C., Wang, E.T., Chen, A.L.: Dynamic skylines considering range queries. In: Database Systems for Advanced Applications: 16th International Conference, DASFAA 2011, Hong Kong, April 22–25, 2011, Proceedings, Part II 16, pp. 235–250. Springer (2011)

  93. Tzouramanis, T., Tiakas, E., Papadopoulos, A.N., Manolopoulos, Y.: The range skyline query. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 47–56 (2018)

  94. Dellis, E., Seeger, B.: Efficient computation of reverse skyline queries. In: VLDB, vol. 7, pp. 291–302. Citeseer (2007)

  95. Lian, X., Chen, L.: Monochromatic and bichromatic reverse skyline search over uncertain databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 213–226 (2008)

  96. Wu, X., Tao, Y., Wong, R.C.-W., Ding, L., Yu, J.X.: Finding the influence set through skylines. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pp. 1030–1041 (2009)

  97. Lian, X., Chen, L.: Reverse skyline search in uncertain databases. ACM Trans. Database Syst. (TODS) 35(1), 1–49 (2008)

    Article  Google Scholar 

  98. Zhu, L., Li, C., Chen, H.: Efficient computation of reverse skyline on data stream. In: 2009 International Joint Conference on Computational Sciences and Optimization, vol. 1, pp. 735–739. IEEE (2009)

  99. Lim, J., Bok, K., Yoo, J.: A continuous reverse skyline query processing scheme for multimedia data sharing in mobile environments. Multimedia Tools Appl. 78(20), 28357–28373 (2019)

    Article  Google Scholar 

  100. Banaei-Kashani, F., Ghaemi, P., Movaqar, B., Kazemitabar, S.J.: Efficient maximal reverse skyline query processing. GeoInformatica 21, 549–572 (2017)

    Article  Google Scholar 

  101. Chen, L., Lian, X.: Dynamic skyline queries in metric spaces. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, pp. 333–343 (2008)

  102. Zhang, Z., Cheng, R., Papadias, D., Tung, A.K.: Minimizing the communication cost for continuous skyline maintenance. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pp. 495–508 (2009)

  103. Hanning, W., Weixiang, X., Yang, J., Wei, L., Chaolong, J.: Efficient processing of continuous skyline query over smarter traffic data stream for cloud computing. Discrete Dynamics in Nature and Society 2013 (2013)

  104. Wulamu, A., Li, H., Guo, X., Xie, Y., Fu, Y.: Processing skyline groups on data streams. In: 2015 IEEE 15th Intl Conf on Scalable Computing and Communications and Its Associated Workshops (UIC-ATC-ScalCom), pp. 935–942. IEEE (2015)

  105. Bai, M., Xin, J., Wang, G., Zhang, L., Zimmermann, R., Yuan, Y., Wu, X.: Discovering the \(k\) representative skyline over a sliding window. IEEE Trans. Knowl. Data Eng. 28(8), 2041–2056 (2016)

    Article  Google Scholar 

  106. Tzanakas, A., Tiakas, E., Manolopoulos, Y.: Skyline algorithms on streams of multidimensional data. In: East European Conference on Advances in Databases and Information Systems, pp. 63–71. Springer (2016)

  107. Tang, Y., Chen, S.: Supporting continuous skyline queries in dynamically weighted road networks. Math. Probl. Eng. 127, 101792 (2020)

    Google Scholar 

  108. Koizumi, K., Eades, P., Hiraki, K., Inaba, M.: Bjr-tree: fast skyline computation algorithm using dominance relation-based tree structure. Int. J. Data Sci. Anal. 7(1), 17–34 (2019)

    Article  Google Scholar 

  109. Jiang, T., Zhang, B., Lin, D., Gao, Y., Li, Q.: Efficient column-oriented processing for mutual subspace skyline queries. Soft Comput. 24(20), 15427–15445 (2020)

    Article  Google Scholar 

  110. Zheng, Z., Ruan, K., Yu, M., Zhang, X., Wang, N., Li, D.: k-dominant skyline query algorithm for dynamic datasets. Front. Comput. Sci. 15(1), 1–9 (2021)

    Article  Google Scholar 

  111. Atallah, M.J., Qi, Y.: Computing all skyline probabilities for uncertain data. In: Proceedings of the Twenty-eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 279–287 (2009)

  112. Zhang, W., Lin, X., Zhang, Y., Wang, W., Yu, J.X.: Probabilistic skyline operator over sliding windows. In: 2009 IEEE 25th International Conference on Data Engineering, pp. 1060–1071. IEEE (2009)

  113. Su, H.Z., Wang, E.T., Chen, A.L.: Continuous probabilistic skyline queries over uncertain data streams. In: International Conference on Database and Expert Systems Applications, pp. 105–121. Springer (2010)

  114. Arefin, M.S., Morimoto, Y.: Skyline sets queries for incomplete data. AIRCC’s Int. J. Comput. Sci. Inform. Technol. 4(5), 67–80 (2016)

    Google Scholar 

  115. Bharuka, R., Kumar, P.S.: Finding skylines for incomplete data. In: Proceedings of the Twenty-Fourth Australasian Database Conference-Volume 137, pp. 109–117 (2013)

  116. Wang, Y., Shi, Z., Wang, J., Sun, L., Song, B.: Skyline preference query based on massive and incomplete dataset. IEEE Access 5, 3183–3192 (2017)

    Article  Google Scholar 

  117. Miao, X., Gao, Y., Zheng, B., Chen, G., Cui, H.: Top-k dominating queries on incomplete data. IEEE Trans. Knowl. Data Eng. 28(1), 252–266 (2015)

    Article  Google Scholar 

  118. Zhang, W., Li, A., Cheema, M.A., Zhang, Y., Chang, L.: Probabilistic n-of-n skyline computation over uncertain data streams. World Wide Web 18(5), 1331–1350 (2015)

    Article  Google Scholar 

  119. Miao, X., Gao, Y., Chen, G., Zhang, T.: k-dominant skyline queries on incomplete data. Inform. Sci. 367, 990–1011 (2016)

    Article  Google Scholar 

  120. Islam, M.S., Rahayu, W., Liu, C., Anwar, T., Stantic, B.: Computing influence of a product through uncertain reverse skyline. In: Proceedings of the 29th International Conference on Scientific and Statistical Database Management, pp. 1–12 (2017)

  121. Liu, C.-M., Pak, D., Ortiz Castellanos, A.E.: Priority-based skyline query processing for incomplete data. In: 25th International Database Engineering & Applications Symposium, pp. 204–211 (2021)

  122. Ding, L., Zhang, X., Zhang, H., Liu, L., Song, B.: Crowdsj: skyline-join query processing of incomplete datasets with crowdsourcing. IEEE Access 9, 73216–73229 (2021)

    Article  Google Scholar 

  123. Li, X., Wang, Y., Li, X., Wang, Y., Huang, R.: Parallelizing probabilistic streaming skyline operator in cloud computing environments. In: 2013 IEEE 37th Annual Computer Software and Applications Conference, pp. 84–89. IEEE (2013)

  124. Li, X., Wang, Y., Li, X., Wang, Y.: Parallel skyline queries over uncertain data streams in cloud computing environments. Int. J. Web Grid Serv. 10(1), 24–53 (2014)

    Article  Google Scholar 

  125. Koizumi, K., Inaba, M., Hiraki, K.: Efficient implementation of continuous skyline computation on a multi-core processor. In: 2015 ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE), pp. 52–55. IEEE (2015)

  126. De Matteis, T., Di Girolamo, S., Mencagli, G.: A multicore parallelization of continuous skyline queries on data streams. In: European Conference on Parallel Processing, pp. 402–413. Springer (2015)

  127. Montahaie, E., Ghafouri, M., Rahmani, S., Ghasemi, H., Bakhtiar, F.S., Zamanshoar, R., Jafari, K., Gavahi, M., Mirzaei, R., Ahmadzadeh, A., et al.: Efficient continuous skyline computation on multi-core processors based on manhattan distance. In: 2015 ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE), pp. 56–59. IEEE (2015)

  128. Islam, M.S., Liu, C., Rahayu, W., Anwar, T.: Q+ tree: An efficient quad tree based data indexing for parallelizing dynamic and reverse skylines. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pp. 1291–1300 (2016)

  129. Liu, J., Li, X., Ren, K., Song, J., Zhang, Z.: Parallel n-of-n skyline queries over uncertain data streams. In: International Conference on Database and Expert Systems Applications, pp. 176–184. Springer (2018)

  130. Liu, J., Li, X., Ren, K., Song, J.: Parallelizing uncertain skyline computation against n-of-n data streaming model. Concurr. Comput. 31(4), 4848 (2019)

    Article  Google Scholar 

  131. Li, X., Liu, J., Ren, K., Li, X., Ren, X., Deng, K.: Parallel k-dominant skyline queries over uncertain data streams with capability index. In: 2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS), pp. 1556–1563. IEEE (2019)

  132. Alami, K., Maabout, S.: A partitioning approach for skyline queries in presence of partial and dynamic orders. In: Transactions on Large-Scale Data-and Knowledge-Centered Systems XLIX, pp. 70–96. Springer (2021)

  133. Tai, L.K., Wang, E.T., Chen, A.L.: Finding the most profitable candidate product by dynamic skyline and parallel processing. Distrib. Parall. Databases 39, 1–30 (2021)

    Article  Google Scholar 

  134. Bøgh, K.S., Chester, S., Šidlauskas, D., Assent, I.: Template skycube algorithms for heterogeneous parallelism on multicore and gpu architectures. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 447–462 (2017)

Download references

Funding

Our research was entirely self-funded, and we did not receive any financial support or funding from external parties.

Author information

Authors and Affiliations

  1. LSA Laboratory, Aeronautical and Spatial Studies Institute, University Blida1, Ouled Yaïch, Algeria

    Walid Khames & Mohand Lagha

  2. LIAS Laboratory, ISAE-ENSMA, Poitiers, France

    Allel Hadjali

Authors
  1. Walid Khames
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Allel Hadjali
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mohand Lagha
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

PhD student Khames Walid designed the algorithm, implemented the program, analyzed the results, and prepared the manuscript. HadjAli Allel and Lagha Mohand as PhD supervisors reviewed the results and contributed to the manuscript corrections.

Corresponding author

Correspondence to Walid Khames.

Ethics declarations

Conflict of interest

We declare that the authors have no Conflict of interest as defined by Springer, or other interests that might be perceived to influence the results and/or discussion reported in this paper.

Ethical approval

for PRSS Algorithm Development and Validation Using Synthetic and Open-Source Real-World Data. Research Objective: The objective of this study is to develop and validate a Skyline algorithm for processing streaming data. The research does not involve human or animal participants or the use of sensitive data. Instead, the algorithm was developed and validated using both synthetic data generated from the open-source skyline data generator software (http://pgfoundry.org/projects/randdataset) and real-world data available in a public repository under the Creative Commons license. Study Design: 1. Algorithm Development: The PRSS algorithm was developed using standard programming practices and techniques. The research team worked collaboratively to design, implement, and optimize the algorithm for processing streaming data. 2. Synthetic Data Generation: Synthetic data is generated using publicly available open-source software called the Standard Skyline Data Generator, which allows the creation of random data sets. This approach eliminates the need for any data collection involving human or animal participants. 3. Real-World Data Acquisition: The real-world data used for validation will be obtained from a public data repository with an open Creative Commons license. As such, no individual or private information will be involved in the study. Ethical Considerations: 1. Privacy and Data Usage: As there are no human or animal participants involved and the synthetic data is generated using open-source software, privacy concerns are not applicable in this research. 2. Compliance with Licensing Terms: The research team ensures full compliance with the licensing terms and conditions for using the real-world data available under the Creative Commons license. 4. Integrity and Transparency: The research team commits to conducting the study with integrity, transparency, and adherence to established scientific practices. Ethical Approval Process: 1. PhD student Khames Walid and the supervisors Allel Hadjali and Mohand Lagha prepared a comprehensive research proposal outlining the study design, data sources, privacy measures, and ethical considerations involved in the algorithm development and validation process. 2. The proposal was submitted to the ethics committee of the aeronautical institute of Blida for review. Given that the research does not involve human or animal participants or sensitive data, the ethics committee will focus on ensuring compliance with open-source software licensing terms. The Ethics Committee of the Aeronautical Institute of Blida has reviewed and approved our research. Since our study did not involve human participants, animals, or sensitive data, the committee ensured that all ethical principles and guidelines were followed throughout the research process. All authors involved in this research have provided their consent and agreement to publish the findings. 3. Upon approval, the research team proceeds with the algorithm development and validation process using the synthetic and open-source real-world data. 4. Research results are provided to the ethics committee to ensure continued adherence to ethical guidelines throughout the research.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Khames, W., Hadjali, A. & Lagha, M. Parallel continuous skyline query over high-dimensional data stream windows. Distrib Parallel Databases 42, 469–524 (2024). https://doi.org/10.1007/s10619-024-07443-7

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10619-024-07443-7

Keywords