Digital Symposium Collection 2000

On Indexing Mobile Objects George Kollios, Dimitrios Gunopulos, and Vassilis J. Tsotras   View Paper (PDF)   Return to Novel Data Abstract We show how to index mobile objects in one and two dimensions using efficient dynamic external memory data structures. The problem is motivated by real life applications in traffic monitoring, intelligent navigation and mobile communications domains. For the l-dimensional case, we give (i) a dynamic, external memory algorithm with guaranteed worst case performance and linear space and (ii) a practical approximation algorithm also in the dynamic, external memory setting, which has linear space and expected logarithmic query time. We also give an algorithm with guaranteed logarithmic query time for a restricted version of the problem. We present extensions of our techniques to two dimensions. In addition we give a lower bound on the number of I/O’s needed to answer the d-dimensional problem. Initial experimental results and comparisons to traditional indexing approaches are also included. 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] Alok Aggarwal , Jeffrey Scott Vitter : The Input/Output Complexity of Sorting and Related Problems. CACM 31(9) : 1116-1127(1988) [4] ... [5] ... [6] Julien Basch , Leonidas J. Guibas , John Hershberger : Data Structures for Mobile Data. SODA 1997 : 747-756 [7] Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer : An Asymptotically Optimal Multiversion B-Tree. VLDB Journal 5(4) : 264-275(1996) [8] 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 [9] Elisa Bertino , Barbara Catania , Boris Shidlovsky : Towards Optimal Two-Dimensional Indexing for Constraint Databases. Information Processing Letters 64(1) : 1-8(1997) [10] Bernard Chazelle , Burton Rosenberg : Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine. ICALP 1992 : 439-449 [11] Jan Chomicki , Peter Z. Revesz : A Geometric Framework for Specifying Spatiotemporal Objects. TIME 1999 : 41-46 [12] Richard Cole : Searching and Storing Similar Lists. J. Algorithms 7(2) : 202-220(1986) [13] Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979) [14] James R. Driscoll , Neil Sarnak , Daniel Dominic Sleator , Robert Endre Tarjan : Making Data Structures Persistent. STOC 1986 : 109-121 [15] Martin Erwig , Ralf Hartmut Güting , Markus Schneider , Michalis Vazirgiannis : Abstract and Discrete Modeling of Spatio-Temporal Data Types. ACM-GIS 1998 : 131-136 [16] Georgios Evangelidis , David B. Lomet , Betty Salzberg : The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995 : 551-561 [17] Volker Gaede , Oliver Günther : Multidimensional Access Methods. Computing Surveys 30(2) : 170-231(1998) [18] Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft , Jie-Bing Yu : Processing Queries By Linear Constraints. PODS 1997 : 257-267 [19] Oliver Günther : The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989 : 598-605 [20] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [21] Andreas Henrich , Hans-Werner Six , Peter Widmayer : The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989 : 45-53 [22] Erik G. Hoel , Hanan Samet : A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992 : 205-214 [23] H. V. Jagadish : On Indexing Line Segments. VLDB 1990 : 614-625 [24] Ibrahim Kamel , Christos Faloutsos : On Packing R-trees. CIKM 1993 : 490-499 [25] Paris C. Kanellakis , Sridhar Ramaswamy , Darren Erik Vengroff , Jeffrey Scott Vitter : Indexing for Data Models with Constraints and Classes. PODS 1993 : 233-243 [26] Anil Kumar , Vassilis J. Tsotras , Christos Faloutsos : Designing Access Methods for Bitemporal Databases. TKDE 10(1) : 1-20(1998) [27] ... [28] Mark H. Overmars : The Design of Dynamic Data Structures. Lecture Notes in Computer Science Vol. 156 Springer 1983, ISBN 3-540-12330-X [29] ... [30] Hanan Samet : The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990 [31] Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos : The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987 : 507-518 [32] Shashi Shekhar , T. A. Yang : Motion in a Geographical Database System. SSD 1991 : 339-358 [33] A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao : Modeling and Querying Moving Objects. ICDE 1997 : 422-432 [34] Sairam Subramanian , Sridhar Ramaswamy : The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. SODA 1995 : 378-387 [35] Jamel Tayeb , Özgür Ulusoy , Ouri Wolfson : A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal 41(3) : 185-200(1998) [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 , Bo Xu , Sam Chamberlain , Liqin Jiang : Moving Objects Databases: Issues and Solutions. SSDBM 1998 : 111-122 BIBTEX @inproceedings{DBLP:conf/pods/KolliosGT99,   author    = {George Kollios and                 Dimitrios Gunopulos and                 Vassilis J. Tsotras},    title     = {On Indexing Mobile Objects},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {261-272},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM