Indexing moving points (extended abstract)

ABSTRACT

We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle R and a real value tq, report all K points of S that lie inside R at time tq. We first present an indexing structure that, for any given constant &egr; > 0, uses O(N/B) disk blocks, where B is the block size, and answers a query in O((N/B)1/2+&egr; + K/B) I/Os. It can also report all the points of S that lie inside R during a given time interval. A point can be inserted or deleted, or the trajectory of a point can be changed, in O(log2B N) I/Os. Next, we present a general approach that improves the query time if the queries arrive in chronological order, by allowing the index to evolve over time. We obtain a trade off between the query time and the number of times the index needs to be updated as the points move. We also describe an indexing scheme in which the number of I/Os required to answer a query depends monotonically on the difference between tq and the current time. Finally, we develop an efficient indexing scheme to answer approximate nearest-neighbor queries among moving points.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paolo G. Franciosa , Jeffry Scott Vitter, Efficient searching with linear constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.169-178, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275506]
• 2: P. K. Agarwal and J. Erickson, Geometric range searching and its relatives, Advances in Discrete and Computational Geometry (B. Chazelle, J. E. Goodman, and R. Pollack, eds.), AMS Press, 1999, pp. 1-56.
• 3: Pankaj K. Agarwal , Jeff Erickson , Leonidas J. Guibas, Kinetic binary space partitions for intersecting segments and disjoint triangles, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.107-116, January 25-27, 1998, San Francisco, California, United States
• 4: ArcView GIS, ArcView Tracking Analyst, 1998.
• 5: Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304010]
• 6: L. Arge , J. S. Vitter, Optimal dynamic interval management in external memory, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.560, October 14-16, 1996
• 7: 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
• 8: Julien Basch , Leonidas J. Guibas , Li Zhang, Proximity problems on moving points, Proceedings of the thirteenth annual symposium on Computational geometry, p.344-351, June 04-06, 1997, Nice, France [doi>10.1145/262839.262998]
• 9: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 10: S. Chamberlain, Model-based battle command: A paradigm whose time has come, Proc. 1st Intl. Sympos. Command and Control Research and Technology, 31- 38, 1995.
• 11: Jan Chomicki , Peter Z. Revesz, A Geometric Framework for Specifying Spatiotemporal Objects, Proceedings of the Sixth International Workshop on Temporal Representation and Reasoning, p.41, May 01-02, 1999
• 12: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 13: Martin Erwig , Markus Schneider, Developments in Spatio-Temporal Query Languages, Proceedings of the 10th International Workshop on Database & Expert Systems Applications, p.441, September 01-03, 1999
• 14: Martin Erwig , Ralf Hartmut Güting , Markus Schneider , Michalis Vazirgiannis, Abstract and discrete modeling of spatio-temporal data types, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.131-136, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288716]
• 15: 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]
• 16: M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter, External-memory computational geometry, Proc. 3~th Annu. IEEE Sympos. Found. Comput. Sci., 714-723, 1993.
• 17: Paris Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey Scott Vitter, Indexing for data models with constraints and classes, Journal of Computer and System Sciences, v.52 n.3, p.589-612, June 1996 [doi>10.1006/jcss.1996.0043 ]
• 18: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 19: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, Nearest Neighbor Queries in a Mobile Environment, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.119-134, September 10-11, 1999
• 20: Manolis Koubarakis , Spiros Skiadopoulos, Tractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatiotemporal Information, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.204-223, September 10-11, 1999
• 21: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992
• 22: Jürg Nievergelt , Peter Widmayer, Spatial Data Structures: Concepts and Design Choices, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.153-197, September 16-20, 1996
• 23: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 24: M.H. Overmars and J. van Leeuwen, Maintenance of configurations in the plane, J. Comput. Syst. Sci. 23:166-204, 1981.
• 25: D. Pfoser, Y. Theodoidis, and C. S. Jensen, Indexing trajectories of moving point objects, Chorochronos Tech. Rept. CH-99-3, 1999.
• 26: S. Ramaswamy and P. Kanellakis, OODB indexing by class division, A.P.I.C. Series, Academic Press, New York, 1995.
• 27: Sridhar Ramaswamy , Sairam Subramanian, Path caching (extended abstract): a technique for optimal external searching, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.25-35, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182595]
• 28: 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
• 29: B. Salzberg and V. J. Tsotras, A Comparison of Access Methods for Temporal Data, TimeCenter Technical Report, TR-13, 1997.
• 30: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 31: A. Prasad Sistla , Ouri Wolfson, Temporal conditions and integrity constraints in active database systems, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.269-280, May 22-25, 1995, San Jose, California, United States
• 32: 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
• 33: J. Tayeb, O. Ulusoy, and O. Wolfson, A quadtree-based dynamic attribute indexing method, The Computer Journal 41:185-200, 1998.
• 34: Peter J. Varman , Rakesh M. Verma, An Efficient Multiversion Access Structure, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.391-409, May 1997 [doi>10.1109/69.599929 ]
• 35: Jeffrey Scott Vitter, Online Data Structures in External Memory, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.119-133, July 11-15, 1999
• 36: 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
• 37: Ouri Wolfson , Liqin Jiang , A. Prasad Sistla , Sam Chamberlain , Naphtali Rishe , Minglin Deng, Databases for Tracking Mobile Units in Real Time, Proceeding of the 7th International Conference on Database Theory, p.169-186, January 10-12, 1999
• 38: Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha, Updating and Querying Databases that Track Mobile Units, Distributed and Parallel Databases, v.7 n.3, p.257-387, July 1999 [doi>10.1023/A:1008782710752 ]
• 39: Ouri Wolfson , Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain, DOMINO: databases fOr MovINg Objects tracking, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.547-549, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 40: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Theory