从轨迹中发现热门路线——扁平简洁风论文答辩ppt模板

DiscoveringPopularRoutesfromTrajectories 从轨迹中发现热门路线 分享人 J JaSon Conference ICDE2011 InternationalConferenceonDataEngineering School Author School Author Theaim DiscoveringtheMostPopularRoutebetweentwolocationsbyobservingbehaviorsofmanyprevioususers 通过观察之前用户的行为 找出两地之间最热门的路线 Whydothis Howdothis Howdothis Threesteps Howdothis Threesteps Howdothis Threesteps RelatedWork Step1 MiningTransferNetwork MiningTransferNetwork Noticethatifthereisaroadmapavailable wecanfindoutthetransfernetworkbymap matchingtrajectories MiningTransferNetwork Detecttheintersectionsoftrajectories Intersectionsoftrajectories Withinanintersectionregion thedensityoftrajectorypointsisnormallyhigher incomparisonwiththedensityofpointsonanincoming outgoingroadedge becauseitistheplacewheretrajectoriesjointogetherordriversslowdowntomakeaturn Ifweconsideranintersectionasagroupofpoints thenthesizeofthegroupshouldbegreaterthansomethreshold Intersectionsoftrajectories Anumberoftrajectorieschangemovingdirectionatanintersection assomepeoplemaketurns Themovingdirectionsoftrajectorypointsfrom todifferentroadedgesarelikelytobeorthogonal i e angleofdifferencetendsto 2 Withinasmalldistance pointswhosemovingdirectionsdifferby0or i e inthesameoroppositedirection areprobablyonthesameroad whilepointswithdirectiondifference 0and arepossiblymovingtodifferentroadbranchesofanintersection Theclosertheangleofdifferencetendsto 2 thehigherpossibilitythatanintersectionexists Intersectionsoftrajectories density 密度条件 direction 方向条件 Definition1 Definition1 Coherence istheEuclideandistancebetween and istheangleofdifferencebetween and smovingdirections Definition2 3 Definition2 DirectlyCoherence Connected Definition3 Coherence Connected Ifthereisachainofpoints and Obviously CoherenceConnectedisasymmetricandtransitiverelation Algorithm Density Coherence Algorithm Algorithm Practice Inpractice asGPSdataismoreorlessdirty wefirstreduceoutlierpointsthatsuddenlyjumpawaybyconsideringphysicallimitsonvehiclespeed beforerunningtheclusteringalgorithm Besides linearinterpolationisconductedforlowsampling ratetrajectoriestoreducethepossibilitythattheyaremissedatsomeintersectionsthattheydopassthrough DirectionsmoothingisalsocarriedouttoalleviatetheeffectofpositionfluctuationcausedbyGPSinaccuracy MiningTransferNetwork Afterdiscoveringalltheclusters intersections wetreateachofthemasatransfernodewhoselocationisapproximatedbytheaveragecoordinate whiletransferedgesareconstructedbycheckingtrajectoriesbetweennodes Step2 DerivingTransferProbability Theaim DerivingTransferProbability Where istheshortestEuclidean networkdistancebetween andthefrontpartof thatstartsfrom RandomWalk Ifweconductsucharandomwalk whatistheexactprobabilitythat startingfromanode wewilleventuallyreachthedestination within steps 用t步从ni走到nj的概率 在t步之内步从ni走到nj的概率 Chooseparameterc Set asthediameterofthetransfernetworkinourexperiments whichguaranteesatleastoneroutecanbefoundbetweenanytwonodesandalsoavoidsconsideringthoseexcessivelylongroutes AMCM AbsorbingMarkovChainModel Astate node ofaMarkovchainiscalledabsorbingifit simpossibletoleaveit AMCM AMCM Assumetherearetotally absorbingstates and transientstates WegroupabsorbingstatesintoABSandtransientstatesintoTR Transfermatrix Howtocalculate Example P 2 2 1 3 1 3 1 4 7 12 Whydothis Lemma3 Whydothis 在t步之内步从ni走到d的概率 用t步从ni走到d的概率 Whydothis Expressedinmatrixform Howtocalculate1 Howtocalculate2 D S D y by x x by 1 y by 1 Howtocalculate3 D Q Q D y by y y by 1 y by 1 D Step3 SearchingTheMPR 热门程度的另一表达形式 路线热门程度定义 Algorithm Algorithm Why However aproblemwiththisalternativeoptionisthatthesearchalgorithmjustconsidersthelocalinformationofthecurrentnodeotherthan stepsfurther whichpossiblycausesanincorrectresult author Experiments Contributions Wepresentanewrouteplanningapproachthatgivesanotheroptionforusersotherthanexistingshortestpathbasedmethods Wedevelopanalgorithmtoestablishthetransfernetworkmodelofacollectionofhistoricaltrajectories andutilizetheAb