High-performance spatial indexing for location-based services

ABSTRACT

Much attention has been accorded to Location-Based Services and location tracking, a necessary component in active, trigger-based LBS applications. Tracking the location of a large population of moving objects requires very high update and query performance of the underlying spatial index. In this paper we investigate the performance and scalability of three main-memory based spatial indexing methods under dynamic update and query loads: an R-tree, a ZB-tree, and an array/hashtable method. By leveraging the LOCUS performance evaluation testbed and the City Simulator dynamic spatial data generator, we are able to demonstrate the scalability of these methods and determine the maximum population size supported by each method, a useful parameter for capacity planning by wireless carriers.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 2: Arnon Amir, Alon Efrat, Jussi Myllymaki, Lingeshwaran Palaniappan, and Kevin Wampler. Buddy tracking - efficient proximity detection among mobile friends. IBM Research Report, RJ 10250, August 2002.
• 3: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 4: James Kaufman, Jussi Myllymaki, and Jared Jackson. City Simulator spatial data generator, November 2001. http://alphaworks.ibm.com/tech/citysimulator.
• 5: Yasuhiko Morimoto, Mining frequent neighboring class sets in spatial databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.353-358, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502564]
• 6: Jussi Myllymaki and James Kaufman. LOCUS: A testbed for dynamic spatial indexing. IEEE Data Engineering Bulletin (Special Issue on Indexing of Moving Objects), 25(2), June 2002.
• 7: Jussi Myllymaki , James Kaufman, DynaMark: A Benchmark for Dynamic Spatial Indexing, Proceedings of the 4th International Conference on Mobile Data Management, p.92-105, January 21-24, 2003
• 8: Dieter Pfoser , Christian S. Jensen, Querying the trajectories of on-line mobile objects, Proceedings of the 2nd ACM international workshop on Data engineering for wireless and mobile access, p.66-73, May 2001, Santa Barbara, California, United States [doi>10.1145/376868.376902]
• 9: Indexing of Moving Objects for Location-Based Services, Proceedings of the 18th International Conference on Data Engineering, p.463, February 26-March 01, 2002
• 10: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 11: Shashi Shekhar , Sanjay Chawla , Siva Ravada , Andrew Fetterer , Xuan Liu , Chang-tien Lu, Spatial Databases-Accomplishments and Research Needs, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.45-55, January 1999 [doi>10.1109/69.755614]
• 12: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 13: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998 [doi>10.1109/SSDM.1998.688116]
• 14: Vincent W.-S. Wong and Victor C. M. Leung. Location management for next generation personal communication networks. IEEE Network, 14(5):18--24, September 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Experimentation, Performance

Keywords:
location-based services, mobile computing, spatial indexing