Traveling Companions Discovery from Streaming Trajectories
Advanced mobile and tracking devices have generated vast trajectory data streams, leading to the exploration of companionship in moving objects. The study focuses on discovering groups of objects moving together, crucial for applications like animal behavior analysis, traffic management, and anti-crime measures. With a motivation example highlighting the identification process, the problem formulation aims to find 'traveling companion' sets meeting specific size and duration criteria from trajectory data snapshots.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
On Discovery of Traveling Companions from Streaming Trajectories Lu-An Tang, Yu Zheng, Jing Yuan, Jiawei Han, Alice Leung, Chih-Chieh Hung and Wen-Chih Peng 2024/11/22
Outline Introduction Related Works Companion Discovery Framework The Buddy-based Approach Experiments and Conclusion DAIS UIUC 2 2024/11/22
Trajectory Data Streams Technical advances in mobile & tracking devices have lead to huge volume of trajectory data Trajectory stream: the devices report the object locations with timestamps in sequences Taxi traces by GPS Animal movements Military trajectories on battlefields Location based social network: check-in sequences DAIS UIUC 3 2024/11/22
Motivation It is interesting and useful to study the partnership in trajectory streams discover the group of objects that move together, i.e., traveling companions Applications: animal behavior analysis, migration path study traffic jam detection, smart driving direction recommendation anti-crime and anti-terrorist, battlefiled survilliance and control location based social network, online game play DAIS UIUC 4 2024/11/22
A Motivation Example o3 o5 o1 o5 o1 o2 o2 o1o2o3o4 o5 o4 o1 o8 o3 o4 o6 o2 o7 o3 o6 o7 o8 o5 o9 o4 o6 o7 o6 o7 o10 o8 o9 o10 o9 o8 o9o10 o10 s1 s2 s3 s4 size threshold = 4 & time threshold = 4 snapshots DAIS UIUC 5 2024/11/22
A Motivation Example o3 o5 o1 o5 o1 o2 o2 o1o2o3o4 o5 o4 o1 o8 o3 o4 o6 o2 o7 o3 o6 o7 o8 o5 o9 o4 o6 o7 o6 o7 o10 o8 o9 o10 o9 o8 o9o10 o10 s1 s2 s3 s4 size threshold = 4 & time threshold = 4 snapshots {o1, o2, o3, o4} is the traveling companion DAIS UIUC 6 2024/11/22
Problem Formulation Let sbe the size threhsold and tbe the duration threshold, a group of objects q is called traveling companion if: The members of q are desity connected by themselves for a period t where t t size(q) s Let trajectory stream S = {s1, s2, si, }, eash snapshot si= {(o1,x1,i,y1,i), (o2,x2,i,y2,i), , (on,xn,i,yn,i)}, the task is to discover the traveling companion set Q DAIS UIUC 7 2024/11/22
The Challenges Key issue: travel together in the same cluster; the cluster may be in arbitrary shape density-based clusters Efficiency discover the companions along the data streams (cannot scan the whole dataset) scalable with large number of objects and long time lasting trajectories Effectiveness report the large and long-lasting companions, rather than small and short-lasting ones DAIS UIUC 8 2024/11/22
Our Contributions Introduce the framwork to discover companions by clustering-and-intersection Improve the technique with smart-intersection and closed companions Propose the buddy-based approach to discover companions with higher efficiency Evaluate the performences on both real and synthetic datasets DAIS UIUC 9 2024/11/22
Outline Introduction Related Works Companion Discovery Framework The Buddy-based Approach Experiments and Conclusion DAIS UIUC 10 2024/11/22
Related Studies Moving group discovery, Kalnis et.al., 2005: two consecutive clusters with the similar contents Flock, Gudmundsson et.al., 2004: a group of objects that move together within a circle of user given ridus r , i.e., a disc Spatial tempo joins, Bakalov et.al., 2005: a pair of objects (only two) travel together TraCluster, Lee et.al., 2007: the clusters that represent the main moving direction of sub-trajectories DAIS UIUC 11 2024/11/22
Convoy Query and Swarm Query Convoy, Jeung et.al., 2008: a group of objects that traveled together continuously for a period of time Swarm, Li et.al., 2010: relaxed temporal moving object clusters Why don t they work on trajectory streams? Efficency: high time or I/O costs Effectiveness: the cluster must be in round shape, i.e, disc Generate results after scaning the entire dataset for static dataset, but not data streams DAIS UIUC 12 2024/11/22
Outline Introduction Related Works Companion Discovery Framework The Buddy-based Approach Experiments and Conclusion DAIS UIUC 13 2024/11/22
The Framework: Clustering-and-Intersection A two-step process to retrieve the traveling companions clustering the objects in each snapshot intersecting the clusters to generate companion candidates, if the candidates meet the size and time standards, output them as companion DAIS UIUC 14 2024/11/22
Example of CI: t=40m, s=4 o3 o5 o1 o5 o1 o1 o2 o6 o2 o1o2o3o4 o5 o4 o8 o7 o3 o4 o3 o8 o5 o6 o7 o10 o9 o6 o7 o6 o9 o7 o8 o10 o9 o8 o9o10 o10 s3 = 10m s2 = 10m s4 = 10m s1 = 10m r1 ={o1, o2, o3, o4}, 40 m r2 ={o1, o2, o3, o4, o5}, 30 m r3 ={o1, o2, o3, o4 , o5}, 20 m r1 ={o1, o2, o3, o4}, 10 m r2 ={o6, o7, o8, o9, o10}, 10 m r1 ={o1, o2, o3, o4}, 20 m r2 ={o6, o7, o8, o9, o10}, 20 m r4 ={o8, o9, o10}, 20 m r5 ={o1, o2, o3, o4, o5}, 10 m r6 ={o8, o9, o10}, 10 m r1 ={o1, o2, o3, o4}, 30 m r2 ={o8, o9, o10}, 30 m r3 ={o1, o2, o3, o4 , o5}, 20 m r3 ={o1, o2, o3, o4, o5, o6, o7, o8, o9, o10}, 10 m R's size: 9 Intersect: 0 R's size: 14 Intersect: 29 R's size: 23 Intersect: 11 R's size: 19 Intersect: 2 DAIS UIUC 15 2024/11/22
Analysis of Clustering-and-Intersection Pros: Guarantee not missing any companions Cons: high costs on both clustering and intersection steps In each snapshot, the intersection is carried out in every pair of candidate and cluster Some redundant and unnecessary candidates are stored DAIS UIUC 16 2024/11/22
The Smart Intersection and Closed Candidates Can we stop the intersection earlier? Smart Intersection: if the objects of a candidate has already been found in a cluster, no need to intersect the candidate furthermore with other clusters Can we only add the necessary ones? Closed candidate: for a new candidate ri, if there exists already another candidate rjthat , and duration(rj) duration (ri), then riis not necessary to add into the memory r r i j DAIS UIUC 17 2024/11/22
Example of Smart-Intersection and Closed Candidates o3 o5 o1 o5 o1 o1 o2 o6 o2 o1o2o3o4 o5 o4 o8 o7 o3 o4 o3 o8 o5 o6 o7 o10 o9 o6 o7 o6 o9 o7 o8 o10 o9 o8 o9o10 o10 s3 = 10m s2 = 10m s4 = 10m s1 = 10m Once found objects in c1, stop interesection; do not add the un-closed candidates we r1 s r1 ={o1, o2, o3, o4}, 30 m r2 ={o8, o9, o10}, 30 m r3 ={o1, o2, o3, o4 , o5}, 20 m r1 ={o1, o2, o3, o4}, 40 m r2 ={o1, o2, o3, o4 , o5}, 30 m r1 ={o1, o2, o3, o4}, 10 m r2 ={o6, o7, o8, o9, o10}, 10 m r1 ={o1, o2, o3, o4}, 20 m r2 ={o6, o7, o8, o9, o10}, 20 m the r3 ={o1, o2, o3, o4, o5, o6, o7, o8, o9, o10}, 10 m R's size: 9 Intersect: 0 R's size: 9 Intersect: 12 R's size: 15 (CI: 23) Intersect: 9 (CI: 11) R's size: 19 Intersect: 2 DAIS UIUC 18 2024/11/22
Outline Introduction Related Works Companion Discovery Framework The Buddy-based Approach Experiments and Conclusion DAIS UIUC 19 2024/11/22
The Bottleneck of Companion Discovery The clustering step: density-based clustering algorithm cost O(n2) time without spatial index It is costly to maintain a spatial index in each snapshot , since the object locations change a lot [Lee et.al., 2003] The clustering step is indeed the bottleneck DAIS UIUC 20 2024/11/22
The Buddy-based Approach Intuition: Speed up the clustering step by reusing the information of previous clusters Observation: People, animal and other creatures like to travel within small groups the buddies Couples/close friends like to travel together Animals migrate in families DAIS UIUC 21 2024/11/22
The Buddy Maintainence Although the buddies may not be larger enough as the companion, they can still be used to improve clustering efficiency The buddy only stores the relationships of objects The maintain cost of buddies is low: with buddy radius, size and center, easy to update the buddy s information when add/remove member objects DAIS UIUC 22 2024/11/22
The Buddy-based Clustering How can the buddies help clustering process? The principles (Lemma 2 to 4) If a buddy is tight (enough size with small radius), all the members of the buddy are density-connected If two buddies center distance is large, then the two of them cannot be directly density connected Lemma 4: If two tight buddies are close, then all their members are density-connected dist (cen(bi), cen(bj)) ri rj bi bj dist (bi, bj) bi bj dist (Oi, Oj) dist (Oi, Oj) (a) DAIS UIUC 23 (b) 2024/11/22
The buddy-based companion discovery The buddies can be used to help companion discovery Construct a buddy index {BID, ObjectSet, CanIDs} If a buddy stay unchanged, then the system only needs to check the buddy ID without looking object details in the intersection process reduce the intersection times DAIS UIUC 24 2024/11/22
Example: The Buddy-based Approach b1 b2 b1 b2 o1 o3 o5 o1 o2 o1o2o3o4 o5 o2 b1 o4 o1 o8 b1 b3 o6 o3 o4 b2 o3 o6 o7 o8 o6 o7 o9 o5 o10 b4 o6 o7 b3 b4 o8 o9 o9 o10 o8 o9o10 b4 o10 s2 = 10m s3 = 10m s4 = 10m s1 = 10m r1 ={b1, b2}, 10 m r2 ={b3, b4}, 10 m b1 ={o1, o2} b2 ={o3, o4} b3 ={o6, o7, o8} b4 ={o9, o10} r1 ={b1, b2}, 30m r2 ={o8, b4}, 30 m r3 ={b1, b2, o5}, 20 m b1 ={o1, o2} b2 ={o3, o4} b4 ={o9, o10} r1 ={b1, b2}, 40 m r1 ={b1, b2}, 20 m r2 ={b3, b4}, 20 m r3 ={b1, b2,b3, b4, o5}, 10 m b1 ={o1, o2} b2 ={o3, o4} b3 ={o6, o7, o8} b4 ={o9, o10} r2 ={b1, b2 , o5}, 30 m b1 ={o1, o2} b2 ={o3, o4} DAIS UIUC 25 2024/11/22
Outline Introduction Related Works Companion Discovery Framework The Buddy-based Approach Experiments and Conclusion DAIS UIUC 26 2024/11/22
Experiment Setup Four datasets: two real, two synthetic comparing the methods of smart-and-closed (SC), buddy-based (BU) with clutering-and-intersection (CI), trajectory clustering (TC) and swarm pattern (SW) DAIS UIUC 27 2024/11/22
Efficency Study I BU SC CI SW TC BU SC CI SW BU costs only 10- 20% time of CI SC costs 20-30% time of CI Larger t, less time 7 10000 1000000 10 Time (second) Candidate size (#) 6 1000 100000 10 5 100 10000 10 4 10 1000 10 3 1 100 10 D1 D2 D3 D4 D1 D2 D3 D4 (a) (b) BU SW SC TC CI BU SC CI SW 6 1000000 10 Time (second) Candidate size (#) 10000 5 100000 10 1000 4 100 10000 10 10 3 t t 1000 10 1 3 7 11 15 3 7 11 15 (a) (b) DAIS UIUC 28 2024/11/22
Efficency Study II Larger s, fewer companion candidagtes, less time If the average buddy size is larger than 2.5, BU outperforms density-based clustering BU SW Time (second) SC TC CI BU SC CI SW 6 1000000 10 Candidate size (#) 10000 5 100000 10 1000 4 10000 10 100 3 1000 10 10 2 s s 100 10 1 10 20 30 40 10 20 30 40 (a) (b) Total# Merge# Split# Same# B-Cluster DBSCAN BU 900 400 Buddy # Time (second) 300 600 200 300 100 0 0 1.26 2.22 4.31 9.17 1.26 2.22 4.31 9.17 |b| (a) |b| (b) DAIS UIUC 29 2024/11/22
Effectiveness Study CI s precision is low, too many non- closed companions TC(Trajectory clustering) may miss some companions BU SW Precision SC TC CI BU SW Recall SC TC CI 100% 100% 80% 80% 60% 60% 40% 40% 20% 20% s s 0% 0% 10 15 20 25 10 15 20 25 (b) (a) SC TC BU SW Precision CI BU SW Recall SC TC CI 100% 100% 80% 80% 60% 60% 40% 40% 20% 20% t t 0% 0% 3 7 11 15 3 7 11 15 (b) (a) DAIS UIUC 30 2024/11/22
Conclusion We have investigated the problem of companion discovery on streaming trajectories Cluster-and-Intersection framework is introduced as the baseline, the improvement of smart-intersection and closed-candidates are proposed The buddy-based companion algorithm is proposed for efficency companion discovery Thank You Very Much! Any Questions? DAIS UIUC 31 2024/11/22
