Popular MPR 1,a) 2,b) 2,c) GPS Most Popular Route( MPR) MPR MPR MPR MPR MPR MPR MPR Popular Popular MPR MPR Popular 1. GPS GPS GPS Google Maps *1 Zaiben [1] Most Popular Route( MPR) MPR MPR MPR 1 525 8577 1-1-1 2 525 8577 1-1-1 a) is004083@ed.ritsumei.ac.jp b) huang@fc.ritsumei.ac.jp c) kawagoe@is.ritsumei.ac.jp *1 https://maps.google.co.jp/ Zaiben MPR [2] MPR MPR GPS MPR MPR MPR Popular Popular MPR MPR Popular 2. MPR MPR 1 1 (a) (b) c 2013 Information Processing Society of Japan 1
1 1(a) MPR 1(b) MPR MPR MPR MPR MPR 2 1 MPR 13 14 MPR 13 13 MPR A 13 14 MPR B MPR 2 MPR MPR MPR MPR MPR GPS MPR MPR MPR 3. MPR MPR 2 MPR 2 (1) (4) Zaiben MPR 1 GPS 2 MPR 2 1 2 Transfer ProbabilityTP 3 TP Route PopularityRP 4 RP MPR MPR (1) (2 TP (1)-2 (1)-3 1)-2 1)-3 MPR 3.1 3.2 3.3 Popular 3.1 T 1 ( ) T t 1 t M M M K 2 ( ) T T.s T.e 1 T T.s T.e T.e T.s + 1 c 2013 Information Processing Society of Japan 2
T = m j=1 T j( T i T j = 0) 3.2 2 T a T b 2 T a T b T a.e + 1 = T b.s T ab T T T a T b T Algorithm1 Algorithm 1 Time Segments Combination INITIALIZATION: T set { T 1,..., T m } 1: [ITERATION] 2: for T a, T b T set ( T a T b ) do 3: if ((CHECK T ab ( T a, T b )) is true) then 4: T ab =COMBINE( T a, T b ) 5: T set T set T ab - T a - T b 6: end if 7: end for 8: [STOP CONDITION] 9: There exists no T ab where CHECK T ab ( T a, T b ) is true for any combination of a pair, T a, T b T set ( T a T b ) 2 T.s + i (0 i < M m ) w i std( T m ) min( T m ) T m std( T m ) std( T m ) = M m 1 i=0 (w i avg( T m )) 2 (1) avg( T m ) = M m 1 i=0 w i M m M m (2) min( T m ) min( T m ) = w k ( w i W, w k w i ) (3) W = (w 0,..., w M ) m MPR MPR MPR 2 MPR 2 2 6 [3] Most Most γ NumberMost 2 MPR 2 ( Most NumberMost MPR MPR Distribution Most NumberMost 2 MPR 2 MPR Distribution Distribution Most NumberMost Distribution 3 3 T 4 T 5 Most T ab ( β% ) std( T ab ) α 3 std Most T 45 NumberMost T ab ( β% ) std( T ab ) α γ 3 c 2013 Information Processing Society of Japan 3
3 1 T 4 T 5 N 1 0 1 N 2 2 2 N 3 5 5 N 4 1 1 N 5 1 0 NumberMost T 45 Distribution ϵ ( N 0,..., N p ) K most K most =1 2 Distribution 3 24 T T 1 T 8 8 3 L 1 L 2 L 3 ϵ 5 1 5 5 1 T 4 T 5 1 T 4 T 5 N 3 2 Algorithm2 Algorithm2 1 3.3 Popular MPR Popular Popular TP TP popular TP TP Popular MPR Algorithm 2 CHECK T ab ( T a, T b ) INITIALIZATION: Time Segment T a, T b ; Parameter α, β, γ, ϵ; OUTPUT: combineflag; 1: boolean combineflag; 2: T ab = COMBINE( T a, T b ) 3: [CONDITION Most] 4: if (Most(more than β) of the std( T ab )) α then 5: combineflag = true; 6: end if 7: [CONDITION NumberMost] 8: if (Most(more than β) of the std( T ab )) α and (the minimum number of trajectories of all edges) γ then 9: combineflag = true; 10: end if 11: [CONDITION Distribution] 12: if (trajectory amounts takes up same persentage in a Time Segment then 13: combineflag = true; 14: end if 15: RETURN combineflag; n i TP P r t (n i d) 1 t d 4 t P r t (n i d) = p j n i,d (4) j=1 R Popular p(r) 5 p(r) = i P r t (n j d) (5) j=1 4. 4.1 Truck [4] 700 9792 GPS 3 TP MPR MPR MPR Popular 2 1 T 24 t 1 t 24 24 3 1 3 AM0 c 2013 Information Processing Society of Japan 4
4 3 MPR Popular Popular 24 MPR 6 0.9187 T 12 MPR 10 0.8903 T 345 MPR 7 0.9293 T 78 MPR 6 0.9204 T 1 MPR 4 0.6472 T 2 MPR 4 0.6206 T 6 MPR 7 0.7382 T 7 MPR 6 0.8105 T 8 MPR 7 0.823 2 Most T 12 (0:00 5:59), T 345 (6:00 14:59), T 6, T 7, T 8 NumberMost T 1, T 2, T 345 (6:00 14:59), T 6, T 7, T 8 Distribution T 12 (0:00 5:59), T 345 (6:00 14:59), T 6, T 78 (18:00 23:59) AM2 59 T 1 AM3 AM5 59 T 2 AM6 AM8 59 T 3 AM9 AM11 59 T 4 PM12 PM14 59 T 5 PM15 00 PM17 59 T 6 PM18 PM20 59 T 7 PM21 00 PM23 59 T 8 8 24 α β γ ϵ 0 T 1, T 2,..., T 8 1 α 10.0 β 60.0 γ 20 ϵ 10 4.2 Transfer Network GPS 4 9792 GPS 819 4.3 3 2 Most NumberMost T 3 T 4 T 5 AM6 PM14 59 Most T 1 T 2 NumberMost 20 Distribution T 1 T 2 T 3 T 4 T 5 T 7 T 8 3 4.4 MPR MPR Popular MPR MPR Popular 5 Popular 3 5(a) (AM0 PM23 59 ) MPR MPR 6 Popular 0.9187 5(b) T 12 (AM0 AM5 59 ) MPR MPR 10 (a) MPR Popular (a) MPR T 12 (AM0 AM5 59 ) MPR MPR 5(c) T 345 (AM6 PM14 59 ) MPR AM6 PM14 59 MPR Popular (a) MPR T 345 (AM6 PM14 59 ) 5(c) MPR 5(d) T 78 (PM18 PM23 59 ) MPR 5(a) MPR Popular T 78 (PM18 PM23 59 ) MPR 3 ( T 12 T 345 T 78 ) ( T 1 T 2 T 6 T 7 T 8 ) Popular MPR MPR Popular MPR T 345 c 2013 Information Processing Society of Japan 5
4 6. 5 MPR T 78 MPR Popular MPR 3 T 345 T 78 Distribution 5. [5] [6] [7] Popular Route Zaiben Ling [8] 2 Uncertain Trajectory Popular Route GPS GPS Julia [9] GPS Kai-Ping [10] 2 MPR Hsun [11] MPR MPR Popular MPR MPR MPR Popular MPR MPR JSPS 24300039 [1] Zaiben Chen, Heng Tao Shen, Xiaofang Zhou. Discovering popular routes from trajectories. In ICDE 11, pp.900-911, 2011. [2] 22 / http://www.pref.kyoto.jp/douro/1317256048145.html (2010) [3],,. MPR. DEIM2013, 2013. [4] Trucks Data Set:http://www.rtreeportal.org/ [5] Chengxuan Liao, Jiaheng Lu, and Hong Chen. Synthesizing routes for low sampling trajectories with absorbing Markov chains. In WAIM 11, pp.614-626, 2011. [6] Yu Zheng, Lizhu Zhang, Xing Xie, Wei-Ying Ma. Mining interesting locations and travel sequences from gps trajectories. In WWW 09, pp.791-800, 2009. [7] Jing Yuan, Yu Zheng, Xing Xie, Guangzhong Sun. Driving with Knowledge from the Physical World. In KDD 11, pp.316-324,2011. [8] Ling-Yin Wei, Yu Zheng, Wen-Chih Peng. Constructing Popular Routes from Uncertain Trajectories. In KDD 12, pp.195-203, 2012. [9] Julia Letchner, John Krumm, Eric Horvitz. Trip Router with Individualized Preferences (TRIP): Incorporating Personalization into Route Planning. In IAAI 06, pp.1795-1800, 2006. [10] Kai-Ping Chang, Ling-Yin Wei, Mi-Yeh Yeh, Wen-Chih Peng. Discovering personalized routes from trajectories. In LBSN 11, pp.33-40,2011. [11] Hsun-Ping Hsieh, Cheng-Te Li, Shou-De Lin. Exploiting Large-Scale Check-in Data to Recommend Time- Sensitive Routes. In UrbComp 12, pp.55-62,2012. c 2013 Information Processing Society of Japan 6