More Web Proxy on the site http://driver.im/

research-article

Relaxed group pattern detection over massive-scale trajectories

Authors:

Lisi ChenAuthors Info & Claims

Volume 144, Issue C

Pages 131 - 139

https://doi.org/10.1016/j.future.2023.02.028

Published: 01 July 2023 Publication History

Abstract

The problem of detecting co-movement patterns from trajectories has been extensively studied by data science community. Existing methods are based on filter-and-refine framework, indexing, location point clustering, and search algorithms. Although these techniques are widely used, they require huge computation efforts to find patterns with complex group definition, making them incapable of producing timely results over massive-scale trajectories. In real-life scenarios, especially in pandemic alert and prevention, it is important to produce real-time and high-quality results. In this light, we simplify and relax the definition of co-movement pattern to support fast detection without loss of generality. Specifically, we define co-movement pattern through companion group that consists of at least m moving objects traveling together for k time periods. If an object can form multiple companion groups with others, it belongs to the companion group with the maximum member size. Given a collection of moving object trajectories, the exact algorithm finds companion groups by combining qualified co-movement pairs, which is time-consuming. To enable efficient discovery, a fast community-aware approximate algorithm is developed. Extensive experiments on two real-world datasets are conducted to verify the effectiveness and efficiency of our proposal.

Highlights

•

We introduce companion group concept suitable for epidemic transmission monitoring.

•

We design a community-aware clustering model to efficiently detect group patterns.

•

The performance of our proposal is evaluated through comprehensive experiments.

References

[1]

Vieira M.R., Bakalov P., Tsotras V.J., On-line discovery of flock patterns in spatio-temporal data, in: GIS, ACM, 2009, pp. 286–295.

[2]

Tanaka P.S., Vieira M.R., Kaster D.S., An improved base algorithm for online discovery of flock patterns in trajectories, J. Inf. Data Manag. 7 (1) (2016) 52–67.

[3]

Jeung H., Yiu M.L., Zhou X., Jensen C.S., Shen H.T., Discovery of convoys in trajectory databases, Proc. VLDB Endow. 1 (1) (2008) 1068–1080.

[4]

Li Z., Ding B., Han J., Kays R., Swarm: Mining relaxed temporal moving object clusters, Proc. VLDB Endow. 3 (1) (2010) 723–734.

[5]

Wang Y., Lim E., Hwang S., Efficient mining of group patterns from user movement data, Data Knowl. Eng. 57 (3) (2006) 240–282.

[6]

Li Y., Bailey J., Kulik L., Efficient mining of platoon patterns in trajectory databases, Data Knowl. Eng. 100 (2015) 167–187.

[7]

Zheng K., Zheng Y., Yuan N.J., Shang S., On discovery of gathering patterns from trajectories, in: ICDE, IEEE Computer Society, 2013, pp. 242–253.

[8]

Zheng K., Zheng Y., Yuan N.J., Shang S., Zhou X., Online discovery of gathering patterns over trajectories, TKDE 26 (8) (2014) 1974–1988.

[9]

Xu J., Lu H., Bao Z., IMO: A toolbox for simulating and querying infected moving objects, Proc. VLDB Endow. 13 (12) (2020) 2825–2828.

[10]

Alarabi L., Basalamah S.M., Hendawi A.M., Abdalla M., Traceall: A real-time processing for contact tracing using indoor trajectories, Inf. 12 (5) (2021) 202.

[11]

Liu Y., Zhao K., Cong G., Bao Z., Online anomalous trajectory detection with deep generative sequence modeling, in: ICDE, IEEE, 2020, pp. 949–960.

[12]

Li K., Chen L., Shang S., Wang H., Liu Y., Kalnis P., Yao B., Towards controlling the transmission of diseases: Continuous exposure discovery over massive-scale moving objects, in: IJCAI, ijcai.org, 2022, pp. 3891–3897.

[13]

Chen Z., Li K., Zhou S., Chen L., Shang S., Towards robust trajectory similarity computation: Representation-based spatio-temporal similarity quantification, World Wide Web (2022) 1–24.

[14]

Zheng B., Xu J., Lee W.-C., Lee D.L., Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services, VLDB J. 15 (1) (2006) 21–39.

[15]

Xu X., Yuruk N., Feng Z., Schweiger T.A.J., SCAN: a structural clustering algorithm for networks, in: SIGKDD, ACM, 2007, pp. 824–833.

[16]

Ranu S., Padmanabhan D., Telang A.D., Deshpande P., Raghavan S., Indexing and matching trajectories under inconsistent sampling rates, in: ICDE, IEEE Computer Society, 2015, pp. 999–1010.

[17]

Su H., Zheng K., Wang H., Huang J., Zhou X., Calibrating trajectory data for similarity-based analysis, in: SIGMOD, ACM, 2013, pp. 833–844.

[18]

Pelekis N., Kopanakis I., Kotsifakos E.E., Frentzos E., Theodoridis Y., Clustering trajectories of moving objects in an uncertain world, in: ICDM, IEEE Computer Society, 2009, pp. 417–427.

[19]

Lee J., Han J., Whang K., Trajectory clustering: a partition-and-group framework, in: SIGKDD, ACM, 2007, pp. 593–604.

[20]

Li Z., Lee J., Li X., Han J., Incremental clustering for trajectories, in: DASFAA, in: Lecture Notes in Computer Science, vol. 5982, Springer, 2010, pp. 32–46.

[21]

Li H., Liu J., Wu K., Yang Z., Liu R.W., Xiong N., Spatio-temporal vessel trajectory clustering based on data mapping and density, IEEE Access 6 (2018) 58939–58954.

[22]

Li X., Zhao K., Cong G., Jensen C.S., Wei W., Deep representation learning for trajectory similarity computation, in: ICDE, IEEE Computer Society, 2018, pp. 617–628.

[23]

Zhang Y., Liu A., Liu G., Li Z., Li Q., Deep representation learning of activity trajectory similarity computation, in: ICWS, IEEE, 2019, pp. 312–319.

[24]

Yao D., Cong G., Zhang C., Bi J., Computing trajectory similarity in linear time: A generic seed-guided neural metric learning approach, in: ICDE, IEEE, 2019, pp. 1358–1369.

[25]

Yuan J., Zheng Y., Xie X., Sun G., Driving with knowledge from the physical world, in: SIGKDD, ACM, 2011, pp. 316–324.

[26]

Yuan J., Zheng Y., Zhang C., Xie W., Xie X., Sun G., Huang Y., T-drive: driving directions based on taxi trajectories, in: ACM-GIS, ACM, 2010, pp. 99–108.

[27]

Guttman A., R-trees: A dynamic index structure for spatial searching, in: SIGMOD, ACM Press, 1984, pp. 47–57.

[28]

Han P., Wang J., Yao D., Shang S., Zhang X., A graph-based approach for trajectory similarity computation in spatial networks, in: Zhu F., Ooi B.C., Miao C. (Eds.), KDD, ACM, 2021, pp. 556–564.

[29]

Yang C., Chen L., Wang H., Shang S., Towards efficient selection of activity trajectories based on diversity and coverage, in: AAAI, AAAI Press, 2021, pp. 689–696.

[30]

Chen L., Shang S., Feng S., Kalnis P., Parallel subtrajectory alignment over massive-scale trajectory data, in: Zhou Z. (Ed.), IJCAI, ijcai.org, 2021, pp. 3613–3619.

[31]

Shang S., Ding R., Zheng K., Jensen C.S., Kalnis P., Zhou X., Personalized trajectory matching in spatial networks, VLDB J. 23 (3) (2014) 449–468.

Digital Library

[32]

Shang S., Zheng K., Jensen C.S., Yang B., Kalnis P., Li G., Wen J., Discovery of path nearby clusters in spatial networks, TKDE 27 (6) (2015) 1505–1518.

[33]

Shang S., Chen L., Jensen C.S., Wen J., Kalnis P., Searching trajectories by regions of interest, TKDE 29 (7) (2017) 1549–1562.

[34]

Shang S., Chen L., Wei Z., Jensen C.S., Zheng K., Kalnis P., Trajectory similarity join in spatial networks, Proc. VLDB Endow. 10 (11) (2017) 1178–1189.

[35]

Shang S., Chen L., Wei Z., Jensen C.S., Zheng K., Kalnis P., Parallel trajectory similarity joins in spatial networks, VLDB J. 27 (3) (2018) 395–420.

[36]

Chen L., Shang S., Jensen C.S., Yao B., Kalnis P., Parallel semantic trajectory similarity join, in: ICDE, IEEE, 2020, pp. 997–1008.

[37]

Zhao Y., Shang S., Wang Y., Zheng B., Nguyen Q.V.H., Zheng K., REST: a reference-based framework for spatio-temporal trajectory compression, in: Y. Guo F. Farooq (Ed.), SIGMOD, ACM, 2018, pp. 2797–2806.

[38]

Liu J., Zhao K., Sommer P., Shang S., Kusy B., Lee J., Jurdak R., A novel framework for online amnesic trajectory compression in resource-constrained environments, IEEE Trans. Knowl. Data Eng. 28 (11) (2016) 2827–2841.

[39]

Liu J., Zhao K., Sommer P., Shang S., Kusy B., Jurdak R., Bounded quadrant system: Error-bounded trajectory compression on the go, in: Gehrke J., Lehner W., Shim K., Cha S.K., Lohman G.M. (Eds.), ICDE, IEEE Computer Society, 2015, pp. 987–998.

[40]

Shang S., Yuan B., Deng K., Xie K., Zheng K., Zhou X., PNN query processing on compressed trajectories, GeoInformatica 16 (3) (2012) 467–496.

[41]

Yao B., Chen Z., Gao X., Shang S., Ma S., Guo M., Flexible aggregate nearest neighbor queries in road networks, in: ICDE, IEEE Computer Society, 2018, pp. 761–772.

[42]

Han P., Li Z., Liu Y., Zhao P., Li J., Wang H., Shang S., Contextualized point-of-interest recommendation, in: Bessiere C. (Ed.), IJCAI, ijcai.org, 2020, pp. 2484–2490.

[43]

Han P., Shang S., Sun A., Zhao P., Zheng K., Kalnis P., AUC-MF: point of interest recommendation with AUC maximization, in: ICDE, IEEE, 2019, pp. 1558–1561.

[44]

Shang S., Chen L., Zheng K., Jensen C.S., Wei Z., Kalnis P., Parallel trajectory-to-location join, IEEE Trans. Knowl. Data Eng. 31 (6) (2019) 1194–1207.

[45]

Feng S., Tran L.V., Cong G., Chen L., Li J., Li F., HME: A hyperbolic metric embedding approach for next-poi recommendation, in: SIGIR, ACM, 2020, pp. 1429–1438.

[46]

Rao X., Chen L., Liu Y., Shang S., Yao B., Han P., Graph-flashback network for next location recommendation, in: KDD, ACM, 2022, pp. 1463–1471.

[47]

Guo D., Zhu Y., Xu W., Shang S., Ding Z., How to find appropriate automobile exhibition halls: Towards a personalized recommendation service for auto show, Neurocomputing 213 (2016) 95–101.

[48]

Li K., Chen L., Shang S., Kalnis P., Yao B., Traffic congestion alleviation over dynamic road networks: Continuous optimal route combination for trip query streams, in: Zhou Z. (Ed.), IJCAI, ijcai.org, 2021, pp. 3656–3662.

[49]

Li K., Chen L., Shang S., Towards alleviating traffic congestion: Optimal route planning for massive-scale trips, in: Bessiere C. (Ed.), IJCAI, ijcai.org, 2020, pp. 3400–3406.

[50]

Chen L., Shang S., Jensen C.S., Yao B., Zhang Z., Shao L., Effective and efficient reuse of past travel behavior for route recommendation, in: Teredesai A., Kumar V., Li Y., Rosales R., Terzi E., Karypis G. (Eds.), KDD, ACM, 2019, pp. 488–498.

[51]

Chen L., Shang S., Guo T., Real-time route search by locations, in: AAAI, AAAI Press, 2020, pp. 574–581.

[52]

Chen L., Shang S., Yao B., Li J., Pay your trip for traffic congestion: Dynamic pricing in traffic-aware road networks, in: AAAI, AAAI Press, 2020, pp. 582–589.

[53]

Shang S., Ding R., Yuan B., Xie K., Zheng K., Kalnis P., User oriented trajectory search for trip recommendation, in: Rundensteiner E.A., Markl V., Manolescu I., Amer-Yahia S., Naumann F., Ari I. (Eds.), EDBT, ACM, 2012, pp. 156–167.

[54]

Liu K., Li Y., Ding Z., Shang S., Zheng K., Benchmarking big data for trip recommendation, in: ICCCN, IEEE, 2014, pp. 1–6.

[55]

Shang S., Guo D., Liu J., Wen J., Prediction-based unobstructed route planning, Neurocomputing 213 (2016) 147–154.

[56]

Shang S., Chen L., Wei Z., Jensen C.S., Wen J., Kalnis P., Collective travel planning in spatial networks, TKDE 28 (5) (2016) 1132–1146.

[57]

Shang S., Lu H., Pedersen T.B., Xie X., Finding traffic-aware fastest paths in spatial networks, in: SSTD, in: Lecture Notes in Computer Science, vol. 8098, Springer, 2013, pp. 128–145.

[58]

Shang S., Lu H., Pedersen T.B., Xie X., Modeling of traffic-aware travel time in spatial networks, in: 2013 IEEE 14th International Conference on Mobile Data Management, Vol. 1, IEEE Computer Society, 2013, pp. 247–250.

[59]

Rao X., Wang H., Zhang L., Li J., Shang S., Han P., FOGS: first-order gradient supervision with learning-based graph for traffic flow forecasting, in: Raedt L.D. (Ed.), IJCAI, ijcai.org, 2022, pp. 3926–3932.

[60]

Liu A., Wang W., Shang S., Li Q., Zhang X., Efficient task assignment in spatial crowdsourcing with worker and task privacy protection, GeoInformatica 22 (2) (2018) 335–362.

[61]

Fan Q., Zhang D., Wu H., Tan K., A general and parallel platform for mining co-movement patterns over large-scale trajectories, Proc. VLDB Endow. 10 (4) (2016) 313–324.

Digital Library

[62]

Naserian E., Wang X., Xu X., Dong Y., Discovery of loose travelling companion patterns from human trajectories, in: HPCC, IEEE Computer Society, 2016, pp. 1238–1245.

[63]

Shein T.T., Puntheeranurak S., Imamura M., Discovery of loose group companion from trajectory data streams, IEEE Access 8 (2020) 85856–85868.

[64]

Fang Z., Gao Y., Pan L., Chen L., Miao X., Jensen C.S., Coming: A real-time co-movement mining system for streaming trajectories, in: Maier D., Pottinger R., Doan A., Tan W., Alawini A., Ngo H.Q. (Eds.), SIGMOD, ACM, 2020, pp. 2777–2780.

[65]

Chen L., Gao Y., Fang Z., Miao X., Jensen C.S., Guo C., Real-time distributed co-movement pattern detection on streaming trajectories, Proc. VLDB Endow. 12 (10) (2019) 1208–1220.

[66]

Zhao Y., Chen Q., Cao W., Yang J., Xiong J., Gui G., Deep learning for risk detection and trajectory tracking at construction sites, IEEE Access 7 (2019) 30905–30912.

[67]

Yao D., Zhang C., Zhu Z., Huang J., Bi J., Trajectory clustering via deep representation learning, in: IJCNN, IEEE, 2017, pp. 3880–3887.

[68]

Boyle J., Nawaz T., Ferryman J.M., Deep trajectory representation-based clustering for motion pattern extraction in videos, in: AVSS, IEEE Computer Society, 2017, pp. 1–6.

[69]

Fang Z., Du Y., Chen L., Hu Y., Gao Y., Chen G., E2dtc: An end to end deep trajectory clustering framework via self-training, in: ICDE, IEEE, 2021, pp. 696–707.

[70]

Chen L., Shang S., Yang C., Li J., Spatial keyword search: a survey, GeoInformatica 24 (1) (2020) 85–106.

[71]

Li M., Chen L., Cong G., Gu Y., Yu G., Efficient processing of location-aware group preference queries, in: CIKM, ACM, 2016, pp. 559–568.

[72]

Shang S., Guo D., Liu J., Zheng K., Wen J., Finding regions of interest using location based social media, Neurocomputing 173 (2016) 118–123.

[73]

Chen L., Shang S., Approximate spatio-temporal top-k publish/subscribe, World Wide Web 22 (5) (2019) 2153–2175.

[74]

Xu Y., Chen L., Yao B., Shang S., Zhu S., Zheng K., Li F., Location-based top-k term querying over sliding window, in: WISE, in: Lecture Notes in Computer Science, vol. 10569, Springer, 2017, pp. 299–314.

[75]

Chen L., Shang S., Jensen C.S., Xu J., Kalnis P., Yao B., Shao L., Top-k term publish/subscribe for geo-textual data streams, VLDB J. 29 (5) (2020) 1101–1128.

[76]

Zhao K., Chen L., Cong G., Topic exploration in spatio-temporal document collections, in: SIGMOD, ACM, 2016, pp. 985–998.

[77]

Chen L., Shang S., Region-based message exploration over spatio-temporal data streams, in: AAAI, AAAI Press, 2019, pp. 873–880.

[78]

Chen L., Shang S., Zheng K., Kalnis P., Cluster-based subscription matching for geo-textual data streams, in: ICDE, IEEE, 2019, pp. 890–901.

[79]

Li X., Cheng Y., Cong G., Chen L., Discovering pollution sources and propagation patterns in urban area, in: KDD, ACM, 2017, pp. 1863–1872.

[80]

Han J., Zheng K., Sun A., Shang S., Wen J., Discovering neighborhood pattern queries by sample answers in knowledge base, in: ICDE, IEEE Computer Society, 2016, pp. 1014–1025.

Cited By

Anowar MShamail AAlbertsen AHall BThielen TRiemersma BTrajcevski G(2024)Detecting and Visualizing Bond-Forming Convoys in Atomic and Molecular TrajectoriesProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691264(657-660)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3678717.3691264
Francia MGallinucci EGolfarelli M(2024)Colossal Trajectory MiningExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.122055238:PDOnline publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.122055
Zhang JYu JShang SChen LFeng S(2024)Continuous frequent contact detection over moving objectsGeoinformatica10.1007/s10707-023-00501-928:2(271-290)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10707-023-00501-9
Show More Cited By

Recommendations

Clustering and aggregating clues of trajectories for mining trajectory patterns and routes

In this paper, we propose a new trajectory pattern mining framework, namely Clustering and Aggregating Clues of Trajectories (CACT), for discovering trajectory routes that represent the frequent movement behaviors of a user. In addition to spatial and ...
A new dissimilarity measure for trajectories with applications in anomaly detection
CIARP'10: Proceedings of the 15th Iberoamerican congress conference on Progress in pattern recognition, image analysis, computer vision, and applications

Trajectory clustering has been used to very effectively in the detection of anomalous behavior in video sequences. A key point in trajectory clustering is how to measure the (dis)similarity between two trajectories. This paper deals with a new ...
A Unifying Framework of Mining Trajectory Patterns of Various Temporal Tightness
Discovering trajectory patterns is shown to be very useful in learning interactions between moving objects. Many types of trajectory patterns have been proposed in the literature, but previous methods were developed for only a specific type of trajectory ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Future Generation Computer Systems

Future Generation Computer Systems Volume 144, Issue C

Jul 2023

344 pages

ISSN:0167-739X

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 July 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Anowar MShamail AAlbertsen AHall BThielen TRiemersma BTrajcevski G(2024)Detecting and Visualizing Bond-Forming Convoys in Atomic and Molecular TrajectoriesProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691264(657-660)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3678717.3691264
Francia MGallinucci EGolfarelli M(2024)Colossal Trajectory MiningExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.122055238:PDOnline publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.122055
Zhang JYu JShang SChen LFeng S(2024)Continuous frequent contact detection over moving objectsGeoinformatica10.1007/s10707-023-00501-928:2(271-290)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10707-023-00501-9
Wang CChen LFeng SShang S(2024)Flexible Contact Correlation Learning on Spatio-Temporal TrajectoriesDatabase Systems for Advanced Applications10.1007/978-981-97-5552-3_10(152-168)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5552-3_10

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents