{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T17:23:46Z","timestamp":1791566626983,"version":"4.3.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Trajectory similarity queries, including similarity search and similarity join, offer a foundation for many geo-spatial applications. With the rapid increase of streaming trajectory data volumes, e.g., data from mobile phones, vessel monitoring, or traffic systems, many location-based services benefit from online similarity analytics over trajectory data streams, where moving objects continually emit real-time position data. However, most existing studies focus on offline settings, and thus several major challenges remain unanswered in an online setting. To this end, we describe Ghost, a distributed stream processing framework that enables generic, efficient, and scalable online trajectory similarity search and join.<\/jats:p>\n          <jats:p>We propose a novel incremental online similarity computation (IOSC) mechanism to accelerate pair-wise streaming trajectory distance calculation, which supports a broad range of trajectory distance metrics. Compared with previous studies, IOSC reduces the complexity from quadratic to linear in terms of trajectory length. Building on this foundation, we propose histogram-based algorithms that exploit histogram indexes and a series of pruning bounds to enable streaming trajectory similarity search and join. Finally, we extend our methods to the distributed platform Flink for scalability, where a CostPartitioner is developed to ensure parallel processing and workload balancing. An experimental study using two real-life and one synthetic datasets shows that Ghost (i) acquires 6-20\u00d7 efficiency\/throughput gains and one order of magnitude memory overhead savings over state-of-the-art baselines, (ii) achieves 3--8\u00d7 workload balancing gains on Flink, and (iii) exhibits low parameter sensitivity and high robustness.<\/jats:p>","DOI":"10.1145\/3589318","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-25","source":"Crossref","is-referenced-by-count":14,"title":["Ghost: A General Framework for High-Performance Online Similarity Queries over Distributed Trajectory Streams"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-2034-5501","authenticated-orcid":false,"given":"Ziquan","family":"Fang","sequence":"first","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2403-8865","authenticated-orcid":false,"given":"Shenghao","family":"Gong","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5685-7017","authenticated-orcid":false,"given":"Lu","family":"Chen","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9203-5840","authenticated-orcid":false,"given":"Jiachen","family":"Xu","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3816-8450","authenticated-orcid":false,"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9697-7670","authenticated-orcid":false,"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University, Aalborg, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2005. Brinkhoff. https:\/\/iapg.jade-hs.de\/personen\/brinkhoff\/generator\/."},{"key":"e_1_2_2_2_1","unstructured":"2014. Apache Flink. http:\/\/flink.apache.org\/."},{"key":"e_1_2_2_3_1","unstructured":"2014. Apache Spark. http:\/\/spark.apache.org\/."},{"key":"e_1_2_2_4_1","unstructured":"2014. Apache Storm. http:\/\/storm.apache.org\/."},{"key":"e_1_2_2_5_1","unstructured":"2015. T-drive Project. http:\/\/www.geolink.pt\/ecmlpkdd2015-challenge\/dataset.html."},{"key":"e_1_2_2_6_1","unstructured":"2020. AIS Project. https:\/\/marinecadastre.gov\/ais."},{"key":"e_1_2_2_7_1","unstructured":"2023. Movebank. https:\/\/www.movebank.org\/cms\/movebank-main."},{"key":"e_1_2_2_8_1","first-page":"647","article-title":"Clustering of Vehicle Trajectories","volume":"11","author":"Atev Stefan","year":"2010","unstructured":"Stefan Atev, Grant Miller, and Nikolaos P. Papanikolopoulos. 2010. Clustering of Vehicle Trajectories. TITS 11, 3 (2010), 647--657.","journal-title":"TITS"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083691"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Lisi Chen and Gao Cong. 2015. Diversity-aware top-k publish\/subscribe for text stream. In SIGMOD.","DOI":"10.1145\/2723372.2749451"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339502"},{"key":"e_1_2_2_12_1","volume-title":"Ng","author":"Chen Lei","year":"2004","unstructured":"Lei Chen and Raymond T. Ng. 2004. On The Marriage of Lp-norms and Edit Distance. In VLDB. 792--803."},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Lei Chen M. Tamer \u00d6zsu and Vincent Oria. 2005. Robust and Fast Similarity Search for Moving Object Trajectories. In SIGMOD. 491--502.","DOI":"10.1145\/1066157.1066213"},{"key":"e_1_2_2_14_1","volume-title":"Heng Tao Shen, and Xiaofang Zhou","author":"Chen Zaiben","year":"2011","unstructured":"Zaiben Chen, Heng Tao Shen, and Xiaofang Zhou. 2011. Discovering popular routes from trajectories. In ICDE. IEEE Computer Society, 900--911."},{"key":"e_1_2_2_15_1","volume-title":"Loureiro","author":"de Sousa Roniel S.","year":"2020","unstructured":"Roniel S. de Sousa, Azzedine Boukerche, and Antonio A. F. Loureiro. 2020. Vehicle Trajectory Similarity: Models, Methods, and Applications. ACM Comput. Surv. 53, 5 (2020), 94:1--94:32."},{"key":"e_1_2_2_16_1","volume-title":"Real-Time Trajectory Similarity Processing Using Longest Common Subsequence","author":"Ding Jiafeng","unstructured":"Jiafeng Ding, Junhua Fang, Zonglei Zhang, Pengpeng Zhao, Jiajie Xu, and Lei Zhao. 2019. Real-Time Trajectory Similarity Processing Using Longest Common Subsequence. In HPCC. IEEE, 1398--1405."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(87)90165-2"},{"key":"e_1_2_2_18_1","volume-title":"Load Balance for Distributed Real-time Computing Systems","author":"Fang Junhua","unstructured":"Junhua Fang, Rong Zhang, and Aoying Zhou. 2020. Load Balance for Distributed Real-time Computing Systems. Vol. 13. World Scientific."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-019-1940-x"},{"key":"e_1_2_2_20_1","volume-title":"Jensen","author":"Fang Ziquan","year":"2022","unstructured":"Ziquan Fang, Yuntao Du, Xinjun Zhu, Danlei Hu, Lu Chen, Yunjun Gao, and Christian S. Jensen. 2022. Spatio-Temporal Trajectory Similarity Learning in Road Networks. In KDD. 347--356."},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Peng Han Jin Wang Di Yao Shuo Shang and Xiangliang Zhang. 2021. A graph approach for trajectory similarity computation in networks. In KDD. 556--564.","DOI":"10.1145\/3447548.3467337"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0262-6"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2904730"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407818"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Xiucheng Li Kaiqi Zhao Gao Cong Christian S. Jensen and Wei Wei. 2018. Deep representation learning for trajectory similarity computation. In ICDE. 617--628.","DOI":"10.1109\/ICDE.2018.00062"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Jiali Mao Cheqing Jin Xiaoling Wang and Aoying Zhou. 2015. Challenges and issues in trajectory streams clustering upon a Sliding-Window Model. In WISA. 303--308.","DOI":"10.1109\/WISA.2015.42"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3444753"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"de Berg Mark Cheong Otfried van Kreveld Marc and Overmars Mark. 2008. Computational geometry algorithms and applications. Spinger.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_2_29_1","first-page":"61","article-title":"Trajectory data mining: A review of methods and applications","volume":"13","author":"Mazimpaka Jean Damasc\u00e8ne","year":"2016","unstructured":"Jean Damasc\u00e8ne Mazimpaka and Sabine Timpf. 2016. Trajectory data mining: A review of methods and applications. J. Spatial Inf. Sci. 13, 1 (2016), 61--99.","journal-title":"J. Spatial Inf. Sci."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-62005-9_28"},{"key":"e_1_2_2_31_1","volume-title":"Big stream processing systems: an experimental evaluation","author":"Shahverdi Elkhan","unstructured":"Elkhan Shahverdi, Ahmed Awad, and Sherif Sakr. 2019. Big stream processing systems: an experimental evaluation. In ICDEW. IEEE, 53--60."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137630"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183743"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00574-9"},{"key":"e_1_2_2_35_1","unstructured":"Michail Vlachos Dimitrios Gunopulos and George Kollios. 2002. Discovering Similar Multidimensional Trajectories. In ICDE. 673--684."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209978.3209989"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904490"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137655"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Zhao Xu Kristian Kersting and Lorenzo von Ritter. 2017. Stochastic Online Anomaly Analysis for Streaming Time Series. In IJCAI. 3189--3195.","DOI":"10.24963\/ijcai.2017\/445"},{"key":"e_1_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Jianye Yang Wenjie Zhang Xiang Wang Ying Zhang and Xuemin Lin. 2020. Distributed Streaming Set Similarity Join. In ICDE. 565--576.","DOI":"10.1109\/ICDE48307.2020.00055"},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Peilun Yang Hanchen Wang Ying Zhang Lu Qin Wenjie Zhang and Xuemin Lin. 2021. T3S: Effective Representation Learning for Trajectory Similarity Computation. In ICDE. 2183--2188.","DOI":"10.1109\/ICDE51399.2021.00221"},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Di Yao Gao Cong Chao Zhang and Jingping Bi. 2019. A generic seed-guided neural metric learning approach. In ICDE. 1358--1369.","DOI":"10.1109\/ICDE.2019.00123"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Byoung-Kee Yi H. V. Jagadish and Christos Faloutsos. 1998. Efficient Retrieval of Similar Time Sequences Under Time Warping. In ICDE. 201--208.","DOI":"10.1109\/ICDE.1998.655778"},{"key":"e_1_2_2_44_1","doi-asserted-by":"crossref","unstructured":"Yanwei Yu Lei Cao Elke A. Rundensteiner and Qin Wang. 2014. Detecting moving object outliers in massive-scale trajectory streams. In KDD. 422--431.","DOI":"10.1145\/2623330.2623735"},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Haitao Yuan and Guoliang Li. 2019. Distributed In-memory Trajectory Similarity Search and Join on Road Network. In ICDE. 1262--1273.","DOI":"10.1109\/ICDE.2019.00115"},{"key":"e_1_2_2_46_1","volume-title":"Continuous Trajectory Similarity Search for Online Outlier Detection. TKDE","author":"Zhang Dongxiang","year":"2020","unstructured":"Dongxiang Zhang, Zhihao Chang, Sai Wu, Ye Yuan, Kian-Lee Tan, and Gang Chen. 2020. Continuous Trajectory Similarity Search for Online Outlier Detection. TKDE (2020)."},{"key":"e_1_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Haida Zhang Zengfeng Huang Zhewei Wei Wenjie Zhang and Xuemin Lin. 2017. Tracking Matrix Approximation over Distributed Sliding Windows. In ICDE. 833--844.","DOI":"10.1109\/ICDE.2017.133"},{"key":"e_1_2_2_48_1","doi-asserted-by":"crossref","unstructured":"Hanyuan Zhang Xinyu Zhang Qize Jiang Baihua Zheng Zhenbang Sun Weiwei Sun and Changhu Wang. 2020. Trajectory Similarity Learning with Auxiliary Supervision and Optimal Matching. In IJCAI. 3209--3215.","DOI":"10.24963\/ijcai.2020\/444"},{"key":"e_1_2_2_49_1","volume-title":"REPOSE: Distributed top-k trajectory similarity search with local reference point tries. In ICDE. 708--719.","author":"Zheng Bolong","year":"2021","unstructured":"Bolong Zheng, Lianggui Weng, Xi Zhao, Kai Zeng, Xiaofang Zhou, and Christian S Jensen. 2021. REPOSE: Distributed top-k trajectory similarity search with local reference point tries. In ICDE. 708--719."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743025"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589318","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589318","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:14Z","timestamp":1750178774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589318"],"URL":"https:\/\/doi.org\/10.1145\/3589318","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}