{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T15:51:48Z","timestamp":1787241108600,"version":"build-2736575974"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,6,1]],"date-time":"2006-06-01T00:00:00Z","timestamp":1149120000000},"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,6]]},"abstract":"<jats:p>\n                    Cars, aircraft, mobile cell phones, ships, tanks, and mobile robots all have the common property that they are moving objects. A kinematic representation can be used to describe the location of these objects as a function of time. For example, a moving point can be represented by the function\n                    <jats:italic>p<\/jats:italic>\n                    (\n                    <jats:italic>t<\/jats:italic>\n                    ) =\n                    <jats:italic>\n                      x\n                      <jats:sup>\u2192<\/jats:sup>\n                    <\/jats:italic>\n                    <jats:sub>0<\/jats:sub>\n                    + (\n                    <jats:italic>t<\/jats:italic>\n                    -\n                    <jats:italic>t<\/jats:italic>\n                    <jats:sub>0<\/jats:sub>\n                    )\n                    <jats:italic>\n                      v\n                      <jats:sup>\u2192<\/jats:sup>\n                    <\/jats:italic>\n                    , where\n                    <jats:italic>\n                      x\n                      <jats:sup>\u2192<\/jats:sup>\n                    <\/jats:italic>\n                    <jats:sub>0<\/jats:sub>\n                    is the start location,\n                    <jats:italic>t<\/jats:italic>\n                    <jats:sub>0<\/jats:sub>\n                    is the start time, and\n                    <jats:italic>\n                      v\n                      <jats:sup>\u2192<\/jats:sup>\n                    <\/jats:italic>\n                    is its velocity vector. Instead of storing the location of the object at a given time in a database, the coefficients of the function are stored. When an object's behavior changes enough so that the function describing its location is no longer accurate, the function coefficients for the object are updated. Because the location of each object is represented as a function of time, spatial query results can change even when no transactions update the database. We present efficient algorithms to maintain\n                    <jats:italic>k<\/jats:italic>\n                    -nearest neighbor, and spatial join queries in this domain as time advances and updates occur. We assume no previous knowledge of what the updates will be before they occur. We experimentally compare these new algorithms with more straight forward adaptations of previous work to support updates. Experiments are conducted using synthetic uniformly distributed data, and real aircraft flight data. The primary metric of comparison is the number of I\/O disk accesses needed to maintain the query results and the supporting data structures.\n                  <\/jats:p>","DOI":"10.1145\/1138394.1138396","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T10:14:26Z","timestamp":1153822466000},"page":"485-536","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":44,"title":["Maintenance of\n                    <i>K<\/i>\n                    -nn and spatial join queries on continuously moving points"],"prefix":"10.1145","volume":"31","author":[{"given":"Glenn S.","family":"Iwerks","sequence":"first","affiliation":[{"name":"The University of Maryland at College Park\/The MITRE Corporation, McLean, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hanan","family":"Samet","sequence":"additional","affiliation":[{"name":"The University of Maryland at College Park, College Park, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kenneth P.","family":"Smith","sequence":"additional","affiliation":[{"name":"The MITRE Corporation, McLean, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335220"},{"key":"e_1_2_1_2_1","first-page":"25","article-title":"Advances in indexing for mobile objects","volume":"25","author":"Agarwal P. K.","year":"2002","unstructured":"Agarwal , P. K. and Procopiuc , C. M. 2002 . Advances in indexing for mobile objects . IEEE Bull. Tech. Comm. Data Eng. 25 , 2, 25 -- 34 .]] Agarwal, P. K. and Procopiuc, C. M. 2002. Advances in indexing for mobile objects. IEEE Bull. Tech. Comm. Data Eng. 25, 2, 25--34.]]","journal-title":"IEEE Bull. Tech. Comm. Data Eng."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645339.650131"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Basch J.","unstructured":"Basch , J. , Guibas , L. J. , and Hershberger , J . 1997. Data structures for mobile data . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms ( New Orleans, LA). ACM, New York, 747--756.]] Basch, J., Guibas, L. J., and Hershberger, J. 1997. Data structures for mobile data. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA). ACM, New York, 747--756.]]"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Database Engineering and Applications Symposium (IDEAS) (Edmonton, Ont., Canada). 44--53","author":"Benetis R.","unstructured":"Benetis , R. , Jensen , C. , Karciauskas , G. , and Saltenis , S . 2002. Nearest neighbor and reverse nearest neighbor queries for moving objects . In Proceedings of the International Database Engineering and Applications Symposium (IDEAS) (Edmonton, Ont., Canada). 44--53 .]] Benetis, R., Jensen, C., Karciauskas, G., and Saltenis, S. 2002. Nearest neighbor and reverse nearest neighbor queries for moving objects. In Proceedings of the International Database Engineering and Applications Symposium (IDEAS) (Edmonton, Ont., Canada). 44--53.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170075"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/84537.84545"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031255"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/352958.352963"},{"key":"e_1_2_1_13_1","unstructured":"G\u00fcting R. H. and Schneider M. 2005. Moving Objects Databases. Morgan-Kaufmann San Francisco CA.]]  G\u00fcting R. H. and Schneider M. 2005. Moving Objects Databases. Morgan-Kaufmann San Francisco CA.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 21st International Conference on Very Large Data Bases","author":"Hellerstein J. M.","unstructured":"Hellerstein , J. M. , Naughton , J. F. , and Pfeffer , A . 1995. Generalized search trees for database systems . In Proceedings of the 21st International Conference on Very Large Data Bases ( Zurich, Switzerland). 562--573.]] Hellerstein, J. M., Naughton, J. F., and Pfeffer, A. 1995. Generalized search trees for database systems. In Proceedings of the 21st International Conference on Very Large Data Bases (Zurich, Switzerland). 562--573.]]"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276326"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases","author":"Iwerks G. S.","unstructured":"Iwerks , G. S. , Samet , H. , and Smith , K . 2003. Continuous k-nearest neighbor queries for continuously moving points with updates . In Proceedings of the 29th International Conference on Very Large Data Bases ( Berlin, Germany). 512--523.]] Iwerks, G. S., Samet, H., and Smith, K. 2003. Continuous k-nearest neighbor queries for continuously moving points with updates. In Proceedings of the 29th International Conference on Very Large Data Bases (Berlin, Germany). 512--523.]]"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases","author":"Iwerks G. S.","unstructured":"Iwerks , G. S. , Samet , H. , and Smith , K . 2004. Maintenance of spatial semijoin queries on moving points . In Proceedings of the 30th International Conference on Very Large Data Bases ( Toronto, Ont., Canada).]] Iwerks, G. S., Samet, H., and Smith, K. 2004. Maintenance of spatial semijoin queries on moving points. In Proceedings of the 30th International Conference on Very Large Data Bases (Toronto, Ont., Canada).]]"},{"key":"e_1_2_1_20_1","first-page":"2","article-title":"Towards increasingly update efficient moving-object indexing","volume":"25","author":"Jensen C. S.","year":"2002","unstructured":"Jensen , C. S. and Saltenis , S. 2002 . Towards increasingly update efficient moving-object indexing . IEEE Bull. Tech. Comm. Data Eng. 25 , 2 (June), 35--40.]] Jensen, C. S. and Saltenis, S. 2002. Towards increasingly update efficient moving-object indexing. IEEE Bull. Tech. Comm. Data Eng. 25, 2 (June), 35--40.]]","journal-title":"IEEE Bull. Tech. Comm. Data Eng."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:DAPD.0000013068.25976.88"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/46.6.680"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233337"},{"key":"e_1_2_1_24_1","first-page":"2","article-title":"Spatio-temporal access methods","volume":"26","author":"Mokbel M. F.","year":"2003","unstructured":"Mokbel , M. F. , Ghanem , T. M. , and Aref , W. G. 2003 . Spatio-temporal access methods . IEEE Bull. Tech. Comm. Data Eng. 26 , 2 (June), 40--49.]] Mokbel, M. F., Ghanem, T. M., and Aref, W. G. 2003. Spatio-temporal access methods. IEEE Bull. Tech. Comm. Data Eng. 26, 2 (June), 40--49.]]","journal-title":"IEEE Bull. Tech. Comm. Data Eng."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007638"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543638"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.843167"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the International Workshop on Spatio-Temporal Database Management","author":"Nascimento M. A.","unstructured":"Nascimento , M. A. , Silva , R. , and Theodoridis , Y . 1999. Evaluation of access structures for discretely moving points . In Proceedings of the International Workshop on Spatio-Temporal Database Management ( Edinburgh, UK), 171--188.]] Nascimento, M. A., Silva, R., and Theodoridis, Y. 1999. Evaluation of access structures for discretely moving points. In Proceedings of the International Workshop on Spatio-Temporal Database Management (Edinburgh, UK), 171--188.]]"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.404027"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233338"},{"key":"e_1_2_1_31_1","first-page":"2","article-title":"Indexing the trajectories of moving objects","volume":"25","author":"Pfoser D.","year":"2002","unstructured":"Pfoser , D. 2002 . Indexing the trajectories of moving objects . IEEE Bull. Tech. Comm. Data Eng 25 , 2 (June), 3--9.]] Pfoser, D. 2002. Indexing the trajectories of moving objects. IEEE Bull. Tech. Comm. Data Eng 25, 2 (June), 3--9.]]","journal-title":"IEEE Bull. Tech. Comm. Data Eng"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the Advances in Spatial Databases---Sixth International Symposium, SSD'99","author":"Pfoser D.","unstructured":"Pfoser , D. and Jensen , C. S . 1999. Capturing the uncertainty of moving-object representations . In Proceedings of the Advances in Spatial Databases---Sixth International Symposium, SSD'99 ( Hong Kong). Lecture Notes in Computer Science, vol 1651. Springer-Verlag, New York, 111--132.]] Pfoser, D. and Jensen, C. S. 1999. Capturing the uncertainty of moving-object representations. In Proceedings of the Advances in Spatial Databases---Sixth International Symposium, SSD'99 (Hong Kong). Lecture Notes in Computer Science, vol 1651. Springer-Verlag, New York, 111--132.]]"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments","author":"Procopiuc C. M.","unstructured":"Procopiuc , C. M. , Agarwal , P. K. , and Har , S. Peled . 2002. Star-tree: An efficient self-adjusting index for moving objects . In Proceedings of the Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments ( San Francicsco, CA). 178--193.]] Procopiuc, C. M., Agarwal, P. K., and Har, S.Peled. 2002. Star-tree: An efficient self-adjusting index for moving objects. In Proceedings of the Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments (San Francicsco, CA). 178--193.]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023403908170"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335427"},{"key":"e_1_2_1_37_1","volume-title":"The Design and Analysis of Spatial Data Structures","author":"Samet H.","unstructured":"Samet , H. 1990. The Design and Analysis of Spatial Data Structures . Addison-Wesley , Reading, MA .]] Samet, H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA.]]"},{"key":"e_1_2_1_38_1","unstructured":"SCIS. 1996. IEEE Std. 1278 1-1995. IEEE Computer Society Standards Committee on Interactive Simulation USA.]]  SCIS. 1996. IEEE Std. 1278 1-1995. IEEE Computer Society Standards Committee on Interactive Simulation USA.]]"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 13th IEEE Conference on Data Engineering (ICDE)","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 Conference on Data Engineering (ICDE) ( Birmingham, UK). IEEE Computer Society Press, Los Alamitos, CA, 422--432.]] Sistla, A. P., Wolfson, O., Chamberlain, S., and Dao, S. 1997. Modeling and querying moving objects. In Proceedings of the 13th IEEE Conference on Data Engineering (ICDE) (Birmingham, UK). IEEE Computer Society Press, Los Alamitos, CA, 422--432.]]"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the Advances in Spatial and Temporal Databases (SSTD)","volume":"2121","author":"Song Z.","unstructured":"Song , Z. and Roussopoulos , N . 2001. K-nearest neighbor search for moving query point . In Proceedings of the Advances in Spatial and Temporal Databases (SSTD) ( Redondo Beach, CA). Lecture Notes in Computer Science , vol. 2121 . Springer-Verlag, New York, 79--96.]] Song, Z. and Roussopoulos, N. 2001. K-nearest neighbor search for moving query point. In Proceedings of the Advances in Spatial and Temporal Databases (SSTD) (Redondo Beach, CA). Lecture Notes in Computer Science, vol. 2121. Springer-Verlag, New York, 79--96.]]"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/777943.777944"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases","author":"Tao Y.","unstructured":"Tao , Y. , Papadias , D. , and Sun , J . 2003a. 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 ( Berlin, Germany). 790--801.]] Tao, Y., Papadias, D., and Sun, J. 2003a. 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 (Berlin, Germany). 790--801.]]"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of 19th IEEE International Conference on Data Engineering (ICDE)","author":"Tao Y.","unstructured":"Tao , Y. , Sun , J. , and Papadias , D . 2003b. Selectivity estimation for predictive spatio-temporal queries . In Proceedings of 19th IEEE International Conference on Data Engineering (ICDE) ( Bangalore, India). IEEE Computer Society Press, Los Alamitos, CA, 417--428.]] Tao, Y., Sun, J., and Papadias, D. 2003b. Selectivity estimation for predictive spatio-temporal queries. In Proceedings of 19th IEEE International Conference on Data Engineering (ICDE) (Bangalore, India). IEEE Computer Society Press, Los Alamitos, CA, 417--428.]]"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/41.3.185"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT)","author":"Trajcevski G.","unstructured":"Trajcevski , G. , Scheuermann , P. , Wolfson , O. , and Nedungadi , N . 2004a. CAT: Correct answers of continuous queries using triggers . In Proceedings of the International Conference on Extending Database Technology (EDBT) ( Heraklion, Greece). 837--840.]] Trajcevski, G., Scheuermann, P., Wolfson, O., and Nedungadi, N. 2004a. CAT: Correct answers of continuous queries using triggers. In Proceedings of the International Conference on Extending Database Technology (EDBT) (Heraklion, Greece). 837--840.]]"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016028.1016030"},{"key":"e_1_2_1_47_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_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.128"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2004.61"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138394.1138396","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1138394.1138396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:41Z","timestamp":1750249121000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138394.1138396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1145\/1138394.1138396"],"URL":"https:\/\/doi.org\/10.1145\/1138394.1138396","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]},"assertion":[{"value":"2006-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}