Prediction and indexing of moving objects with unknown motion patterns

ABSTRACT

Existing methods for peediction spatio-temporal databases assume that objects move according to linear functions. This severely limits their applicability, since in practice movement is more complex, and individual objects may follow drastically diffferent motion patterns. In order to overcome these problems, we first introduce a general framework for monitoring and indexing moving objects, where (i) each boject computes individually the function that accurately captures its movement and (ii) a server indexes the object locations at a coarse level and processes queries using a filter-refinement mechanism. Our second contribution is a novel recursive motion function that supports a broad class of non-linear motion patterns. The function does not presume any a-priori movement but can postulate the particular motion of each object by examining its locations at recent timestamps. Finally. we propse an efficient indexing scheme that faciliates the processing of predicitive queries without false misses.

References

1. {AAE00} Agarwal, P., Arge, L., Erickson, J. Indexing Moving Points. PODS, 2000.
2. {AA03} Aggarwal, C., Agrawal, D. On Nearest Neighbor Indexing of Nonlinear Trajectories. PODS, 2003
3. {BKSS90} Beckmann, N., Kriegel, H., Schneider, R., Seeger, B. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD, 1990.
4. {CC02} Choi, Y., Chung, C. Selectivity Estimation for Spatio-Temporal Queries to Moving Objects. SIGMOD, 2002.
5. {HKT03} Hadjieleftheriou, M., Kollios, G., Tsotras, V. Performance Evaluation of Spatio-temporal Selectivity Estimation Techniques, SSDBM, 2003.
6. {HKTG02} Hadjieleftheriou, M., Kollios, G., Tsotras, V., Gunopulos, D. Efficient Indexing of Spatiotemporal Objects. EDBT, 2002.
7. {ISS03} Iwerks, G., Samet, H., Smith, K. Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates. VLDB, 2003.
8. {KGT99} Kollios, G., Gunopulos, D., Tsotras, V. On Indexing Mobile Objects. PODS, 1999.
9. {PFTV02} Press, W., Flannery, B., Teukolsky, S., Vetterling, W. Numerical Recipes in C++ (second edition). Combridge University Press, ISBN 0-521-75034-2, 2002.
10. {PSTW93} Pagel B., Six, H., Toben, H., Widmayer, P. Towards an Analysis of Rang Query Performance in Spatial Data Structures. PODS, 1993.
11. {SJ02} Saltenis, S., Jensen, C. Indexing of Moving Objects for Location-Based Services. ICDE, 2002.
12. {SJLL00} Saltenis, S., Jensen, C., Leutenegger, S., Lopez, M. Indexing the Positions of Continuously Moving Objects. SIGMOD. 2000.
13. {Tiger} http://www.census.gov/geo/www/tiger/
14. {TP02} Tao, Y., Papadias, D. Time-Parameterized Queries in Spatio-Temporal Databases, SIGMOD, 2002.
15. {TPS03} Tao, Y., Papadia, D., Sun, J. The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries. VLDB, 2003.
16. {TSP03} Tao, Y., Sun, J., Papadias, D. Selectivity Estimation for Predictive Spatio-Temporal Queries. ICDE, 2003.
17. {TUW98} Tayeb, J., Ulusoy, O., Wolfson, O. A. Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal, 41(3):185--200, 1998.

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory