On nearest neighbor indexing of nonlinear trajectories

ABSTRACT

In recent years, the problem of indexing mobile objects has assumed great importance because of its relevance to a wide variety of applications. Most previous results in this area have proposed indexing schemes for objects with linear trajectories in one or two dimensions. In this paper, we present methods for indexing objects with nonlinear trajectories. Specifically, we identify a useful condition called the convex hull property and show that any trajectory satisfying this condition can be indexed by storing a careful representation of these objects in a traditional index structure. Since a wide variety of relevant nonlinear trajectories satisfy this condition, our result significantly expands the class of trajectories for which nearest neighbor indexing schemes can be devised. We also show that even though many non-linear trajectories do not satisfy the convex hull condition, an approximate representation can often be found which satisfies it. We discuss examples of techniques which can be utilized to find representations that satisfy the convex hull property. We present empirical results to demonstrate the effectiveness of our indexing method.

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: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 4: Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Storage and Retrieval of Moving Objects, Proceedings of the Second International Conference on Mobile Data Management, p.173-184, January 08-10, 2001
• 5: 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
• 6: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 7: 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
• 8: 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]
• 9: Erwin Kreyszig, Advanced Engineering Mathematics: Maple Computer Guide, John Wiley & Sons, Inc., New York, NY, 2000
• 10: K. I. Lin, H. V. Jagadish, and C. Faloutsos. The tv-tree: An index structure for high dimensional data. In VLDB Journal, 1992.
• 11: 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
• 12: D. Pfoser, Y. Theodoridis, and C. Jensen. Indexing trajectories of moving point objects. In VLDB Conference, 2000.
• 13: Kriengkrai Porkaew , Iosif Lazaridis , Sharad Mehrotra, Querying Mobile Objects in Spatio-Temporal Databases, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.59-78, July 12-15, 2001
• 14: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 15: 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
• 16: 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]
• 17: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 18: Zhexuan Song , Nick Roussopoulos, Hashing Moving Objects, Proceedings of the Second International Conference on Mobile Data Management, p.161-172, January 08-10, 2001
• 19: Ouri Wolfson , A. Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain , Yelena Yesha , Naphtali Rishe, Tracking Moving Objects Using Database Technology in DOMINO, Proceedings of the 4th International Workshop on Next Generation Information Technologies and Systems, p.112-119, July 05-07, 1999
• 20: 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 [doi>10.1109/SSDM.1998.688116]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

General Terms:
Experimentation, Theory