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

A distributed spatial index for error-prone wireless data broadcast

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

Abstract

Information is valuable to users when it is available not only at the right time but also at the right place. To support efficient location-based data access in wireless data broadcast systems, a distributed spatial index (called DSI) is presented in this paper. DSI is highly efficient because it has a linear yet fully distributed structure that naturally shares links in different search paths. DSI is very resilient to the error-prone wireless communication environment because interrupted search operations based on DSI can be resumed easily. It supports search algorithms for classical location-based queries such as window queries and kNN queries in both of the snapshot and continuous query modes. In-depth analysis and simulation-based evaluation have been conducted. The results show that DSI significantly out-performs a variant of R-trees tailored for wireless data broadcast environments.

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

Access this article

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.

Similar content being viewed by others

References

  1. Acharya, D., Kumar, V.: Location based indexing scheme for days. In: Proceedings of the 4th ACM International Workshop on Data engineering for Wireless and Mobile access (MobiDE’05), pp. 17–24, June 2005

  2. 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), pp. 199–210, May 1995

  3. Chen M.-S., Wu K.-L., Yu S.: Optimizing index allocation for sequential data broadcasting in wireless mobile computing. IEEE Trans Knowl Data Eng (TKDE) 15(1), 161–173 (2003)

    Article  Google Scholar 

  4. 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), pp. 124–133, April 1997

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

    Article  Google Scholar 

  6. Garg, N., Kumar, V., Dunham, M.: Information mapping and indexing in days. In: Proceedings of the 14th International Workshop on Database and Expert Systems Applications (DEXA’03), pp. 951–955, 2003

  7. Gedik, B., Liu, L.: Location privacy in mobile systems: a personalized anonymization model. In: Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS’05), June 2005

  8. Gedik, B., Singh, A., Liu, L.: Energy efficient exact kNN search in wireless broadcast environments. In: Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems (GIS’04), pp. 137–146, 2004

  9. Gotsman C., Lindenbaum M.: On the metric properties of discrete space-filling curves. IEEE Trans. Image Process. 5(5), 794–797 (1996)

    Article  Google Scholar 

  10. Gruteser, M., Grunwald, D.: Anonymous usage of location-based services through spatial and temporal cloaking. In: Proceedings of the 1st ACM/USENIX International Conference on Mobile Systems, Applications, and Services (MobiSys’03), June 2003

  11. Guttman, A.: R-trees: A dynamic index structure for spatial searching. In: Proceedings of the ACM SIGMOD Conference on Management of Data (SIGMOD’84), pp. 47–54, June 1984

  12. Hu, Q.L., Lee, W.-C., Lee, D.L.: Power conservative multi-attribute queries on data broadcast. In: Proceedings of the 16th International Conference on Data Engineering (ICDE’00), pp. 157–166, February 2000

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

  14. Imielinski T., Viswanathan S., Badrinath, B.R.: Power efficiency filtering of data on air. In: Proceedings of the 4th International Conference on Extending Database Technology (EDBT’94), pp. 245–258, March 1994

  15. Imielinski, T., Viswanathan, S., Badrinath, B.R.: Data on Air—Organization and Access. IEEE Transactions on Knowledge and Data Engineering (TKDE), 9(3), May–June 1997

  16. Kasten, O.: Energy Consumption. Website at http://www.inf.ethz.ch/personal/kasten/research/bathtub/energy_consumption.html

  17. Lee W.-C., Lee D.L.: Using signature techniques for information filtering in wireless and mobile environments. J. Distrib. Parallel Databases (DPDB) (Special Issue on Database and Mobile Computing) 4(3), 205–227 (1996)

    Google Scholar 

  18. Lee, W.-C., Zheng, B.: DSI: a fully distributed spatial index for wireless data broadcast. In: Proceedings of 25th IEEE International Conference on Distributed Computing Systems (ICDCS’05), June 2005

  19. Leutenegger, S.T., Edgington, J.M., Lopez, M.A.: STR: a simple and efficient algorithm for R-Tree packing. In: Proceedings of the 13th International Conference on Data Engineering (ICDE’97), pp. 497–506, April 1997

  20. Lo S.-C., Chen L.-P.: An adaptive access method for broadcast data under an error-prone mobile environment. IEEE Trans. Knowl. Data Eng. (TKDE) 12(4), 609–620 (2000)

    Article  Google Scholar 

  21. Mokbel, M., Chow, C.-Y., Aref, W.: The new casper: query processing for location services without compromising privacy. In: Proceedings of the International Conference on Very Large Data Bases (VLDB’06), Seoul, Korea, 2006

  22. Moore, D.: Hilbert Curve. URL at http://www.caam.rice.edu/dougm/twiddle/Hilbert

  23. Ren, Q., Dunham, M.H.: Using semantic caching to manage location dependent data in mobile computing. In: Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom’00), pp. 210–221, August 2000

  24. Robinson, J.T.: The KDB Tree: a search structure for large multidimentional dynamic indexes. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’81), pp. 10–18, Ann Arbor, MI, USA, April 1981

  25. SA-1100 Microprocessor product brief. Website at http://bwrc.eecs.berkeley.edu/Research/Pico_Radio/Test_Bed/Hardware/Documentation/ARM/processor_arm_SA1100-productbrief.pdf

  26. Samet H.: The QuadTree and related hierarchical data structures. ACM Comput. Surv. (CSUR) 16(2), 187–260 (1984)

    Article  MathSciNet  Google Scholar 

  27. Schwetman, H.: CSIM User’s Guide (version 18). Mesquite Software, Inc., http://www.mesquite.com, 1998

  28. Seydim, A., Dunham, M., Kumar, V.: Location dependent query processing. In: Proceedings of the 2nd ACM International Workshop on Data Engineering for Wireless and Mobile Access (MobiDE’01), pp. 47–53, Santa Barbara, CA, USA, May 2001

  29. Seydim, A., Dunham, M., Kumar, V.: An architecture for location dependent query processing. In: Proceedings of the Fourth International Workshop on Mobility in Databases and Distributed Systems (MDDS’01), 2001

  30. 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), pp. 85–96, June 1999

  31. Sistla, A.P., Wolfson, O., Chamberlain, S., Dao, S.: Modeling and querying moving objects. In: Proceedings of the 13th International Conference on Data Engineering (ICDE’97), pp. 422–432, April 1997

  32. Stoica, I., Morris, R., Karger, D., Kaashoek, M., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for Internet applications. In: Proceedings of conference of the Special Interest Group on Data Communication (SIGCOMM’01), pp. 149–160, August 2001

  33. Tao, Y., Papadias, D., Shen, Q.: Continuous nearest neighbor search. In: Proceedings of the 28th International Conference on Very Large Data Bases (VLDB’02), August 2002

  34. Topologically Integrated Geographic Encoding and Referencing system. TIGER homepage. Website at http://www.census.gov/geo/www/tiger/

  35. Wang, A., Cho, S., Sodini, G., Chandrakasan, P.: Energy efficient modulation and MAC for asymmetric RF microsensor systems. In: Proceedings of the 2001 International Symposium on Low Power Electronics and Design, 2001

  36. Wang, J., Sinnarajah, R., Chen, T., Wei, Y., Tiedemann, E.: Broadcast and multicast services in cdma2000. IEEE Comm. Mag. 42(2), 2004

  37. Xu, J., Lee, W.-C., Tang, X.: Exponential index: a parameterized distributed indexing scheme for data on air. In: Proceedings of the 2nd ACM/USENIX International Conference on Mobile Systems, Applications, and Services (MobiSys’04), Boston, MA, June 2004

  38. Xu, J., Zheng, B., Lee, W.-C., Lee, D.L.: Energy efficient index for querying location-dependent data in mobile broadcast environments. In: Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE’03), pp. 239–250, March 2003

  39. Zhang, J., Gruenwald, L.: Efficient placement of geographical data over broadcast channel for spatial range query under quadratic cost model. In: Proceedings of the 3rd International ACM Workshop on Data Engineering for Wireless and Mobile Access (MobiDE’03), 2003

  40. Zhang, J., Gruenwald, L.: Optimizing data placement over wireless broadcast channel for multi-dimensional range query processing. In: Proceedings of IEEE International Conference on Mobile Data Management (MDM’04), 2004

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

    Article  Google Scholar 

  42. Zheng, B., Lee, W.-C., Lee, D.L.: Spatial index on air. In: Proceedings of the first IEEE International Conference on Pervasive Computing and Communications (PerCom’03), pp. 297–304, March 2003

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

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Baihua Zheng.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zheng, B., Lee, WC., Lee, K.C.K. et al. A distributed spatial index for error-prone wireless data broadcast. The VLDB Journal 18, 959–986 (2009). https://doi.org/10.1007/s00778-009-0137-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00778-009-0137-2

Keywords

Navigation