DiscoveringPopularRoutesfromTrajectories从轨迹中发现热门路线分享人：J-JaSonConferenceICDE2011InternationalConferenceonDataEngineeringSchool&Author2014/15QS43School&AuthorZaibenChenHengTaoShenXiaofangZhouTheaimDiscoveringtheMostPopularRoutebetweentwolocationsbyobservingbehaviorsofmanyprevioususers.通过观察之前用户的行为，找出两地之间最热门的路线WhydothisIsusefulespeciallyforuserswhoaretravelingtounfamiliarareas.对在陌生区域驾驶的人很有帮助。Theshortestorthefastestmaynotbethebest.最短的和最快的不一定是最好的。HowdothisHowdothisThreesteps:1DevelopaCoherenceExpandingalgorithmtoretrieveatransfernetworkfromrawtrajectories提出CoherenceExpandingalgorithm用于从未预处理的轨迹中得到transfernetworkHowdothisThreesteps:2TheAbsorbingMarkovChainmodelisappliedtoderiveareasonabletransferprobabilityforeachtransfernode用AbsorbingMarkovChainmodel推导出每个转换点的transferprobabilityHowdothisThreesteps:3ProposeaMaximumProbabilityProductalgorithmtodiscovertheMPRfromatransfernetwork使用MaximumProbabilityProduct从转换网络中得到MPR(最热门路径)RelatedWorkStep1MiningTransferNetworkIsasetoftransfernodes,whichcanbeanintersectionoftrajectoriesorjusttheendlocationsofatrajectory.N是交换点的集合，交换点可以是轨迹的交叉点也可以是轨迹的终点。Isacollectionoftransferedgesconnectingtransfernodes.E是一系列连接交换点的交换边。MiningTransferNetworkNoticethatifthereisaroadmapavailable,wecanfindoutthetransfernetworkbymap-matchingtrajectories.Tracesofhiking,boating,很多地图上walking,andmanyout-door的路线或有法律activities或者技术上的限制arenotconstrainedbya爬r山o，ad划n船e，tw步o行rk等.mostmapsthatpeoplethinkofasfree户外运动的不会被havelegalortechnical路网所限制restrictionsontheiruse.MiningTransferNetworkDetecttheintersectionsoftrajectoriesIntersectionsoftrajectoriesWithinanintersectionregion,thedensityoftrajectorypointsisnormallyhigher,incomparisonwiththedensityofpointsonanincoming/outgoingroadedge,becauseitistheplacewheretrajectoriesjointogetherordriversslowdowntomakeaturn.Ifweconsideranintersectionasagroupofpoints,thenthesizeofthegroupshouldbegreaterthansomethreshold.IntersectionsoftrajectoriesAnumberoftrajectorieschangemovingdirectionatanintersection,assomepeoplemaketurns.Themovingdirectionsoftrajectorypointsfrom/todifferentroadedgesarelikelytobeorthogonal(i.e.,angleofdifferencetendsto𝜋/2).Withinasmalldistance,pointswhosemovingdirectionsdifferby0or𝜋(i.e.,inthesameoroppositedirection)areprobablyonthesameroad,whilepointswithdirectiondifference>0and<𝜋arepossiblymovingtodifferentroadbranchesofanintersection.Theclosertheangleofdifferencetendsto𝜋/2,thehigherpossibilitythatanintersectionexists.Intersectionsoftrajectoriesdensitydirection密度条件方向条件Definition1Definition1：Coherence𝑑𝑖𝑠𝑡(𝑝,𝑞)istheEuclideandistancebetween𝑝and𝑞𝛿isascalingfactor𝜃istheangleofdifferencebetween𝑝and𝑞’smovingdirections𝛼and𝛽aretuningparametersDefinition2,3Definition2：DirectlyCoherence-ConnectedifthenDefinition3：Coherence-ConnectedIfthereisachainofpointsandthenObviously,CoherenceConnectedisasymmetricandtransitiverelation.andAlgorithmDensityDBSCANCoherenceAlgorithmAlgorithmPracticeInpractice,asGPSdataismoreorlessdirty,wefirstreduceoutlierpointsthatsuddenlyjumpawaybyconsideringphysicallimitsonvehiclespeed,beforerunningtheclusteringalgorithm.Besides,linearinterpolationisconductedforlowsampling-ratetrajectoriestoreducetheposs...
