Maintenance of K-nn and spatial join queries on continuously moving points

ABSTRACT

Cars, aircraft, mobile cell phones, ships, tanks, and mobile robots all have the common property that they are moving objects. A kinematic representation can be used to describe the location of these objects as a function of time. For example, a moving point can be represented by the function p(t) = &OV0489;0 + (t − t0)&OV0505;, where &OV0489;0 is the start location, t0 is the start time, and &OV0505; is its velocity vector. Instead of storing the location of the object at a given time in a database, the coefficients of the function are stored. When an object's behavior changes enough so that the function describing its location is no longer accurate, the function coefficients for the object are updated. Because the location of each object is represented as a function of time, spatial query results can change even when no transactions update the database. We present efficient algorithms to maintain k-nearest neighbor, and spatial join queries in this domain as time advances and updates occur. We assume no previous knowledge of what the updates will be before they occur. We experimentally compare these new algorithms with more straight forward adaptations of previous work to support updates. Experiments are conducted using synthetic uniformly distributed data, and real aircraft flight data. The primary metric of comparison is the number of I/O disk accesses needed to maintain the query results and the supporting data structures.

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: Agarwal, P. K. and Procopiuc, C. M. 2002. Advances in indexing for mobile objects. IEEE Bull. Tech. Comm. Data Eng. 25, 2, 25--34.
• 3: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jan Vahrenhold , Jeffrey Scott Vitter, A Unified Approach for Indexed and Non-Indexed Spatial Joins, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.413-429, March 27-31, 2000
• 4: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 5: Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
• 6: Rimantas Benetis , Christian S. Jensen , Gytis Karciauskas , Simonas Saltenis, Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.44-53, July 17-19, 2002
• 7: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 8: Douglas, D. and Peucker, T. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartograph. 10, 2, 112--122.
• 9: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 10: Bugra Gedik , Kun-Lung Wu , Philip Yu , Ling Liu, Motion adaptive indexing for moving continual queries over moving objects, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031255]
• 11: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 12: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 13: Güting, R. H. and Schneider, M. 2005. Moving Objects Databases. Morgan-Kaufmann, San Francisco, CA.
• 14: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 15: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 16: Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.237-248, June 01-04, 1998, Seattle, Washington, United States
• 17: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 18: Iwerks, G. S., Samet, H., and Smith, K. 2003. Continuous k-nearest neighbor queries for continuously moving points with updates. In Proceedings of the 29th International Conference on Very Large Data Bases (Berlin, Germany). 512--523.
• 19: Iwerks, G. S., Samet, H., and Smith, K. 2004. Maintenance of spatial semijoin queries on moving points. In Proceedings of the 30th International Conference on Very Large Data Bases (Toronto, Ont., Canada).
• 20: Jensen, C. S. and Saltenis, S. 2002. Towards increasingly update efficient moving-object indexing. IEEE Bull. Tech. Comm. Data Eng. 25, 2 (June), 35--40.
• 21: Dmitri V. Kalashnikov , Sunil Prabhakar , Susanne E. Hambrusch, Main Memory Evaluation of Monitoring Queries Over Moving Objects, Distributed and Parallel Databases, v.15 n.2, p.117-135, March 2004 [doi>10.1023/B:DAPD.0000013068.25976.88]
• 22: Lema, J. A. C., Forlizzi, L., Güting, R. H., Nardelli, E., and Schneider, M. 2003. Algorithms for moving objects databases. Comput. J. 46, 6, 680--712.
• 23: Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
• 24: Mokbel, M. F., Ghanem, T. M., and Aref, W. G. 2003. Spatio-temporal access methods. IEEE Bull. Tech. Comm. Data Eng. 26, 2 (June), 40--49.
• 25: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 26: Hoda Mokhtar , Jianwen Su , Oscar Ibarra, On moving object queries: (extended abstract), Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543638]
• 27: Nakamura, Y. and Yamane, K. 2000. Dynamics computation of structure-varying kinematic chains and its application to human figures. IEEE Trans. Rob. Automat. 16, 2 (Apr.), 124--134.
• 28: Mario A. Nascimento , Jefferson R. O. Silva , Yannis Theodoridis, Evaluation of Access Structures for Discretely Moving Points, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.171-188, September 10-11, 1999
• 29: Gultekin Ozsoyoglu , Richard Thomas Snodgrass, Temporal and Real-Time Databases: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.513-532, August 1995 [doi>10.1109/69.404027]
• 30: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 31: Pfoser, D. 2002. Indexing the trajectories of moving objects. IEEE Bull. Tech. Comm. Data Eng 25, 2 (June), 3--9.
• 32: Dieter Pfoser , Christian S. Jensen, Capturing the Uncertainty of Moving-Object Representations, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.111-132, July 20-23, 1999
• 33: Cecilia Magdalena Procopiuc , Pankaj K. Agarwal , Sariel Har-Peled, STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects, Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments, p.178-193, January 04-05, 2002
• 34: K. Raptopoulou , A. N. Papadopoulos , Y. Manolopoulos, Fast Nearest-Neighbor Query Processing in Moving-Object Databases, Geoinformatica, v.7 n.2, p.113-137, June 2003 [doi>10.1023/A:1023403908170]
• 35: 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
• 36: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 37: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 38: SCIS. 1996. IEEE Std. 1278 1-1995. IEEE Computer Society, Standards Committee on Interactive Simulation, USA.
• 39: 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
• 40: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 41: Yufei Tao , Dimitris Papadias, Spatial queries in dynamic environments, ACM Transactions on Database Systems (TODS), v.28 n.2, p.101-139, June 2003 [doi>10.1145/777943.777944]
• 42: Tao, Y., Papadias, D., and Sun, J. 2003a. The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In Proceedings of the 29th International Conference on Very Large Data Bases (Berlin, Germany). 790--801.
• 43: Tao, Y., Sun, J., and Papadias, D. 2003b. Selectivity estimation for predictive spatio-temporal queries. In Proceedings of 19th IEEE International Conference on Data Engineering (ICDE) (Bangalore, India). IEEE Computer Society Press, Los Alamitos, CA, 417--428.
• 44: Tayeb, J., Ulusoy, Ö., and Wolfson, O. 1998. A quadtree-based dynamic attribute indexing method. Comput. J. 41, 3, 185--200.
• 45: Trajcevski, G., Scheuermann, P., Wolfson, O., and Nedungadi, N. 2004a. CAT: Correct answers of continuous queries using triggers. In Proceedings of the International Conference on Extending Database Technology (EDBT) (Heraklion, Greece). 837--840.
• 46: Goce Trajcevski , Ouri Wolfson , Klaus Hinrichs , Sam Chamberlain, Managing uncertainty in moving objects databases, ACM Transactions on Database Systems (TODS), v.29 n.3, p.463-507, September 2004 [doi>10.1145/1016028.1016030]
• 47: Ouri Wolfson , Sam Chamberlain , Son Dao , Liqin Jiang , Gisela Mendez, Cost and Imprecision in Modeling the Position of Moving Objects, Proceedings of the Fourteenth International Conference on Data Engineering, p.588-596, February 23-27, 1998
• 48: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 49: Scalable Spatio-temporal Continuous Query Processing for Location-aware Services, Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), p.317, June 21-23, 2004 [doi>10.1109/SSDBM.2004.61]

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Object representation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
      H.2.8 Database applications
          Subjects: Spatial databases and GIS
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Command and control

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
k-nearest neighbor, Moving object databases, continuously moving objects, materialized view maintenance, spatial join, temporal databases