Jignesh M. Patel
ABSTRACT
Moving object databases are required to support queries on a large number of continuously moving objects. A key requirement for indexing methods in this domain is to efficiently support both update and query operations. Previous work on indexing such databases can be broadly divided into categories: indexing the past positions and indexing the future predicted positions. In this paper we focus on an efficient indexing method for indexing the future positions of moving objects.In this paper we propose an indexing method, called STRIPES, which indexes predicted trajectories in a dual transformed space. Trajectories for objects in d-dimensional space become points in a higher-dimensional 2d-space. This dual transformed space is then indexed using a regular hierarchical grid decomposition indexing structure. STRIPES can evaluate a range of queries including time-slice, window, and moving queries. We have carried out extensive experimental evaluation comparing the performance of STRIPES with the best known existing predicted trajectory index (the TPR*-tree), and show that our approach is significantly faster than TPR*-tree for both updates and search queries.
- Agarwal, P. K., Arge, L. and Erickson, J., Indexing Moving Points. In PODS, 2000, 175--186.]] Google Scholar
Digital Library
- Beckmann, N., Kriegel, H.-P., Schneider, R. and Seeger, B., The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In SIGMOD, 1990, 322--331.]] Google ScholarDigital Library
- Bellman, R. Adaptive Control Processes. Princeton University Press., Princeton, NJ, 1961.]]Google Scholar
- Berchtold, S., Keim, D. A. and Kriegel, H.-P., The X-tree: An Index Structure for High-Dimensional Data. In VLDB, 1996, 28--39.]] Google ScholarDigital Library
- Beyer, K., Goldstein, J., Ramakrishnan, R. and Shaft, U., When is "Nearest Neighbor" Meaningful? In Intl. Conf. on Database Theory (ICDT), 1999, 217--235.]] Google ScholarDigital Library
- Cai, M. C., Keshwani, D. and Revesz, P. Z., Parametric Rectangles: A Model for Querying and Animation of Spatiotemporal Satabases. In EDBT, 2000, 430--444.]] Google ScholarDigital Library
- Carey, M. J., DeWitt, D. J., Franklin, M. J., et al., Shoring Up Persistent Applications. In SIGMOD, 1994, 383--394.]] Google ScholarDigital Library
- Chakka, V. P., Everspaugh, A. C. and Patel, J. M., Indexing Large Trajectory Data Sets with SETI. In First Biennial Conf. on Innovative Data Systems Research (CIDR), 2003, 164--175.]]Google Scholar
- Chon, H. D., Agrawal, D. and Abbadi:, A. E., Storage and Retrieval of Moving Objects. In IEEE Intl. Conf. on Mobile Data Management (MDM), 2001, 173--184.]] Google ScholarDigital Library
- Gargantini, I. An Effective Way to Represent Quadtrees. CACM, 25(12) 1982, 905--910.]] Google ScholarDigital Library
- Guting, R. H., Bohlen, M. H., Erwig, M., Jensen, C. S., Lorentzos, N. A., Schneider, M. and Vazirgiannis, M. A Foundation for Representing and Quering Moving Objects. ACM TODS, 25 (1) 2000, 1--42.]] Google ScholarDigital Library
- Guttman, A., R-trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD, 1984, 47--57.]] Google ScholarDigital Library
- Hjaltason, G. R. and Samet, H. Speeding up Construction of PMR Quadtree-based Spatial Indexes. VLDB Journal, 11 (2) 2002, 109--137.]] Google ScholarDigital Library
- Jagadish, H. V., On Indexing Line Segments. In VLDB, 1990, 614--625.]] Google ScholarDigital Library
- Kollios, G., Gunopulos, D. and Tsotras, V. J., On Indexing Mobile Objects. In PODS, 1999, 261--272.]] Google ScholarDigital Library
- Kwon, D., Lee, S. and Lee, S., Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree. In IEEE Intl. Conf. on Mobile Data Management (MDM), 2002, 113--120.]] Google ScholarDigital Library
- Lee, M.-L., Hsu, W., Jensen, C. S., Cui, B. and Teo, K. L., Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. In VLDB, 2003, 608--619.]] Google ScholarDigital Library
- Leutenegger, S. T. and Lopez, M. A., The Effect of Buffering on the Performance of R-trees. In IEEE TKDE, 2000, 33--44.]] Google ScholarDigital Library
- Mokbel, M. F., Ghanem, T. M. and Aref, W. G. Spatio-Temporal Access Methods. IEEE Data Engineering Bulletin, 26 (2) 2003, 40--49.]]Google Scholar
- Nascimento, M. A. and Silva, J. R. O., Towards Historical R-trees. In ACM Symposium on Applied Computing, 1998, 235--240.]] Google ScholarDigital Library
- Nascimento, M. A., Silva, J. R. O. and Theodoridis, Y., Evaluation of Access Structures for Discretely Moving Points. In Intl. Workshop on Spatio-Temporal Database Management (STDBM), 1999, 171--188.]] Google ScholarDigital Library
- Papadias, D., Tao, Y., Kalnis, P. and Zhang, J., Indexing Spatio-temporal Data Warehouses. In ICDE, 2002, 166--175.]] Google ScholarDigital Library
- Pfoser, D., Jensen, C. and Theodoidis, Y., Novel Approaches to the Indexing of Moving Objects Trajectories. In VLDB, 2000, 395--406.]] Google ScholarDigital Library
- Pitoura, E. and Samaras, G. Locating Objects in Mobile Computing. IEEE TKDE, 13 (4) 2001, 571--592.]] Google ScholarDigital Library
- Porkaew, K., Lazaridis, I. and Mehrotra, S., Querying Mobile Objects in Spatio-temporal Databases. In Symposium on Spatial and Temporal Databases (SSTD), 2001, 59--78.]] Google ScholarDigital Library
- Prabhakar, S., Xia, Y. N., Kalashnikov, D. V., Aref, W. G. and Hambrusch, S. E., Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects. In IEEE Transactions on Computers, 2002, 1124--1140.]] Google ScholarDigital Library
- Procopiuc, C. M., Agarwal, P. K. and Har-Peled, S., STAR-Tree: An Efficient Self-adjusting Index for Moving Objects. In 4th Intl. Workshop on Algorithm Engineering and Experiments (ALENEX), 2002, 178--193.]] Google ScholarDigital Library
- Saltenis, S. and Jensen, C. S., Indexing of Moving Objects for Location-Based Service. In ICDE, 2002.]]Google ScholarCross Ref
- Saltenis, S., Jensen, C. S., Leutenegger, S. T. and Lopez, M. A., Indexing the Positions of Continuously Moving Objects. In SIGMOD, 2000, 331--342.]] Google ScholarDigital Library
- Samet, H. The Quadtree and Related Hierarchical Data Structures. Computing Surveys, 16 (2) 1984, 187--260.]] Google ScholarDigital Library
- Song, Z. and Roussopoulos, N., Hashing Moving Objects. In IEEE Intl. Conf. on Mobile Data Management (MDM), 2001, 161--172.]] Google ScholarDigital Library
- Song, Z. X. and Roussopoulos, N., SEB-tree: An Approach to Index Continuously Moving Objects. In IEEE Intl. Conf. on Mobile Data Management (MDM), 2003, 340--344.]] Google ScholarDigital Library
- Tao, Y. and Papadias, D., MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries. In VLDB Journal, 2001, 431--440.]] Google ScholarDigital Library
- Tao, Y., Papadias, D. and Sun, J., The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries. In VLDB, 2003, 790--801.]] Google ScholarDigital Library
- Tayeb, J., Ulusoy, O. and Wolfson, O. A Quadtree-based Dynamic Attribute Indexing Method. Computer Journal, 41 (3) 1998, 185--200.]]Google Scholar
- Theodoridis, Y., Vazirgiannis, M. and Sellis, T. K., Spatio-Temporal Indexing for Large Multimedia Application. In IEEE Intl. Conf. on Multimedia Computing and Systems, 1996, 441--448.]] Google ScholarDigital Library
- Wolfson, O., Xu, B., Chamberlain, S. and Jiang, L., Moving Objects Databases: Issues and Solutions. In Statistical and Scientific Database Management (SSDBM), 1998, 111--122.]] Google ScholarDigital Library
- Xu, X., Han, J. and Lu, W., RT-tree: An Improved R-Tree Index Structure for Spatiotemporal Databases. In Intl. Sym. on Spatial Data Handling, 1990, 1040--1049.]]Google Scholar
- STRIPES: an efficient index for predicted trajectories
Recommendations
The hyperdyadic index and generalized indexing and query with PIQUE
SSDBM '15: Proceedings of the 27th International Conference on Scientific and Statistical Database ManagementMany scientists rely on indexing and query to identify trends and anomalies within extreme-scale scientific data. Compressed bitmap indexing (e.g., FastBit) is the go-to indexing method for many scientific datasets and query workloads. Recently, the ...
Transform-Space View: Performing Spatial Join in the Transform Space Using Original-Space Indexes
Spatial joins find all pairs of objects that satisfy a given spatial relationship. In spatial joins using indexes, original-space indexes such as the R-tree are widely used. An original-space index is the one that indexes objects as represented in the ...
Comparison between the zeroth-order Randić index and the sum-connectivity index
The zeroth-order Randić index and the sum-connectivity index are very popular topological indices in mathematical chemistry. These two indices are based on vertex degrees of graphs and attracted a lot of attention in recent years. Recently Li and Li (...
Comments