{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T15:56:17Z","timestamp":1774540577452,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["IIS-0905215, CNS-0931975, CCF-0905014, IIS-1017362"],"award-info":[{"award-number":["IIS-0905215, CNS-0931975, CCF-0905014, IIS-1017362"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006754","name":"U.S. Army Research Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0905215, CNS-0931975, CCF-0905014, IIS-1017362"],"award-info":[{"award-number":["IIS-0905215, CNS-0931975, CCF-0905014, IIS-1017362"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["IIS-0905215, CNS-0931975, CCF-0905014, IIS-1017362"],"award-info":[{"award-number":["IIS-0905215, CNS-0931975, CCF-0905014, IIS-1017362"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>\n            The advance of mobile technologies leads to huge volumes of spatio-temporal data collected in the form of trajectory data streams. In this study, we investigate the problem of discovering object groups that travel together (i.e.,\n            <jats:italic>traveling companions<\/jats:italic>\n            ) from trajectory data streams. Such technique has broad applications in the areas of scientific study, transportation management, and military surveillance. To discover traveling companions, the monitoring system should cluster the objects of each snapshot and intersect the clustering results to retrieve moving-together objects. Since both clustering and intersection steps involve high computational overhead, the key issue of companion discovery is to improve the efficiency of algorithms. We propose the models of closed companion candidates and smart intersection to accelerate data processing. A data structure termed\n            <jats:italic>traveling buddy<\/jats:italic>\n            is designed to facilitate scalable and flexible companion discovery from trajectory streams. The traveling buddies are microgroups of objects that are tightly bound together. By only storing the object relationships rather than their spatial coordinates, the buddies can be dynamically maintained along the trajectory stream with low cost. Based on traveling buddies, the system can discover companions without accessing the object details. In addition, we extend the proposed framework to discover companions on more complicated scenarios with spatial and temporal constraints, such as on the road network and battlefield. The proposed methods are evaluated with extensive experiments on both real and synthetic datasets. Experimental results show that our proposed buddy-based approach is an order of magnitude faster than the baselines and achieves higher accuracy in companion discovery.\n          <\/jats:p>","DOI":"10.1145\/2542182.2542185","type":"journal-article","created":{"date-parts":[[2014,1,2]],"date-time":"2014-01-02T13:09:43Z","timestamp":1388668183000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["A framework of traveling companion discovery on trajectory data streams"],"prefix":"10.1145","volume":"5","author":[{"given":"Lu-An","family":"Tang","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign and Microsoft Research Asia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Zheng","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jing","family":"Yuan","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiawei","family":"Han","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Champaign, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alice","family":"Leung","sequence":"additional","affiliation":[{"name":"BBN Technologies"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen-Chih","family":"Peng","sequence":"additional","affiliation":[{"name":"National Chiao Tung University, Taiwan, ROC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas La","family":"Porta","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, University Park PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,1,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Discovering moving groups of tagged objects. Tech. rep","author":"Aung H.-H.","unstructured":"Aung , H.-H. 2008. Discovering moving groups of tagged objects. Tech. rep ., National University of Singapore . http:\/\/www.nus.edu.sg\/. Aung, H.-H. 2008. Discovering moving groups of tagged objects. Tech. rep., National University of Singapore. http:\/\/www.nus.edu.sg\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1097064.1097091"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347119"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 24th International Conference on Very Large Data Bases (VLDB'98)","author":"Ester M.","unstructured":"Ester , M. , Kriegel , H.-P. , Sander , J. , Wimmer , M. , and Xu , X . 1998. Incremental clustering for mining in a data warehousing environment . In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB'98) . 323--333. Ester, M., Kriegel, H.-P., Sander, J.,Wimmer, M., and Xu, X. 1998. Incremental clustering for mining in a data warehousing environment. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB'98). 323--333."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD'96)","author":"Ester M.","unstructured":"Ester , M. , Kriegel , H.-P. , Sander , J. , and Xu , X . 1996. A density-based algorithm for discovering clusters in large spatial databases with noise . In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD'96) . 226--231. Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD'96). 226--231."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312198"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281230"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183471.1183479"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1032222.1032259"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 18th International Conference on Data Engineering (ICDE'02)","author":"Gunopoulos D.","year":"2002","unstructured":"Gunopoulos , D. 2002 . Discovering similar multidimensional trajectories . In Proceedings of the 18th International Conference on Data Engineering (ICDE'02) . 673--684. Gunopoulos, D. 2002. Discovering similar multidimensional trajectories. In Proceedings of the 18th International Conference on Data Engineering (ICDE'02). 673--684."},{"key":"e_1_2_1_13_1","volume-title":"Data Mining: Concepts and Techniques","author":"Han J.","year":"2006","unstructured":"Han , J. and Kamber , M . 2006 . Data Mining: Concepts and Techniques 2 nd Ed. Morgan Kaufmann . Han, J. and Kamber, M. 2006. Data Mining: Concepts and Techniques 2nd Ed. Morgan Kaufmann.","edition":"2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-2822-7"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI'05)","author":"Horvitz E.","unstructured":"Horvitz , E. , Apacible , J. , Sarin , R. , and Liao , L . 2005. Prediction, expectation, and surprise: Methods, designs, and study of a deployed traffic forecasting service . In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI'05) . Horvitz, E., Apacible, J., Sarin, R., and Liao, L. 2005. Prediction, expectation, and surprise: Methods, designs, and study of a deployed traffic forecasting service. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI'05)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1054"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453971"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_21"},{"key":"e_1_2_1_19_1","unstructured":"Krout T. 2007. Cb manet scenario data distribution. Tech. rep. BBN.  Krout T. 2007. Cb manet scenario data distribution. Tech. rep. BBN."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247546"},{"key":"e_1_2_1_21_1","first-page":"719","article-title":"Supporting frequent updates in r-trees: A bottom-up approach","volume":"18","author":"Lee M.","year":"2003","unstructured":"Lee , M. , Hsu , W. , Jensen , C. S. , Cui , B. , and Teo , K. 2003 . Supporting frequent updates in r-trees: A bottom-up approach . The VLDB J. 18 , 3, 719 -- 738 . Lee, M., Hsu, W., Jensen, C. S., Cui, B., and Teo, K. 2003. Supporting frequent updates in r-trees: A bottom-up approach. The VLDB J. 18, 3, 719--738.","journal-title":"The VLDB J."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases (SSTD'07)","author":"Li X.","unstructured":"Li , X. , Han , J. , Lee , J.-G. , and Gonzalez , H . 2007. Traffic density based discovery of hot routes in road networks . In Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases (SSTD'07) . 441--459. Li, X., Han, J., Lee, J.-G., and Gonzalez, H. 2007. Traffic density based discovery of hot routes in road networks. In Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases (SSTD'07). 441--459."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014129"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920934"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989369"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/PERCOM.2007.23"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453973"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0163-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/525"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453966"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.63"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 12th International Conference on Advances in Spatial and Temporal Databases (SSTD'11)","author":"Tang L.-A.","unstructured":"Tang , L.-A. , Zheng , Y. , Xie , X. , Yuan , J. , Yu , X. , and Han , J . 2011. Retrieving k-nearest neighboring trajectories by a set of point locations . In Proceedings of the 12th International Conference on Advances in Spatial and Temporal Databases (SSTD'11) . 223--241. Tang, L.-A., Zheng, Y., Xie, X., Yuan, J., Yu, X., and Han, J. 2011. Retrieving k-nearest neighboring trajectories by a set of point locations. In Proceedings of the 12th International Conference on Advances in Spatial and Temporal Databases (SSTD'11). 223--241."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.33"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE'04)","author":"Tao Y.","unstructured":"Tao , Y. , Kollios , G. , Considine , J. , Li , F. , and Papadias , D . 2004. Spatio-temporal aggregation using sketches . In Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE'04) . 214. Tao, Y., Kollios, G., Considine, J., Li, F., and Papadias, D. 2004. Spatio-temporal aggregation using sketches. In Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE'04). 214."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989368"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869806"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687753"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516422"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 14th International Conference on Data Engineering (ICDE'98)","author":"Yi B.","unstructured":"Yi , B. , Jagadish , H. V. , and Faloutsos , C . 1998. Efficient retrieval of similar time sequences under time warping . In Proceedings of the 14th International Conference on Data Engineering (ICDE'98) . 201--208. Yi, B., Jagadish, H. V., and Faloutsos, C. 1998. Efficient retrieval of similar time sequences under time warping. In Proceedings of the 14th International Conference on Data Engineering (ICDE'98). 201--208."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1032222.1032258"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 15th Australasian Database Conference (ADC'04)","author":"Zhang Q.","unstructured":"Zhang , Q. and Lin , X . 2004. Clustering moving objects for spatial-temporal selectivity estimation . In Proceedings of the 15th Australasian Database Conference (ADC'04) . 123--130. Zhang, Q. and Lin, X. 2004. Clustering moving objects for spatial-temporal selectivity estimation. In Proceedings of the 15th Australasian Database Conference (ADC'04). 123--130."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497495"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0259-1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.42"},{"key":"e_1_2_1_47_1","first-page":"32","article-title":"GeoLife: A collaborative social networking service among user, location and trajectory","volume":"33","author":"Zheng Y.","year":"2010","unstructured":"Zheng , Y. , Xie , X. , and Ma , W. 2010 . GeoLife: A collaborative social networking service among user, location and trajectory . IEEE Data Engin. Bull. 33 , 2, 32 -- 40 . Zheng, Y., Xie, X., and Ma, W. 2010. GeoLife: A collaborative social networking service among user, location and trajectory. IEEE Data Engin. Bull. 33, 2, 32--40.","journal-title":"IEEE Data Engin. Bull."},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Zheng Y. and Zhou X. 2011. Computing with Spatial Trajectories. Springer.   Zheng Y. and Zhou X. 2011. Computing with Spatial Trajectories. Springer.","DOI":"10.1007\/978-1-4614-1629-6"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 23rd International Conference on Data Engineering (ICDE'07)","author":"Zhu F.","unstructured":"Zhu , F. , Yan , X. , Han , J. , Yu , P. S. , and Cheng , H . 2007. Mining colossal frequent patterns by core pattern fusion . In Proceedings of the 23rd International Conference on Data Engineering (ICDE'07) . 706--715. Zhu, F., Yan, X., Han, J., Yu, P. S., and Cheng, H. 2007. Mining colossal frequent patterns by core pattern fusion. In Proceedings of the 23rd International Conference on Data Engineering (ICDE'07). 706--715."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542182.2542185","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2542182.2542185","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:56Z","timestamp":1750234196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542182.2542185"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1145\/2542182.2542185"],"URL":"https:\/\/doi.org\/10.1145\/2542182.2542185","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}