Welcome to D
SIGMOD'00
PODS'00
= PODS'00 Webs
= Plenary Talk
<<< = PODS'00 Pape>>>
SIGMOD Recor
CIKM 2000/CI
COMAD 2000
Data Enginee
DL 2000
DPDJ
EDBT 2000
Hypertext 20
ICDE 2000
KDD 2000
KDD Explorat
KRDB 2000
SBBD 2000
SIGIR 2000
SIGIR Forum
SSDBM 2000
TODS
VLDB'00
VLDBJ

Indexing Moving Points


Pankaj K. Agarwal, Lars Arge, and Jeff Erickson

  View Paper (PDF)  

Return to Indexing / Transactions


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 [epsilon] 0, uses O(N/B) disk blocks, where B is the block size, and answers a query in O((N/B)1/2+[epsilon] + 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


Note: References link to DBLP on the Web.

[1]
Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paolo Giulio Franciosa , Jeffrey Scott Vitter : Efficient Searching with Linear Constraints. PODS 1998 : 169-178
[2]
...
[3]
Pankaj K. Agarwal , Jeff Erickson , Leonidas J. Guibas : Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (Extended Abstract). SODA 1998 : 107-116
[4]
...
[5]
Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter : On Two-Dimensional Indexability and Optimal Range Search Indexing. PODS 1999 : 346-357
[6]
Lars Arge , Jeffrey Scott Vitter : Optimal Dynamic Interval Management in External Memory (extended abstract). FOCS 1996 : 560-569
[7]
Julien Basch , Leonidas J. Guibas , John Hershberger : Data Structures for Mobile Data. SODA 1997 : 747-756
[8]
Julien Basch , Leonidas J. Guibas , Li Zhang : Proximity Problems on Moving Points. Symposium on Computational Geometry 1997 : 344-351
[9]
Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer : An Asymptotically Optimal Multiversion B-Tree. VLDB Journal 5(4) : 264-275(1996)
[10]
...
[11]
Jan Chomicki , Peter Z. Revesz : A Geometric Framework for Specifying Spatiotemporal Objects. TIME 1999 : 41-46
[12]
James R. Driscoll , Neil Sarnak , Daniel Dominic Sleator , Robert Endre Tarjan : Making Data Structures Persistent. JCSS 38(1) : 86-124(1989)
[13]
Martin Erwig , Markus Schneider : Developments in Spatio-Temporal Query Languages. DEXA Workshop 1999 : 441-449
[14]
Martin Erwig , Ralf Hartmut Güting , Markus Schneider , Michalis Vazirgiannis : Abstract and Discrete Modeling of Spatio-Temporal Data Types. ACM-GIS 1998 : 131-136
[15]
Volker Gaede , Oliver Günther : Multidimensional Access Methods. Computing Surveys 30(2) : 170-231(1998)
[16]
Michael T. Goodrich , Jyh-Jong Tsay , Darren Erik Vengroff , Jeffrey Scott Vitter : External-Memory Computational Geometry (Preliminary Version). FOCS 1993 : 714-723
[17]
Paris C. Kanellakis , Sridhar Ramaswamy , Darren Erik Vengroff , Jeffrey Scott Vitter : Indexing for Data Models with Constraints and Classes. JCSS 52(3) : 589-612(1996)
[18]
George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras : On Indexing Mobile Objects. PODS 1999 : 261-272
[19]
George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras : Nearest Neighbor Queries in a Mobile Environment. Spatio-Temporal Database Management 1999 : 119-134
[20]
Manolis Koubarakis , Spiros Skiadopoulos : Tractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatiotemporal Information. Spatio-Temporal Database Management 1999 : 204-223
[21]
Jirí Matousek : Efficient Partition Trees. Symposium on Computational Geometry 1991 : 1-9
[22]
Jürg Nievergelt , Peter Widmayer : Spatial Data Structures: Concepts and Design Choices. Algorithmic Foundations of Geographic Information Systems 1996 : 153-197
[23]
Mark H. Overmars : The Design of Dynamic Data Structures. Lecture Notes in Computer Science Vol. 156 Springer 1983, ISBN 3-540-12330-X
[24]
Mark H. Overmars , Jan van Leeuwen : Maintenance of Configurations in the Plane. JCSS 23(2) : 166-204(1981)
[25]
...
[26]
Sridhar Ramaswamy , Paris C. Kanellakis : OODB Indexing by Class-Division. SIGMOD Conference 1995 : 139-150
[27]
Sridhar Ramaswamy , Sairam Subramanian : Path Caching: A Technique for Optimal External Searching. PODS 1994 : 25-35
[28]
Simonas Saltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez : Indexing the Positions of Continuously Moving Objects. SIGMOD Conference 2000 : 331-342
[29]
Betty Salzberg , Vassilis J. Tsotras : Comparison of Access Methods for Time-Evolving Data. Computing Surveys 31(2) : 158-221(1999)
[30]
...
[31]
A. Prasad Sistla , Ouri Wolfson : Temporal Conditions and Integrity Constraints in Active Database Systems. SIGMOD Conference 1995 : 269-280
[32]
A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao : Modeling and Querying Moving Objects. ICDE 1997 : 422-432
[33]
Jamel Tayeb , Özgür Ulusoy , Ouri Wolfson : A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal 41(3) : 185-200(1998)
[34]
Peter J. Varman , Rakesh M. Verma : An Efficient Multiversion Access STructure. TKDE 9(3) : 391-409(1997)
[35]
Jeffrey Scott Vitter : Online Data Structures in External Memory. ICALP 1999 : 119-133
[36]
Ouri Wolfson , Sam Chamberlain , Son Dao , Liqin Jiang , Gisela Mendez : Cost and Imprecision in Modeling the Position of Moving Objects. ICDE 1998 : 588-596
[37]
Ouri Wolfson , Liqin Jiang , A. Prasad Sistla , Sam Chamberlain , Naphtali Rishe , Minglin Deng : Databases for Tracking Mobile Units in Real Time. ICDT 1999 : 169-186
[38]
Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha : Updating and Querying Databases that Track Mobile Units. Distributed and Parallel Databases 7(3) : 257-387(1999)
[39]
Ouri Wolfson , A. Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain : DOMINO: Databases fOr MovINg Objects tracking. SIGMOD Conference 1999 : 547-549
[40]
Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang : Moving Objects Databases: Issues and Solutions. SSDBM 1998 : 111-122

Referenced by

  1. Simonas Saltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez : Indexing the Positions of Continuously Moving Objects. SIGMOD Conference 2000 : 331-342

BIBTEX


@inproceedings{DBLP:conf/pods/AgarwalAE00,
  author    = {Pankaj K. Agarwal and
                Lars Arge and
                Jeff Erickson},
   title     = {Indexing Moving Points},
   booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium
                on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
                USA},
   publisher = {ACM},
   year      = {2000},
   isbn      = {1-58113-214-X},
   pages     = {175-186},
   crossref  = {DBLP:conf/pods/00},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


DiSC'01 Copyright ©2002 ACM Inc.