Skip to main content
SpringerLink
Log in

Optimized skyline queries on road networks using nearest neighbors

  • Original Article
  • Published:
Personal and Ubiquitous Computing Aims and scope Submit manuscript

Abstract

Skyline queries are used with data extensive applications, such as mobile location-based services, to support multi-criteria decision-making and to prune the data space by returning the most “interesting” data points. Most interesting data points are the points, which are not dominated by any other point. Spatial network skyline query is a subset of the skyline query problem where data points are nodes in a road network and the attributes of the data points are network distance relative to a set of query points. Spatial network skyline query’s problem is the need to calculate the attributes with an expensive distance calculation operation. Previous works (Deng et al. Proceedings of the 23th international conference on data engineering, 796–805, 2007), Sharifzadeh et al. Proceedings of the 32nd international conference on very large databases, 751–762, 2009) that addressed this problem involved extensive network distance calculation between the query points and data points. A new algorithm that requires a remarkably less number of network distance calculations is proposed in this work. Our approach uses a progressive nearest neighbor algorithm to minimize the set of candidates then evaluates those candidates by only comparing them to a subset of discovered skyline points. Experiments showed the effectiveness of our algorithm compared to previous works.

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

Access this article

Log in via an institution

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

Similar content being viewed by others

References

  1. Börzsönyi S, Kossmann D, Stocker K (2001) The skyline operator. In: Proceedings of the 17th international conference on data engineering, pp 421–430

  2. Bhattacharya B, Bishnu A, Cheong O, Das S, Karmakar A, Snoeyink J (2010) Computation of non-dominated points using compact Voronoi diagrams. Walcom Algo Comput LNCS 5942:82–93

    Article  Google Scholar 

  3. Chen L, Lian X (2008) Dynamic skyline queries in metric spaces. In: Proceedings of the 11th international conference on extending database technology: advances in database technology, pp 333–343

  4. Deng K, Zhou X, Shen HT (2007) Multi-source skyline query processing in road networks. In: Proceedings of the 23th international conference on data engineering, pp 796–805

  5. Kolahdouzan MR, Shahabi C (2004) Voronoi-based K nearest neighbor search for spatial network databases. In: Proceedings of the 30th international conference on very large data bases, pp 840–851

  6. Kossmann D, Ramsak F, Rost S (2002) Shooting stars in the sky: an online algorithm for skyline queries. In: Proceedings of the 28th international conference on very large data bases, pp 275–286

  7. Lee K, Zheng B, Li H, Lee W (2007) Approaching the skyline in Z order. In: Proceedings of the 33rd international conference on very large data bases, pp 23–27

  8. Papadias D, Tao Y, Fu G, Seeger B (2003) An optimal and progressive algorithm for skyline queries. In: Proceedings of the 2003 ACM SIGMOD international conference on management of data, pp 467–478

  9. Safar M (2008) Spatial queries in road networks based on PINE. J Univ Comput Sci 14(4):590–611

    Google Scholar 

  10. Safar M (2005) K nearest neighbour search in navigation systems. Mob Inf Syst 1(3):207–224

    Google Scholar 

  11. Sharifzadeh M, Shahabi C (2006) The spatial skyline queries. In: Proceedings of the 32nd international conference on very large databases, pp 751–762

  12. Sharifzadeh M, Shahabi C, Kazemi L (2009) Processing spatial skyline queries in both vector spaces and spatial network databases. ACM Trans Database Syst 14(3)

  13. Son W, Lee M, Ahn H, Hwang S (2009) Spatial skyline queries: an efficient geometric algorithm. Adv Spatial Temp Databases LNCS 5644:247–264

    Article  Google Scholar 

  14. Tan K, Eng P, Ooi BC (2001) Efficient progressive skyline computation. In: Proceedings of the 27th international conference on very large data bases, pp 301–310

  15. Zheng B, Lee K, Lee W (2008) Location-dependent skyline query. In: Proceedings of the 9th international conference on mobile data management, pp 148–155

  16. Zou L, Chen L, Özsu MT, Zhao D (2010) Dynamic skyline in large graphs. Database Syst Adv App LNCS 5982:62–78

    Article  Google Scholar 

  17. Okabe A, Boots B, Sugihara K, Chiu SN (2000) Spatial tessellations, concepts and applications of Voronoi diagrams, 2nd edn. Wiley

  18. Fagin R (1996) Combining Fuzzy Information from Multiple Systems. In: Proceedings ACM SIGMOD/SIGACT conference on principle of database systems (PODS), pp 216–226

  19. Xuan K, Zhao G, Taniar D, Srinivasan B, Safar M, Gavrilova M (2009) Network Voronoi diagram based range search. IEEE 23rd international conference on advanced information networking and applications (AINA), pp 741–748

  20. Zhao G, Xuan K, Taniar D, Safar M, Gavrilova M, Srinivasan B (2009) Multiple object types KNN search using network Voronoi diagram. In: Proceedings of IEEE international conference on computational science and its applications (ICCSA), 5593/2009, pp 819–834

  21. Zhao G, Taniar D, Rahayu W, Safar M, Srinivasan B (2010) Path branch points in mobile navigation. In: Proceedings of the 8th international conference on advances in mobile computing & multimedia (MoMM)

  22. Xuan K, Taniar D, Safar M, Srinivasan B (2010) Time constrained range search queries over moving objects in road networks. In: Proceedings of the 12th international conference on information integration and web-based applications & services (iiWAS)

  23. Al-Khalidi H, Taniar D, Safar M (2011) Approximate static and continuous range search in mobile navigation. 5th ACM international conference on ubiquitous information management and communication (ICUIMC)

  24. Safar M (2008) Group K-nearest neighbour’s queries in spatial network databases. J Geo Sys 10(4):407–416, published by Springer

    Google Scholar 

  25. Zhao G, Xuan K, Rahayu W, Taniar D, Safar M, Gavrilova M, Srinivasan B (2009) Voronoi based continuous k nearest neighbor search in mobile navigation. IEEE Trans Ind Electron (IEEE TIE) 56(12)

  26. Xuan K, Zhao G, Taniar D, Srinivasan B, Safar M, Gavrilova M (2009) continuous range search based on network Voronoi diagram. Int J Grid Utility Comput (IJGUC) 1(4), Inderscience Publisher

  27. Xuan K, Zhao G, Taniar D, Safar M, Srinivasan B (2009) Voronoi-based multi-level range search in mobile navigation. Int J Multimed Tools App, Springer. doi:10.1007/s11042-010-0498-y, online first

  28. Xuan K, Zhao G, Taniar D, Rahayu W, Safar M, Srinivasan B (2011) Voronoi-based range and continuous range query processing in mobile databases. Pub J Comput Syst Sci (JCSS), Elsevier Science 77(4):637–651

    Google Scholar 

  29. Jayaputera J, Taniar D (2005) Data retrieval for location-dependent queries in a multi-cell wireless environment. Mob Inf Syst 1(2):91–108

    Google Scholar 

  30. Borgy Waluyo A, Srinivasan B, Taniar D (2005) Research in mobile database query optimization and processing. Mob Inf Syst 1(4):225–252

    Google Scholar 

  31. Xuan K, Zhao G, Taniar D, Srinivasan B (2008) Continuous range search query processing in mobile navigation. In: Proceedings of the 14th international conference on parallel and distributed systems (ICPADS 2008), IEEE, pp 361–368

  32. Waluyo BA, Srinivasan B, Taniar D (2005) Research on location-dependent queries in mobile databases. Int J Comput Syst Sci Eng 20(2)

  33. Thai Tran Q, Taniar D, Safar M (2010) Bichromatic reverse nearest-neighbor search in mobile systems. IEEE Syst J 4(2):230–242

    Article  Google Scholar 

  34. Waluyo BA, Taniar D, Rahayu W, Srinivasan B (2009) Mobile service oriented architectures for NN-queries. J Net Comput App 32(2):434–447

    Article  Google Scholar 

  35. Safar M, Ebrahimi D, Taniar D (2009) Voronoi-based reverse nearest neighbor query processing on spatial networks. Multimed Syst 15(5):295–308

    Article  Google Scholar 

  36. Thai Tran Q, Taniar D, Safar M (2009) Reverse k nearest neighbor and reverse farthest neighbor search on spatial networks. Trans Large Scale Data Knowl Cent Syst 5740(2009):353–372

    Article  Google Scholar 

  37. Zhao G, Xuan K, Taniar D, Srinivasan B (2010) Look ahead continuous KNN mobile query processing. Comput Syst Sci Eng 25(3):205–217

    Google Scholar 

  38. Zhao G, Xuan K, Taniar D, Srinivasan B (2008) Incremental k-nearest-neighbor search on road networks. J Int Net 9(4):455–470

    Article  Google Scholar 

  39. Borgy Waluyo A, Taniar D, Rahayu W, Srinivasan B (2011) Mobile broadcast services with MIMO antennae in 4G wireless networks. World Wide Web J. doi:10.1007/s11280-011-0113-9, online for early access

  40. Zhao G, Xuan K, Rahayu W, Taniar D, Safar M, Gavrilova M, Srinivasan B (2010) Voronoi-based continuous k nearest neighbor search in mobile navigation. IEEE Trans Ind Electron. doi:10.1109/TIE.2009.2026372, online for early access

  41. Waluyo B.A, Rahayu W, Taniar D, Srinivasan B (2010) A novel structure and access mechanism for mobile broadcast data in digital ecosystems. IEEE Trans Ind Electron. doi:10.1109/TIE.2009.2035457, online for early access

  42. Taniar D, Safar M, Thai Tran Q, Rahayu W, Hyuk Park J (2010) Spatial network RNN queries in GIS. Comput J. doi:10.1093/comjnl/bxq068, online for early access

  43. Xuan K, Zhao G, Taniar D, Rahayu W, Safar M, Srinivasan B (2010) Voronoi-based range and continuous range query processing in mobile databases. J Comput Syst Sci. doi:10.1016/j.jcss.2010.02.005, online for early access

  44. Xuan K, Zhao G, Taniar D, Safar M, Srinivasan B (2010) Voronoi-based multi-level range search in mobile navigation. Multimed Tools App. doi:10.1007/s11042-010-0498-y, online for early access

  45. Mammeri Z, Morvan F, Hameurlain A, Marsit N (2009) Location-dependent query processing under soft real-time constraints. Mob Inf Syst 5(3):205–232

    Google Scholar 

  46. Borrego-Jaraba F, Luque Ruiz I, Ángel Gómez-Nieto M (2010) A NFC-based pervasive solution for city touristic surfing. Pers Ubiquit Comput. doi:10.1007/s00779-010-0364-y, online for early access

  47. Rashid O, Coulton P, Edwards R (2008) Providing location based information/advertising for existing mobile phone users. Pers Ubiquit Comput 12(1):3–10

    Article  Google Scholar 

  48. Choi J, Jang B, Kim G (2010) Organizing and presenting geospatial tags in location-based augmented reality. Pers Ubiquit Comput. doi:10.1007/s00779-010-0343-3, online for early access

  49. Kenteris M, Gavalas D, Economou D (2009) An innovative mobile electronic tourist guide application. Pers Ubiquit comput 13(2):103–118

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Kuwait University, Kuwait City, Kuwait

    Maytham Safar & Dalal El-Amin

  2. Monash University, Melbourne, Australia

    David Taniar

Authors
  1. Maytham Safar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dalal El-Amin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Taniar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Maytham Safar.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Safar, M., El-Amin, D. & Taniar, D. Optimized skyline queries on road networks using nearest neighbors. Pers Ubiquit Comput 15, 845–856 (2011). https://doi.org/10.1007/s00779-011-0371-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00779-011-0371-7

Keywords

Search

Navigation