Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Continuous monitoring of moving skyline and top-k queries

  • Regular Paper
  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

Given a set of criteria, an object o dominates another object \(o'\) if o is more preferable than \(o'\) according to every criterion. A skyline query returns every object that is not dominated by any other object. A top-k query returns k most preferred objects according to a given scoring function. In this paper, we study the problem of continuously monitoring moving skyline queries and moving top-k queries where one of the criteria is the distance between the objects and the moving query. We propose safe zone-based techniques to address the challenge of efficiently updating the results as the query moves. A safe zone is the area such that the results of a query remain unchanged as long as the query lies inside this area. Hence, the results are required to be updated only when the query leaves its safe zone. We present several non-trivial optimizations and propose an efficient algorithm for safe zone construction for both the skyline queries and top-k queries. Our techniques for the moving top-k queries are generic in the sense that these are immediately applicable to any top-k query as long as its scoring function is monotonic. Furthermore, we show that the proposed techniques can also be extended to monitor various other queries for different distance metrics. Our experiments demonstrate that the cost of our techniques is reasonably close to a lower bound cost and is several orders of magnitude lower than the cost of a naïve algorithm.

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
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

References

  1. Abeywickrama, T., Cheema, M.A., Khan, A.: K-SPIN: efficiently processing spatial keyword queries on road networks. IEEE TKDE 32, 983–997 (2019)

    Google Scholar 

  2. Abrishamchi, A., Ebrahimian, A., Tajrishi, M., Mariño, M.A.: Case study: application of multicriteria decision making to urban water supply. J. Water Resour. Plan. Manag. 131, 326–335 (2005)

    Article  Google Scholar 

  3. Adriyendi, M.: Multi-attribute decision making using simple additive weighting and weighted product in food choice (2015)

  4. Aurenhammer, F., Edelsbrunner, H.: An optimal algorithm for constructing the weighted voronoi diagram in the plane. Pattern Recognit. 17(2), 251–257 (1984)

    Article  MathSciNet  Google Scholar 

  5. Beliakov, G., Pradera, A., Calvo, T., et al.: Aggregation Functions: A Guide for Practitioners, vol. 221. Springer, Heidelberg

  6. Bohm, C., Ooi, B.C., Plant, C., Yan, Y.: Efficiently processing continuous k-NN queries on data streams. In: ICDE, pp. 156–165 (2007)

  7. Börzsönyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: ICDE, pp. 421–430 (2001)

  8. Brinkhoff, T.: A framework for generating network-based moving objects. GeoInformatica 6(2), 153–180 (2002)

    Article  Google Scholar 

  9. Cheema, M.A., Brankovic, L., Lin, X., Zhang, W., Wang, W.: Continuous monitoring of distance-based range queries. IEEE TKDE 23(8), 1182–1199 (2010)

    Google Scholar 

  10. Cheema, M.A., Brankovic, L., Lin, X., Zhang, W., Wang, W.: Multi-guarded safe zone: an effective technique to monitor moving circular range queries. In: ICDE (2010)

  11. Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: A safe zone based approach for monitoring moving skyline queries. In: EDBT, pp. 275–286 (2013)

  12. Cheema, M.A., Shen, Z., Lin, X., Zhang, W.: A unified framework for efficiently processing ranking related queries. In: EDBT, pp. 427–438 (2014)

  13. Chen, J., Zheng, J., Jiang, S., Qiu, X.: Distance-based continuous skylines on geo-textual data. In: Asia-Pacific Web Conference, pp. 228–240. Springer (2016)

  14. Cong, G., Jensen, C.S., Wu, D.: Efficient retrieval of the top-k most relevant spatial web objects. PVLDB 2(1), 337–348 (2009)

    Google Scholar 

  15. 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 

  16. Hsueh, Y., Zimmermann, R., Ku, W.: Efficient updates for continuous skyline computations. In: DEXA (2008)

  17. http://www.cs.fsu.edu/~lifeifei/SpatialDataset.htm

  18. Huang, W., Li, G., Tan, K.L., Feng, J.: Efficient safe-region construction for moving top-k spatial keyword queries. In: CIKM, pp. 932–941 (2012)

  19. Huang, Z., Lu, H., Ooi, B.C., Tung, A.K.H.: Continuous skyline queries for moving objects. TKDE 18, 1645–1658 (2006)

    Google Scholar 

  20. Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40(4), 11:1–11:58 (2008)

  21. Kang, J.M., Mokbel, M.F., Shekhar, S., Xia, T., Zhang, D.: Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors. In: ICDE (2007)

  22. Kossmann, D., Ramsak, F., Rost, S.: Shooting stars in the sky: an online algorithm for skyline queries. In: VLDB, pp. 275–286 (2002)

  23. Lai, C.C., Akbar, Z.F., Liu, C.M., Ta, V.D., Wang, L.C.: Distributed continuous range-skyline query monitoring over the internet of mobile things. IEEE Internet Things J. 6, 6652–6667 (2019)

    Article  Google Scholar 

  24. Lee, M.W., won Hwang, S.: Continuous skylining on volatile moving data. In: ICDE, pp. 1568–1575 (2009)

  25. Li, H., Yoo, J.: An efficient scheme for continuous skyline query processing over dynamic data set. In: BIGCOMP, pp. 54–59 (2014)

  26. Lin, X., Yuan, Y., Wang, W., Lu, H.: Stabbing the sky: efficient skyline computation over sliding windows. In: ICDE, pp. 502–513 (2005)

  27. Liu, J., Yang, J., Xiong, L., Pei, J., Luo, J.: Skyline diagram: finding the voronoi counterpart for skyline queries. In: ICDE, pp. 653–664 (2018)

  28. Lu, H., Zhou, Y., Haustad, J.: Continuous skyline monitoring over distributed data streams. In: SSDBM (2010)

  29. Mateo, J.R.S.C.: Weighted sum method and weighted product method. In: Multi criteria analysis in the renewable energy industry, pp. 19–22. Springer (2012)

  30. Mouratidis, K., Bakiras, S., Papadias, D.: Continuous monitoring of top-k queries over sliding windows. In: ACM SIGMOD (2006)

  31. Nutanong, S., Zhang, R., Tanin, E., Kulik, L.: The v*-diagram: a query-dependent approach to moving knn queries. PVLDB 1, 1095–1106 (2008)

    Google Scholar 

  32. Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, Hoboken (1999)

    MATH  Google Scholar 

  33. Papadias, D., Tao, Y., Fu, G., Seeger, B.: An optimal and progressive algorithm for skyline queries. In: SIGMOD (2003)

  34. Papapetrou, O., Garofalakis, M.: Monitoring distributed fragmented skylines. DAPD 36(4), 675–715 (2018)

    Google Scholar 

  35. Qi, J., Zhang, R., Jensen, C.S., Ramamohanarao, K., He, J.: Continuous spatial query processing: a survey of safe region based techniques. ACM Comput. Surv. (CSUR) 51(3), 64 (2018)

    Google Scholar 

  36. Shen, Z., Cheema, M.A., Lin, X.: Loyalty-based selection: retrieving objects that persistently satisfy criteria. In: CIKM, pp. 2189–2193 (2012)

  37. Shen, Z., Cheema, M.A., Lin, X., Zhang, W., Wang, H.: Efficiently monitoring top-k pairs over sliding windows. In: ICDE, pp. 798–809 (2012)

  38. Shen, Z., Cheema, M.A., Lin, X., Zhang, W., Wang, H.: A generic framework for top-k pairs and top-k objects queries over sliding windows. IEEE TKDE 26, 1349–1366 (2014)

    Google Scholar 

  39. Shi, C., Qin, X., Wang, L.: Continuous skyline queries for moving objects in road networks. J. Softw. 10, 190–200 (2015)

    Article  Google Scholar 

  40. Tan, K.L., Eng, P.K., Ooi, B.C.: Efficient progressive skyline computation. In: VLDB, pp. 301–310 (2001)

  41. Tang, Y., Chen, S.: Supporting continuous skyline queries in dynamically weighted road networks. Math. Probl. Eng. 10.1155/2018/6749650 (2018)

  42. Wang, M., Liu, S., Wang, S., Lai, K.K.: A weighted product method for bidding strategies in multi-attribute auctions. J. Syst. Sci. Complex. 23, 194–208 (2010)

    Article  MathSciNet  Google Scholar 

  43. Wu, D., Yiu, M.L., Jensen, C.S., Cong, G.: Efficient continuously moving top-k spatial keyword query processing. In: ICDE, pp. 541–552 (2011)

  44. Wu, P., Agrawal, D., Egecioglu, Ö., Abbadi, A.E.: Deltasky: optimal maintenance of skyline deletions without exclusive dominance region generation. In: ICDE (2007)

  45. Xia, T., Zhang, D.: Continuous reverse nearest neighbor monitoring. In: ICDE, p. 77 (2006)

  46. Yang, S., Cheema, M.A., Lin, X., Zhang, Y., Zhang, W.: Reverse k nearest neighbors queries and spatial reverse top-k queries. VLDB J. 26(2), 151–176 (2017)

    Article  Google Scholar 

  47. Zavadskas, E.K., Antucheviciene, J., Hajiagha, S.H.R., Hashemi, S.S.: Extension of weighted aggregated sum product assessment with interval-valued intuitionistic fuzzy numbers (WASPAS-IVIF). Appl. Soft Comput. 24, 1013–1021 (2014)

    Article  Google Scholar 

  48. Zhang, J., Zhu, M., Papadias, D., Tao, Y., Lee, D.L.: Location-based spatial queries. In: SIGMOD (2003)

  49. Zheng, J., Jiang, S., Chen, J., Yu, W., Zhang, S.: Dynamic skyline maintaining strategies for moving query points in road networks. J. Internet Technol. 20(5), 1359–1369 (2019)

    Google Scholar 

  50. Zhong, R., Li, G., Tan, K.L., Zhou, L.: G-tree: an efficient index for knn search on road networks. In: CIKM, pp. 39–48 (2013)

Download references

Acknowledgements

Muhammad Aamir Cheema is supported by Australian Research Council (ARC) FT180100140 and DP180103411. Xuemin Lin is supported by ARC DP180103096 and DP200101338. Wenjie Zhang is supported by ARC DP180103096 and DP200101116. Ying Zhang is supported by ARC FT170100128 and DP180103096.

Author information

Authors and Affiliations

  1. Brawijaya University, Malang, Indonesia

    Arif Hidayat

  2. Monash University, Melbourne, Australia

    Arif Hidayat & Muhammad Aamir Cheema

  3. University of New South Wales, Kensington, Australia

    Xuemin Lin & Wenjie Zhang

  4. University of Technology Sydney, Ultimo, Australia

    Ying Zhang

Authors
  1. Arif Hidayat
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Muhammad Aamir Cheema
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xuemin Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wenjie Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ying Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Muhammad Aamir Cheema.

Additional information

Publisher's Note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hidayat, A., Cheema, M.A., Lin, X. et al. Continuous monitoring of moving skyline and top-k queries. The VLDB Journal 31, 459–482 (2022). https://doi.org/10.1007/s00778-021-00702-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00778-021-00702-4

Keywords

Search

Navigation