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

Advertisement

Springer Nature Link
Log in

Spatial query processing in road networks for wireless data broadcast

  • Published:
Wireless Networks Aims and scope Submit manuscript

Abstract

Recently, wireless broadcast environments have attracted significant attention due to its high scalability to broadcast information to a large number of mobile subscribers. It is especially a promising and desirable dissemination method for the heavily loaded environment where a great number of the same type of requests are sent from the users. There have been many studies on processing spatial queries via broadcast model recently. However, not much attention is paid to the spatial queries in road networks on wireless broadcast environments. In this paper, we focus on three common types of spatial queries, namely, k nearest neighbor (kNN) queries, range queries and reverse nearest neighbor (RNN) queries in spatial networks for wireless data broadcast. Specially, we propose a novel index for spatial queries in wireless broadcast environments (ISW). With the reasonable organization and the effectively pre-computed bounds, ISW provides a powerful framework for spatial queries. Furthermore, efficient algorithms are designed to cope with kNN, range and RNN queries separately based on ISW. The search space can be obviously reduced and subsequently the client can download as less as possible data for query processing, which can conserve the energy while not significantly influence the efficiency. The detailed theory analysis of cost model and the experimental results are presented for verifying the efficiency and effectiveness of ISW and our methods.

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
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25

Similar content being viewed by others

References

  1. Zheng, B., Xu, J., Lee, W.-C., & Lee, L. (2006). Grid-partition index: A hybrid method for nearest-neighbor queries in wireless location-based services. Journal on Very Large Data Bases, 15, 21–39.

    Article  Google Scholar 

  2. Park, K., Choo, H., & Valduriez, P. (2010). A scalable energy-efficient continuous nearest neighbor search in wireless broadcast systems. Wireless Networks, 16, 1011–1031.

    Article  Google Scholar 

  3. Lin, L.-F., Chen, C.-C., & Lee, C. (2010). Benefit-oriented data retrieval in data broadcast environments. Wireless Networks, 16(1):1–15.

    Article  MathSciNet  Google Scholar 

  4. Gedik, B., Singh, A., & Liu, L. (2004). Energy efficient exact knn search in wireless broadcast environments. In GIS (pp. 137–146).

  5. Zheng, B., Lee, W.-C., Lee, K., Lee, D. L., & Shao, M. (2009). A distributed spatial index for error-prone wireless data broadcast. The VLDB Journal, 18, 959–986.

    Article  Google Scholar 

  6. Ambient information network. http://www.ambientdevices.com/cat/index.html.

  7. Zheng, B., Lee, W.-C., Lee, & D. L. (2004). Spatial queries in wireless broadcast systems. Wireless Networks, 10, 723–736.

    Article  Google Scholar 

  8. Zhang, X., Lee, W.-C., Mitra, P., & Zheng, B. (2008). Processing transitive nearest-neighbor queries in multi-channel access environments. In Proceedings of EDBT (pp. 452–463).

  9. Zheng, B., Lee, W.-C., Lee, & D. L. (2007). On searching continuous k nearest neighbors in wireless data broadcast systems. IEEE Transactions on Mobile Computing, 6, 748–761.

    Article  Google Scholar 

  10. Shahabi, C., Kolahdouzan, M. R., & Sharifzadeh, M. (2002). A road network embedding technique for k-nearest neighbor search in moving object databases. In GIS (pp. 94–100).

  11. Papadias, D., Zhang, J., Mamoulis, N., & Tao, Y. (2003). Query processing in spatial network databases. In VLDB (pp. 802–813).

  12. Kolahdouzan, M., & Shahabi, C. (2004). Voronoi-based k nearest neighbor search for spatial network databases. In VLDB (pp. 840–851).

  13. Samet, H., Sankaranarayanan, J., & Alborzi, H. (2008). Scalable network distance browsing in spatial databases. In SIGMOD (pp. 43–54).

  14. Kellaris, G., & Mouratidis, K. (2010). Shortest path computation on air indexes. In VLDB (pp. 747–757).

  15. Anticaglia, S., Barsi, F., Bertossi, A., Lamele, L., & Pinotti, M. (2008). Efficient heuristics for data broadcasting on multiple channels. Wireless Networks, 14(2), 219–231.

    Article  Google Scholar 

  16. Imielinski, T., Viswanathan, S., & Badrinath, B. (1997). Data on air: Organization and access. IEEE Transactions on Knowledge and Data Engineering, 9, 353–372.

    Article  Google Scholar 

  17. Mouratidis, K., Bakiras, S., & Papadias, D. (2009). Continuous monitoring of spatial queries in wireless broadcast environments. IEEE Transactions on Mobile Computing, 8, 1297–1311.

    Article  Google Scholar 

  18. Lee, W.-C., & Zheng, B. (2005). Dsi: A fully distributed spatial index for location-based wireless broadcast services. In ICDCS (pp. 349–358).

  19. Xu, J., Lee, W.-C., & Tang, X. (2004). Exponential index: a parameterized distributed indexing scheme for data on air. In Proceedings of MobiSys (pp. 153–164).

  20. Shen, J.-H., & Chang, Y.-I. (2008). An efficient nonuniform index in the wireless broadcast environments. Journal of Systems and Software, 81, 2091–2103.

    Article  Google Scholar 

  21. Zhong, J., Wu, W., Shi, Y., & Gao, X. (2011). Energy-efficient tree-based indexing schemes for information retrieval in wireless data broadcast. In Proceedings of DASFAA (pp. 335–351).

  22. Yiu, M. L., Papadias, D., Mamoulis, N., & Tao, Y. (2006). Reverse nearest neighbors in large graphs. IEEE Transactions on Knowledge and Data Engineering, 18(4), 540–553.

    Article  Google Scholar 

  23. Möhring, R., Schilling, H., Schütz, B., Wagner, D., & Willhalm, T. (2006). Partitioning graphs to speedup dijkstra’s algorithm. Journal of Experimental Algorithmics, 11, 1–29.

    Google Scholar 

  24. Xiao, X., Yao, B., & Li, F. (2011). Optimal location queries in road network databases. In ICDE (pp. 804–815).

Download references

Acknowledgments

This work was supported in part by the the National Natural Science Foundation of China under grants Nos. 60933001, 61003058, and the Fundamental Research Funds for the Central Universities under grants No.N100604014 and No. N110604001.

Author information

Authors and Affiliations

  1. College of Information Science and Engineering, Northeastern University, Shenyang, 110819, China

    Yanqiu Wang, Chuanfei Xu, Yu Gu, Mo Chen & Ge Yu

Authors
  1. Yanqiu Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chuanfei Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yu Gu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mo Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ge Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yanqiu Wang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, Y., Xu, C., Gu, Y. et al. Spatial query processing in road networks for wireless data broadcast. Wireless Netw 19, 477–494 (2013). https://doi.org/10.1007/s11276-012-0479-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-012-0479-3

Keywords

Search

Navigation