资源描述
Discovering Popular Routes from Trajectories,从轨迹中发现热门路线,分享人：J-JaSon,Conference,ICDE 2011,International Conference on Data Engineering,School & Author,School & Author,The aim,Discovering the Most Popular Route between two locations by observing behaviors of many previous users.,通过观察之前用户的行为，找出两地之间最热门的路线,Why do this,How do this,How do this,Three steps:,How do this,Three steps:,How do this,Three steps:,Related Work,Step 1,Mining Transfer Network,Mining Transfer Network,Notice that if there is a road map available, we can find out the transfer network by map-matching trajectories.,Mining Transfer Network,Detect the intersections of trajectories,Intersections of trajectories,Within an intersection region, the density of trajectory points is normally higher, in comparison with the density of points on an incoming/outgoing road edge, because it is the place where trajectories join together or drivers slow down to make a turn. If we consider an intersection as a group of points, then the size of the group should be greater than some threshold.,Intersections of trajectories,A number of trajectories change moving direction at an intersection, as some people make turns. The moving directions of trajectory points from/to different road edges are likely to be orthogonal (i.e., angle of difference tends to /2). Within a small distance, points whose moving directions differ by 0 or (i.e., in the same or opposite direction) are probably on the same road, while points with direction difference0 and are possibly moving to different road branches of an intersection. The closer the angle of difference tends to /2, the higher possibility that an intersection exists.,Intersections of trajectories,density,密度条件,direction,方向条件,Definition 1,Definition 1：Coherence,(, ) is the Euclidean distance between and , is the angle of difference between and s moving directions,Definition 2,3,Definition 2：Directly Coherence-Connected,Definition 3：Coherence-Connected,If there is a chain of points,and,Obviously, CoherenceConnected is a symmetric and transitive relation.,Algorithm,Density,Coherence,Algorithm,Algorithm,Practice,In practice, as GPS data is more or less dirty, we first reduce outlier points that suddenly jump away by considering physical limits on vehicle speed, before running the clustering algorithm. Besides, linear interpolation is conducted for low sampling-rate trajectories to reduce the possibility that they are missed at some intersections that they do pass through. Direction smoothing is also carried out to alleviate the effect of position fluctuation caused by GPS inaccuracy.,Mining Transfer Network,After discovering all the clusters (intersections), we treat each of them as a transfer node whose location is approximated by the average coordinate, while transfer edges are constructed by checking trajectories between nodes.,Step 2,Deriving Transfer Probability,The aim：,Deriving Transfer Probability,Where (, ) is the shortest Euclidean/network distance between and the front part of that starts from .,Random Walk,If we conduct such a random walk, what is the exact probability that, starting from a node , we will eventually reach the destination within steps?,用t步从ni走到nj的概率,在t步之内步从ni走到nj的概率,Choose parameter c,Set as the diameter of the transfer network in our experiments, which guarantees at least one route can be found between any two nodes and also avoids considering those excessively long routes.,AMCM,Absorbing Markov Chain Model:,A state (node) of a Markov chain is called absorbing if its impossible to leave it.,AMCM,AMCM,Assume there are totally absorbing states, and transient states (+=). We group absorbing states into ABS and transient states into TR.,Transfer matrix：,How to calculate,Example：,P =, 2 = ?, 2 13 = ?,1/3+1/4 = 7/12,Why do this,Lemma 3:,Why do this,在t步之内步从ni走到d的概率,用t步从ni走到d的概率,Why do this,Expressed in matrix form:,How to calculate 1,How to calculate 2,D =,=,S,D,y-by-x,x-by-1,y-by-1,How to calculate 3,D =,=,Q,QD,y-by-y,y-by-1,y-by-1,D,Step 3,Searching The MPR,热门程度的另一表达形式:,路线热门程度定义:,Algorithm,Algorithm,(),Why,However, a problem with this alternative option is that the search algorithm just considers the local information of the current node other than steps further, which possibly causes an incorrect result.,author,Experiments,Contributions,We present a new route planning approach that gives another option for users other than existing shortest path based methods.,We develop an algorithm to establish the transfer network model of a collection of historical trajectories, and utilize the Absorbing Markov Chain model to derive the transfer probability for transfer nodes.,We propose a reasonable popularity function as well as the search algorithm for discovering the most popular route over a transfer network.,Thank you!,
展开阅读全文