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.
Similar content being viewed by others
References
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
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
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)
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
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)
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
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
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
Gotsman C., Lindenbaum M.: On the metric properties of discrete space-filling curves. IEEE Trans. Image Process. 5(5), 794–797 (1996)
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
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
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
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
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
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
Kasten, O.: Energy Consumption. Website at http://www.inf.ethz.ch/personal/kasten/research/bathtub/energy_consumption.html
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)
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
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
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)
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
Moore, D.: Hilbert Curve. URL at http://www.caam.rice.edu/dougm/twiddle/Hilbert
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
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
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
Samet H.: The QuadTree and related hierarchical data structures. ACM Comput. Surv. (CSUR) 16(2), 187–260 (1984)
Schwetman, H.: CSIM User’s Guide (version 18). Mesquite Software, Inc., http://www.mesquite.com, 1998
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
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
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
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
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
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
Topologically Integrated Geographic Encoding and Referencing system. TIGER homepage. Website at http://www.census.gov/geo/www/tiger/
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
Wang, J., Sinnarajah, R., Chen, T., Wei, Y., Tiedemann, E.: Broadcast and multicast services in cdma2000. IEEE Comm. Mag. 42(2), 2004
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
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
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
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
Zheng B., Lee D.L.: Information dissemination via wireless broadcast. Comm. ACM 48(5), 105–110 (2005)
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
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)
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-009-0137-2