{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T20:39:53Z","timestamp":1791146393871,"version":"4.1.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>With the proliferation of wireless communications and geo-positioning, e-services are envisioned that exploit the positions of a set of continuously moving users to provide context-aware functionality to each individual user. Because advances in disk capacities continue to outperform Moore's Law, it becomes increasingly feasible to store online all the position information obtained from the moving e-service users. With the much slower advances in I\/O speeds and many concurrent users, indexing techniques are of the essence in this scenario.Existing indexing techniques come in two forms. Some techniques capture the position of an object up until the time of the most recent position sample, while other techniques represent an object's position as a constant or linear function of time and capture the position from the current time and into the (near) future. This article offers an indexing technique capable of capturing the positions of moving objects at all points in time. The index substantially modifies partial persistence techniques, which support transaction time, to support valid time for monitoring applications. The performance of a timeslice query is independent of the number of past position samples stored for an object. No existing indices exist with these characteristics.<\/jats:p>","DOI":"10.1145\/1132863.1132870","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"255-298","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":88,"title":["Indexing the past, present, and anticipated future positions of moving objects"],"prefix":"10.1145","volume":"31","author":[{"given":"Mindaugas","family":"Pelanis","sequence":"first","affiliation":[{"name":"Aalborg University, Denmark, Ost, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simonas","family":"\u0160altenis","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark, Ost, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark, Ost, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335220"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). 148--157","author":"Agarwal P. K.","unstructured":"Agarwal , P. K. and Har-Peled , S . 2001. Maintaining approximate extent measures of moving points . In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). 148--157 .]] Agarwal, P. K. and Har-Peled, S. 2001. Maintaining approximate extent measures of moving points. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). 148--157.]]"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA). 747--756","author":"Basch J.","unstructured":"Basch , J. , Guibas , L. , and Hershberger , J . 1997. Data structures for mobile data . In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA). 747--756 .]] Basch, J., Guibas, L., and Hershberger, J. 1997. Data structures for mobile data. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA). 747--756.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050028"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015231126594"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 10th International Conference on Management of Data (COMAD).]]","author":"Cai M.","unstructured":"Cai , M. and Revesz , P. Z . 2000. Parametric R-tree: An index structure for moving objects . In Proceedings of the 10th International Conference on Management of Data (COMAD).]] Cai, M. and Revesz, P. Z. 2000. Parametric R-tree: An index structure for moving objects. In Proceedings of the 10th International Conference on Management of Data (COMAD).]]"},{"key":"e_1_2_1_8_1","volume-title":"Online Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR).]]","author":"Chakka V. P.","unstructured":"Chakka , V. P. , Everspaugh , A. , and Patel , J. M . 2003. Indexing large trajectory data sets with SETI . In Online Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR).]] Chakka, V. P., Everspaugh, A., and Patel, J. M. 2003. Indexing large trajectory data sets with SETI. In Online Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR).]]"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 3rd International Conference on Mobile Data Management (MDM). 121--128","author":"Chon H. D.","year":"2002","unstructured":"Chon , H. D. , Agrawal , D. , and El Abbadi , A. 2002 . Query processing for moving objects with space-time grid storage model . In Proceedings of the 3rd International Conference on Mobile Data Management (MDM). 121--128 .]] Chon, H. D., Agrawal, D., and El Abbadi, A. 2002. Query processing for moving objects with space-time grid storage model. In Proceedings of the 3rd International Conference on Mobile Data Management (MDM). 121--128.]]"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 1st International Conference on Mobile and Ubiquitous Systems: Networking and Services. 164--173","author":"\u010civilis A.","unstructured":"\u010civilis , A. , Jensen , C. S. , Nenortait\u0117 , J. , and Pakalnis , S . 2004. Efficient tracking of moving objects with precision guarantees . In Proceedings of the 1st International Conference on Mobile and Ubiquitous Systems: Networking and Services. 164--173 .]] \u010civilis, A., Jensen, C. S., Nenortait\u0117, J., and Pakalnis, S. 2004. Efficient tracking of moving objects with precision guarantees. In Proceedings of the 1st International Conference on Mobile and Ubiquitous Systems: Networking and Services. 164--173.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.80"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 8th International Conference on Extending Database Technology (EDBT). 251--268","author":"Hadjieleftheriou M.","unstructured":"Hadjieleftheriou , M. , Kollios , G. , Tsotras , V. J. , and Gunopulos , D . 2002. Efficient indexing of spatiotemporal objects . In Proceedings of the 8th International Conference on Extending Database Technology (EDBT). 251--268 .]] Hadjieleftheriou, M., Kollios, G., Tsotras, V. J., and Gunopulos, D. 2002. Efficient indexing of spatiotemporal objects. In Proceedings of the 8th International Conference on Extending Database Technology (EDBT). 251--268.]]"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). 768--779","author":"Jensen C. S.","unstructured":"Jensen , C. S. , Lin , D. , and Ooi , B. C . 2004. Query and update efficient B&plus;-tree based indexing of moving objects . In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). 768--779 .]] Jensen, C. S., Lin, D., and Ooi, B. C. 2004. Query and update efficient B&plus;-tree based indexing of moving objects. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). 768--779.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90020-W"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.956099"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115807"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.667079"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071246.1071256"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/647222.760124"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 5th International Workshop on Mobility in Databases and Distributed Systems (MDDS). 693--697","author":"Papadopoulos D.","unstructured":"Papadopoulos , D. , Kollios , G. , Gunopulos , D. , and Tsotras , V. J . 2002. Indexing mobile objects on the plane . In Proceedings of the 5th International Workshop on Mobility in Databases and Distributed Systems (MDDS). 693--697 .]] Papadopoulos, D., Kollios, G., Gunopulos, D., and Tsotras, V. J. 2002. Indexing mobile objects on the plane. In Proceedings of the 5th International Workshop on Mobility in Databases and Distributed Systems (MDDS). 693--697.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007639"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases (VLDB). 395--406","author":"Pfoser D.","unstructured":"Pfoser , D. , Theodoridis , Y. , and Jensen , C. S . 2000. Novel approaches in query processing for moving object trajectories . In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB). 395--406 .]] Pfoser, D., Theodoridis, Y., and Jensen, C. S. 2000. Novel approaches in query processing for moving object trajectories. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB). 395--406.]]"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases (SSTD). 59--78","author":"Porkaew K.","unstructured":"Porkaew , K. , Lasaridis , I. , and Mehrotra , S . 2001. Querying mobile objects in spatio-temporal databases . In Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases (SSTD). 59--78 .]] Porkaew, K., Lasaridis, I., and Mehrotra, S. 2001. Querying mobile objects in spatio-temporal databases. In Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases (SSTD). 59--78.]]"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 4th International Workshop on Algorithm Engineering and Experiments (ALENEX). 178--193","author":"Procopiuc C. M.","unstructured":"Procopiuc , C. M. , Agarwal , P. K. , and Har-Peled , S . 2002. STAR-tree: An efficient self-adjusting index for moving objects . In Proceedings of the 4th International Workshop on Algorithm Engineering and Experiments (ALENEX). 178--193 .]] Procopiuc, C. M., Agarwal, P. K., and Har-Peled, S. 2002. STAR-tree: An efficient self-adjusting index for moving objects. In Proceedings of the 4th International Workshop on Algorithm Engineering and Experiments (ALENEX). 178--193.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335427"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE). 463--472","author":"\u0160altenis S.","unstructured":"\u0160altenis , S. and Jensen , C. S . 2002. Indexing of moving objects for location-based services . In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE). 463--472 .]] \u0160altenis, S. and Jensen, C. S. 2002. Indexing of moving objects for location-based services. In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE). 463--472.]]"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 13th IEEE International Conference on Data Engineering (ICDE). 422--432","author":"Sistla A. P.","unstructured":"Sistla , A. P. , Wolfson , O. , Chamberlain , S. , and Dao , S . 1997. Modeling and querying moving objects . In Proceedings of the 13th IEEE International Conference on Data Engineering (ICDE). 422--432 .]] Sistla, A. P., Wolfson, O., Chamberlain, S., and Dao, S. 1997. Modeling and querying moving objects. In Proceedings of the 13th IEEE International Conference on Data Engineering (ICDE). 422--432.]]"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 2nd International Conference on Mobile Data Management (MDM). 161--172","author":"Song Z.","unstructured":"Song , Z. and Roussopoulos , N . 2001. Hashing moving objects . In Proceedings of the 2nd International Conference on Mobile Data Management (MDM). 161--172 .]] Song, Z. and Roussopoulos, N. 2001. Hashing moving objects. In Proceedings of the 2nd International Conference on Mobile Data Management (MDM). 161--172.]]"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 4th International Conference on Mobile Data Management (MDM). 340--344","author":"Song Z.","unstructured":"Song , Z. and Roussopoulos , N . 2003. SEB-tree: An approach to index continuously moving objects . In Proceedings of the 4th International Conference on Mobile Data Management (MDM). 340--344 .]] Song, Z. and Roussopoulos, N. 2003. SEB-tree: An approach to index continuously moving objects. In Proceedings of the 4th International Conference on Mobile Data Management (MDM). 340--344.]]"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE). 202--213","author":"Sun J.","unstructured":"Sun , J. , Papadias , D. , Tao , Y. , and Liu , B . 2004. Querying about the past, the present and the future in spatio-temporal databases . In Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE). 202--213 .]] Sun, J., Papadias, D., Tao, Y., and Liu, B. 2004. Querying about the past, the present and the future in spatio-temporal databases. In Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE). 202--213.]]"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). 431--440","author":"Tao Y.","unstructured":"Tao , Y. and Papadias , D . 2001. MV3R-tree: A spatio-temporal access method for timestamp and interval queries . In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). 431--440 .]] Tao, Y. and Papadias, D. 2001. MV3R-tree: A spatio-temporal access method for timestamp and interval queries. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). 431--440.]]"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 790--801","author":"Tao Y.","unstructured":"Tao . Y. , Papadias , D. , and Sun , J . 2003. The TPR&ast;-tree: An optimized spatio-temporal access method for predictive queries . In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 790--801 .]] Tao. Y., Papadias, D., and Sun, J. 2003. The TPR&ast;-tree: An optimized spatio-temporal access method for predictive queries. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 790--801.]]"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/581751.581754"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/41.3.185"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 22th International Conference on Very Large Data Bases (VLDB). 168--179","author":"Van den Bercken J.","unstructured":"Van den Bercken , J. and Seeger , B . 1996. Query processing techniques for multiversion access methods . In Proceedings of the 22th International Conference on Very Large Data Bases (VLDB). 168--179 .]] Van den Bercken, J. and Seeger, B. 1996. Query processing techniques for multiversion access methods. In Proceedings of the 22th International Conference on Very Large Data Bases (VLDB). 168--179.]]"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1998.688116"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 14th IEEE International Conference on Data Engineering (ICDE). 588--596","author":"Wolfson O.","unstructured":"Wolfson , O. , Chamberlain , S. , Dao , S. , Jiang , L. , and Mendez , G . 1998. Cost and imprecision in modeling the position of moving objects . In Proceedings of the 14th IEEE International Conference on Data Engineering (ICDE). 588--596 .]] Wolfson, O., Chamberlain, S., Dao, S., Jiang, L., and Mendez, G. 1998. Cost and imprecision in modeling the position of moving objects. In Proceedings of the 14th IEEE International Conference on Data Engineering (ICDE). 588--596.]]"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008782710752"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289075"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132870","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132863.1132870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132863.1132870"],"URL":"https:\/\/doi.org\/10.1145\/1132863.1132870","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}