{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,19]],"date-time":"2025-10-19T06:04:07Z","timestamp":1760853847474},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n            Nearest neighbor (NN) queries in trajectory databases have received significant attention in the past, due to their applications in spatio-temporal data analysis. More recent work has considered the realistic case where the trajectories are uncertain; however, only simple uncertainty models have been proposed, which do not allow for accurate probabilistic search. In this paper, we fill this gap by addressing probabilistic nearest neighbor queries in databases with uncertain trajectories modeled by stochastic processes, specifically the Markov chain model. We study three nearest neighbor query semantics that take as input a query state or trajectory\n            <jats:italic>q<\/jats:italic>\n            and a time interval, and theoretically evaluate their runtime complexity. Furthermore we propose a sampling approach which uses Bayesian inference to guarantee that sampled trajectories conform to the observation data stored in the database. This sampling approach can be used in Monte-Carlo based approximation solutions. We include an extensive experimental study to support our theoretical results.\n          <\/jats:p>","DOI":"10.14778\/2732232.2732239","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"205-216","source":"Crossref","is-referenced-by-count":48,"title":["Probabilistic nearest neighbor queries on uncertain moving object trajectories"],"prefix":"10.14778","volume":"7","author":[{"given":"Johannes","family":"Niedermayer","sequence":"first","affiliation":[{"name":"Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen"}]},{"given":"Andreas","family":"Z\u00fcfle","sequence":"additional","affiliation":[{"name":"Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen"}]},{"given":"Tobias","family":"Emrich","sequence":"additional","affiliation":[{"name":"Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen"}]},{"given":"Matthias","family":"Renz","sequence":"additional","affiliation":[{"name":"Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen"}]},{"given":"Nikos","family":"Mamoulis","sequence":"additional","affiliation":[{"name":"University of Hong Kong"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Hans-Peter","family":"Kriegel","sequence":"additional","affiliation":[{"name":"Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen"}]}],"member":"320","published-online":{"date-parts":[[2013,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376688"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409635.1409677"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-006-0007-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0185-7"},{"key":"e_1_2_1_7_1","first-page":"512","article-title":"Continuous k-nearest neighbor queries for continuously moving points with updates","author":"Iwerks G. S.","year":"2003","unstructured":"G. S. Iwerks , H. Samet , and K. Smith , \" Continuous k-nearest neighbor queries for continuously moving points with updates ,\" in VLDB , 2003 , pp. 512 -- 523 . G. S. Iwerks, H. Samet, and K. Smith, \"Continuous k-nearest neighbor queries for continuously moving points with updates,\" in VLDB, 2003, pp. 512--523.","journal-title":"VLDB"},{"key":"e_1_2_1_8_1","first-page":"287","article-title":"Continuous nearest neighbor search","author":"Tao Y.","year":"2002","unstructured":"Y. Tao , D. Papadias , and Q. Shen , \" Continuous nearest neighbor search ,\" in Proc. VLDB , 2002 , pp. 287 -- 298 . Y. Tao, D. Papadias, and Q. Shen, \"Continuous nearest neighbor search,\" in Proc. VLDB, 2002, pp. 287--298.","journal-title":"Proc. VLDB"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007637"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.92"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.128"},{"key":"e_1_2_1_12_1","first-page":"133","volume-title":"MDM","author":"Mokhtar H.","year":"2004","unstructured":"H. Mokhtar and J. Su , \" Universal trajectory queries for moving object databases,\" in Proc . MDM , 2004 , pp. 133 -- 144 . H. Mokhtar and J. Su, \"Universal trajectory queries for moving object databases,\" in Proc. MDM, 2004, pp. 133--144."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016028.1016030"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516460"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.94"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2010.76"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.46"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-009-0173-z"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544823"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646518.756858"},{"key":"e_1_2_1_21_1","first-page":"422","article-title":"Modeling and querying moving objects","author":"Prasad Sistla A.","year":"1997","unstructured":"A. Prasad Sistla , O. Wolfson , S. Chamberlain , and S. Dao , \" Modeling and querying moving objects ,\" in Proc. ICDE. IEEE , 1997 , pp. 422 -- 432 . A. Prasad Sistla, O. Wolfson, S. Chamberlain, and S. Dao, \"Modeling and querying moving objects,\" in Proc. ICDE. IEEE, 1997, pp. 422--432.","journal-title":"Proc. ICDE. IEEE"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69497-7_37"},{"key":"e_1_2_1_23_1","first-page":"65","article-title":"Cknn query processing over moving objects with uncertain speeds in road networks","author":"Li G.","year":"2011","unstructured":"G. Li , Y. Li , L. Shu , and P. Fan , \" Cknn query processing over moving objects with uncertain speeds in road networks ,\" in APWeb , 2011 , pp. 65 -- 76 . G. Li, Y. Li, L. Shu, and P. Fan, \"Cknn query processing over moving objects with uncertain speeds in road networks,\" in APWeb, 2011, pp. 65--76.","journal-title":"APWeb"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0249-3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396813"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"J. Niedermayer A. Z\u00fcfle T. Emrich M. Renz N. Mamoulis L. Chen and H.-P. Kriegel \"Probabilistic nearest neighbor queries on uncertain moving object trajectories (technical report) \" 2013 http:\/\/www.dbs.ifi.lmu.de\/Publikationen\/Papers\/TRPNN.pdf.  J. Niedermayer A. Z\u00fcfle T. Emrich M. Renz N. Mamoulis L. Chen and H.-P. Kriegel \"Probabilistic nearest neighbor queries on uncertain moving object trajectories (technical report) \" 2013 http:\/\/www.dbs.ifi.lmu.de\/Publikationen\/Papers\/TRPNN.pdf.","DOI":"10.14778\/2732232.2732239"},{"key":"e_1_2_1_27_1","first-page":"487","article-title":"Fast algorithms for mining association rules","author":"Agrawal R.","year":"1994","unstructured":"R. Agrawal and R. Srikant , \" Fast algorithms for mining association rules ,\" in Proc. VLDB , 1994 , pp. 487 -- 499 . R. Agrawal and R. Srikant, \"Fast algorithms for mining association rules,\" in Proc. VLDB, 1994, pp. 487--499.","journal-title":"Proc. VLDB"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376686"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"issue":"4","key":"e_1_2_1_30_1","first-page":"1","article-title":"Hidden markov models and the baum-welch algorithm","volume":"53","author":"Welch L. R.","year":"2003","unstructured":"L. R. Welch , \" Hidden markov models and the baum-welch algorithm ,\" IEEE Information Theory Society Newsletter , vol. 53 , no. 4 , pp. 1 , 10--13, 2003 . L. R. Welch, \"Hidden markov models and the baum-welch algorithm,\" IEEE Information Theory Society Newsletter, vol. 53, no. 4, pp. 1, 10--13, 2003.","journal-title":"IEEE Information Theory Society Newsletter"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732232.2732239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:19:44Z","timestamp":1672219184000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732232.2732239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.14778\/2732232.2732239"],"URL":"https:\/\/doi.org\/10.14778\/2732232.2732239","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,11]]}}}