Welcome to D
SIGMOD'00
= SIGMOD'00 We
= Plenary Talk
<<< = SIGMOD'00 Pa>>>
PODS'00
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 the Positions of Continuously Moving Objects


Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, and Mario A. Lopez

  View Paper (PDF)  

Return to Research Sessions


Abstract

The coming years will witness dramatic advances in wireless communications as well as positioning technologies. As a result, tracking the changing positions of objects capable of continuous movement is becoming increasingly feasible and necessary. The present paper proposes a novel, R*-tree based indexing technique that supports the efficient querying of the current and projected future positions of such moving objects. The technique is capable of indexing objects moving in one-, two-, and three-dimensional space. Update algorithms enable the index to accommodate a dynamic data set, where objects may appear and disappear, and where changes occur in the anticipated positions of existing objects. A comprehensive performance study is reported.


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]
Pankaj K. Agarwal , Lars Arge , Jeff Erickson : Indexing Moving Points. PODS 2000 : 175-186
[3]
Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter : On Two-Dimensional Indexability and Optimal Range Search Indexing. PODS 1999 : 346-357
[4]
Julien Basch , Leonidas J. Guibas , John Hershberger : Data Structures for Mobile Data. SODA 1997 : 747-756
[5]
Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger : The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990 : 322-331
[6]
Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer : An Asymptotically Optimal Multiversion B-Tree. VLDB Journal 5(4) : 264-275(1996)
[7]
Rasa Bliujute , Christian S. Jensen , Simonas Saltenis , Giedrius Slivinskas : R-Tree Based Indexing of Now-Relative Bitemporal Data. VLDB 1998 : 345-356
[8]
Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft , Jie-Bing Yu : Processing Queries By Linear Constraints. PODS 1997 : 257-267
[9]
Oliver Günther , Eugene Wong : A Dual Approach to Detect Polyhedral Intersections in Arbitrary Demensions. BIT 31(1) : 3-14(1991)
[10]
Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer : Generalized Search Trees for Database Systems. VLDB 1995 : 562-573
[11]
Ibrahim Kamel , Christos Faloutsos : On Packing R-trees. CIKM 1993 : 490-499
[12]
...
[13]
George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras : On Indexing Mobile Objects. PODS 1999 : 261-272
[14]
...
[15]
Anil Kumar , Vassilis J. Tsotras , Christos Faloutsos : Designing Access Methods for Bitemporal Databases. TKDE 10(1) : 1-20(1998)
[16]
Scott T. Leutenegger , Mario A. Lopez : The Effect of Buffering on the Performance of R-Trees. ICDE 1998 : 164-171
[17]
...
[18]
Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer : Towards an Analysis of Range Query Performance in Spatial Data Structures. PODS 1993 : 214-221
[19]
...
[20]
Dieter Pfoser , Christian S. Jensen : Capturing the Uncertainty of Moving-Object Representations. SSD 1999 : 111-132
[21]
...
[22]
Hanan Samet : The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
[23]
...
[24]
...
[25]
...
[26]
Jamel Tayeb , Özgür Ulusoy , Ouri Wolfson : A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal 41(3) : 185-200(1998)
[27]
Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang : Moving Objects Databases: Issues and Solutions. SSDBM 1998 : 111-122
[28]
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)

Referenced by

  1. Pankaj K. Agarwal , Lars Arge , Jeff Erickson : Indexing Moving Points. PODS 2000 : 175-186

BIBTEX


@inproceedings{DBLP:conf/sigmod/SaltenisJLL00,
  author    = {Simonas Saltenis and
                Christian S. Jensen and
                Scott T. Leutenegger and
                Mario A. Lopez},
   editor    = {Weidong Chen and
                Jeffrey F. Naughton and
                Philip A. Bernstein},
   title     = {Indexing the Positions of Continuously Moving Objects},
   booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on
                Management of Data, May 16-18, 2000, Dallas, Texas, USA},
   journal   = {SIGMOD Record},
   publisher = {ACM},
   volume    = {29},
   number    = {2},
   year      = {2000},
   isbn      = {1-58113-218-2},
   pages     = {331-342},
   crossref  = {DBLP:conf/sigmod/2000},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


DiSC'01 Copyright ©2002 ACM Inc.