[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Hierarchical Grid Index (HGI), spatial queries in wireless data broadcasting

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

Abstract

The main requirements for spatial query processing via mobile terminals include rapid and accurate searching and low energy consumption. Most location-based services (LBSs) are provided using an on-demand method, which is suitable for light-loaded systems where contention for wireless channels and server processing is not severe. However, as the number of users of LBSs increases, performance deteriorates rapidly since the servers’ capability to process queries is limited. Furthermore, the response time of a query may significantly increase with the concentration of users’ queries in a server at the same time. That is because the server has to check the locations of users and potential objects for the final result and then individually send answers to clients via a point-to-point channel. At this time, an inefficient structure of spatial index and searching algorithm may incur an extremely large access latency.

To address this problem, we propose the Hierarchical Grid Index (HGI), which provides a light-weight sequential location-based index structure for efficient LBSs. We minimize the index size through the use of hierarchical location-based identifications. And we support efficient query processing in broadcasting environments through sequential data transfer and search based on the object locations. We also propose Top-Down Search and Reduction-Counter Search algorithms for efficient searching and query processing. HGI has a simple structure through elimination of replication pointers and is therefore suitable for broadcasting environments with one-dimensional characteristics, thus enabling rapid and accurate spatial search by reducing redundant data. Our performance evaluation shows that our proposed index and algorithms are accurate and fast and support efficient spatial query processing.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Algorithm 1
Fig. 7
Fig. 8
Algorithm 2
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

Similar content being viewed by others

Notes

  1. The average duration for getting to the next index segment is called the probe wait [5].

  2. Access time is the time elapsed from the time a client requests data to the point when all the required data is downloaded by the client [4].

  3. Tuning time is the amount of time spent by a client listening to the channel. This allows determining the power consumed by the client to retrieve the required data [4].

  4. The R-tree is a classical spatial index structure. The basic idea is to approximate a spatial object with a minimal bounding rectangle (MBR) and to index the MBRs recursively [26, 27].

  5. Even until recently, DSI and ESS have been a representative study of index for supporting spatial query processing in wireless broadcast environments. In this paper, performance assessment was conducted on DSS that assumed the most similar environments as the proposed technique.

  6. Each index table in the DSI and ESS has the next pointers that increase exponentially within the range of N, the total r amount of data. For example, if N=1024, a single index table has 9 next pointers of 1, 2, 4, 8, and up to 1024.

  7. The leaf grid node refers to the node that is located at the lowest place in the tree structure. That is, the node does not have any more child grid nodes.

  8. The exponential value allows indexing pointers to be exponentially increased at any base value e. For example, if the number of objects and the value of e are set to 8 and 2, respectively, a data item 0 has four forward pointers such as 1(20), 2(21), 4(22), and 8(23).

References

  1. Acharya, S., Alonso, R., Franklin, M., Zdonik, S.: Broadcast disks: data management for asymmetric communications environments. In: Proceedings of ACM SIGMOD Conference on Management of Data (SIGMOD’95), May 1995, pp. 199–210 (1995)

    Google Scholar 

  2. Datta, A., Celik, A., Kim, J.K., VanderMeer, D., Kumar, V.: Adaptive broadcast protocols to support power conservation retrieval by mobile users. In: Proceedings of IEEE International Conference Data Engineering (ICDE’97), April 1997, pp. 124–133 (1997).

    Chapter  Google Scholar 

  3. Datta, A., VanderMeer, D.E., Celik, A., Kumar, V.: Broadcast protocols to support efficient retrieval from databases by mobile users. ACM Trans. Database Syst. 24(1), 1–79 (1999)

    Article  Google Scholar 

  4. Imielinski, T., Viswanathan, S., Badrinath, B.R.: Energy efficiency indexing on air. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, May 1994, pp. 25–36 (1994)

    Google Scholar 

  5. Imielinski, T., Viswanathan, S., Badrinath, B.R.: Data on air—organization and access. IEEE Trans. Knowl. Data Eng. 9(3), 353–372 (1997)

    Article  Google Scholar 

  6. Shanmugasundaram, J., Nithrakashyap, A., Sivasankaran, R.M., Ramamritham, K.: Efficient concurrency control for broadcast environments. In: Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD’99), June 1999, pp. 85–96 (1999)

    Google Scholar 

  7. Zheng, B., Lee, D.L.: Information dissemination via wireless broadcast. Commun. ACM 48(5), 105–110 (2005)

    Article  Google Scholar 

  8. Zheng, B., Xu, J., Lee, W.-C., Lee, D.L.: Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services. VLDB J. 15(1), 21–39 (2006)

    Article  Google Scholar 

  9. Lee, K.C.K., Lee, W.-C., Winter, J., Zheng, B., Xu, J.: CS cache engine: data access accelerator for location-based service in mobile environments. In: Proc. of Special Interest Group on Management of Data (SIGMOD), pp. 787–789 (2006)

    Google Scholar 

  10. Ku, W., Zimmermann, R., Wang, H.: Location-based spatial query processing in wireless broadcast environments. IEEE Trans. Mob. Comput. 7(6), 778–791 (2008)

    Article  Google Scholar 

  11. Mouratidis, K., Bakiras, S., Papadias, D.: Continuous monitoring of spatial queries in wireless broadcast environments. IEEE Trans. Mob. Comput. 8(10), 1297–1311 (2009)

    Article  Google Scholar 

  12. Park, K., Choo, H.: Energy-efficient data dissemination schemes for nearest neighbor query processing. IEEE Trans. Comput. 56(6), 754–768 (2007)

    Article  MathSciNet  Google Scholar 

  13. Xu, J., Zheng, B., Lee, W.-C., Lee, D.L.: Energy efficient index for querying location-dependent data in mobile broadcast environments. In: Proc. of ICDE, pp. 239–250 (2003)

    Google Scholar 

  14. Zheng, B., Lee, W.-C., Lee, D.L.: On searching continuous k nearest neighbors in wireless data broadcast systems. IEEE Trans. Mob. Comput. 6(7), 748–761 (2007)

    Article  Google Scholar 

  15. Tao, Y., Papadias, D., Shen, Q.: Continuous nearest neighbor search. In: Proc. of VLDB, pp. 287–298 (2002)

    Google Scholar 

  16. Park, K., Choo, H., Valduriez, P.: A scalable energy-efficient continuous nearest neighbor search in wireless broadcast systems. Wirel. Netw. 16(4), 1011–1031 (2010)

    Article  Google Scholar 

  17. Hu, Q., Lee, W.-C., Lee, D.L.: Power conservative multi-attribute queries on data broadcast. In: Proc. Int’l Conf. Data Eng. (ICDE’00), pp. 157–166 (2000)

    Chapter  Google Scholar 

  18. Hambrusch, S.E., Liu, C.-M., Aref, W., Prabhakar, S.: Query processing in broadcasted spatial index trees. In: Proc. of Symposium on Spatial and Temporal Databases (SSTD), pp. 502–521 (2001)

    Google Scholar 

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

    Chapter  Google Scholar 

  20. Xuan, P., Sen, S., Gonzalez, O., Fernandez, J., Ramamritham, K.: Broadcast on demand: efficient and timely dissemination of data in mobile environments. In: Proc. of IEEE Real Time Technology and Applications Symposium, pp. 38–48 (1997)

    Chapter  Google Scholar 

  21. Liu, C.-M., Lin, K.-F.: Disseminating dependent data in wireless broadcast environments. Distrib. Parallel Databases 22(1), 1–25 (2007)

    Article  Google Scholar 

  22. Nicopolitidis, P., Papadimitriou, G.I., Pomportsis, A.S.: Exploiting locality of demand to improve the performance of wireless data broadcasting. IEEE Trans. Veh. Technol. 55(4), 1347–1361 (2006)

    Article  Google Scholar 

  23. Wang, H., Zimmermann, R.: Processing of continuous location-based range queries on moving objects in road networks. IEEE Trans. Knowl. Data Eng. 23(7), 1065–1078 (2011)

    Article  Google Scholar 

  24. Zhang, W., Yang, X., Wu, W., Xiang, G.: An optimized query index method based on R-tree. In: Proc. of International Joint Conference on Computational Sciences and Optimization, pp. 1007–1011 (2011)

    Google Scholar 

  25. Roussopoulos, N., Kelley, F.V.S.: Nearest neighbor queries. In: Proc. of SIGMOD, pp. 71–79 (1995)

    Google Scholar 

  26. Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proc. of Special Interest Group on Management of Data (SIGMOD), pp. 47–57 (1984)

    Google Scholar 

  27. Jagadish, H.V., Ooi, B.C., Vu, Q.H., Zhang, R., Zhou, A.: VBI-tree: a peer-to-peer framework for supporting multi-dimensional indexing schemes. In: Proc. of International Conference on Data Engineering (ICDE), p. 34 (2006)

    Google Scholar 

  28. Ku, W.-S., Zimmermann, R., Wan, C.-N., Wang, H.: MAPLE: a mobile scalable P2P nearest neighbor query system for location-based services. In: Proc. of International Conference on Data Engineering (ICDE), p. 160 (demo) (2006)

    Google Scholar 

  29. Lee, W.-C., Zheng, B.: DSI: a fully distributed spatial index for location-based wireless broadcast services. In: Proc. of ICDCS, Columbus, USA, 6–10 June 2005, pp. 349–358 (2005)

    Google Scholar 

  30. Zheng, B., Lee, W.-C., Lee, K., Lee, D., Shao, M.: A distributed spatial index for error-prone wireless data broadcast. VLDB J. 18(4), 959–986 (2009)

    Article  Google Scholar 

  31. Gedik, B., Singh, A., Liu, L.: Energy efficient exact kNN search in wireless broadcast environments. In: Proc. Ann. ACM Int’l Workshop Geographic Information Systems (GIS’04), pp. 137–146 (2004)

    Chapter  Google Scholar 

  32. Park, K., Valduriez, P., Choo, H.: Mobile continuous nearest neighbor queries on air. In: Proc. of ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS), p. 65 (2008)

    Google Scholar 

  33. Camp, T., Boleng, J., Davies, V.: A survey of mobility models for ad hoc network research. Wirel. Commun. Mob. Comput. 2(5), 483–502 (2002)

    Article  Google Scholar 

  34. Mouratidis, K., Bakiras, S., Papadias, D.: Continuous monitoring of spatial queries in wireless broadcast environments. IEEE Trans. Mob. Comput. 8(10), 1297–1311 (2009)

    Article  Google Scholar 

  35. Chowdhury, P., Sarkar, S., Reaz, A.: Comparative cost study of broadband access technologies. In: Proc. of Advanced Networks and Telecommunication Systems, pp. 1–3 (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Electrical Electronics and Information Engineering, Wonkwang University, Iksan-Shi, Chunrabuk-do, 570-749, Republic of Korea

    Kwangjin Park

  2. INRIA and LIRMM, 161 rue Ada, 34392, Montpellier Cedex 5, France

    Patrick Valduriez

Authors
  1. Kwangjin Park
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Patrick Valduriez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kwangjin Park.

Additional information

Communicated by Divyakant Agrawal.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Park, K., Valduriez, P. A Hierarchical Grid Index (HGI), spatial queries in wireless data broadcasting. Distrib Parallel Databases 31, 413–446 (2013). https://doi.org/10.1007/s10619-013-7121-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10619-013-7121-y

Keywords

Search

Navigation