An error-resilient cell-based distributed index for location-based wireless broadcast services

ABSTRACT

Air indexing techniques have been developed for energy efficient query processing of mobile clients(MCs) in the wireless data broadcast. In the air indexing for spatial data, previous studies have involved various problems, long broadcast cycle by large index size and unnecessary data listening by the query processing based on coordinates, which are mapped on space-filling curves from the real coordinates of data instances. In this paper, Cell-based Distributed Spatial Index(called CEDI) is proposed for wireless broadcast services. CEDI is very compact in size by keeping pointers of the groups of data instances instead of the pointer of each data instance. CEDI has distributed structure and supports multiple search paths by the replication of the pointers of data groups. CEDI does not have unnecessary data instances in the result due to processing queries based on the real coordinates of data instances. Therefore CEDI is very efficient for energy and has reduced access time to desired data. Moveover, CEDI has the robustness for link-error in error-prone wireless transmission environments. For the performance evaluation, simulation experiments using a real dataset and a uniform distribution dataset under various link-error probabilities are conducted. Experimental results show that CEDI outperforms the existing scheme in the energy efficiency and data access time. In particular, CEDI is much more resilient to link-errors.

REFERENCES

• 1: T. Imielinski , S. Viswanathan , B. r. Badrinath, Data on Air: Organization and Access, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.353-372, May 1997 [doi>10.1109/69.599926 ]
• 2: Tomasz Imielinski , S. Viswanathan , B. R. Badrinath, Energy efficient indexing on air, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.25-36, May 24-27, 1994, Minneapolis, Minnesota, United States
• 3: Baihua Zheng , Wang-Chien Lee , Dik Lun Lee, Spatial Index on Air, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.297, March 23-26, 2003
• 4: Baihua Zheng , Wang-Chien Lee , Dik Lun Lee, Spatial queries in wireless broadcast systems, Wireless Networks, v.10 n.6, p.723-736, November 2004 [doi>10.1023/B:WINE.0000044031.03597.97]
• 5: Wang-Chien Lee , Baihua Zheng, DSI: A Fully Distributed Spatial Index for Location-Based Wireless Broadcast Services, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.349-358, June 06-10, 2005 [doi>10.1109/ICDCS.2005.26]
• 6: Swarup Acharya , Michael Franklin , Stanley Zdonik, Balancing push and pull for data broadcast, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.183-194, May 11-15, 1997, Tucson, Arizona, United States
• 7: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 8: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 9: R. McNab and F.W. Howell, "Using Java for Discrete Event Simulation," In proceedings of the Twelfth UK Computer and Telecommunications Performance Engineering Workshop (UKPEW), pp. 219--228. 1996.
• 10: Real Datasets, available at http://www.rtreeportal.org
• 11: D. Moore. Hilbert Curve. available at http://www.caam.rice.edu/~dougm/twiddle/Hilbert

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Design, Performance

Keywords:
air index, location-based services, wireless broadcast