Learning Points and Routes to Recommend Trajectories

1 Introduction

• POI recommendation scores locations using geographic, behavioral, spatial, and temporal information, whereas next-location recommendation scores candidates given a partial trajectory.The latter incorporates compatibility with the locations already visited.Source: §1 · p. 1
• Trajectory recommendation specifies a start and end point and may include a desired trip length, while evaluating routes by both POI desirability and transition compatibility.The paper identifies a need to jointly learn POI ranking and route planning and to unify the treatment of features such as location, time, distance, user profiles, and social interactions.Source: §1 · p. 1
• The proposed approach jointly optimizes point preferences and routes, learns from past behavior using features, and reports better performance than recent methods.The contributions also include using transition information to improve POI sequences and avoiding sub-tours to improve classical Markov-chain methods.Source: §1 · p. 2
• Pairs-F1 evaluates whether POI pairs appear in the recommended visiting order, reaching 1 if and only if the recommended trajectory matches the ground truth exactly.Figure 1 encodes POI scores by node size, transition scores by edge width, observed locations in grey, and start and end locations with a star and flag.Source: Figure 1 · p. 1, §1 · p. 2

2 POI, Query and Transition

• A tour is a sequence of L POIs that maximizes user utility, given a specified start, end, and length, and training tours from the city.The graph contains previously visited POIs as nodes and observed directed transitions between them as edges.Source: §2 · p. 2
• POI ranking features include category, popularity, visits, duration, neighbourhood, and distance, contrasted with the query's start and end points.The query also includes the required tour length; category and neighbourhood comparisons use matching indicators, while popularity, visits, and duration use real-valued differences.Source: §2 · p. 2
• Feature-factorized Markov transitions address the difficulty of estimating direct POI-to-POI probabilities for unseen, unobserved, or rarely visited transitions.Feature-wise transition probabilities are estimated by maximum likelihood, combined with Kronecker products, then adjusted to remove self-loops, distribute probability among POIs with identical features, and exclude feature combinations absent from the dataset.Source: §2 · p. 2
• Popularity, visit counts, and average duration are discretized into five uniform log-scale bins before feature-wise transition estimation.Figure 2 visualizes Melbourne transition matrices for the category and neighbourhood features.Source: §2 · p. 2, Figure 2 · p. 2

3.1 POI Ranking and Route Planning

• PoiPopularity uses the same top-k popular POIs for all visitors, adjusting k to tour length; PoiRank learns rankings from query-grouped visit counts and connects the top L−2 POIs.PoiRank uses rankSVM with POI features, and its training labels exclude occurrences where a POI is the trajectory origin or destination.Source: §3.1 · pp. 2–3

3.2 Combine Ranking and Transition

• Rank+Markov combines POI-ranking probabilities and transition probabilities with a tunable α weight, then uses Viterbi to find the best path.The ranking score is transformed with softmax; α can be tuned using cross-validation.Source: §3.2 · p. 3

3.3 Avoiding sub-tours

• Viterbi paths can contain circular sub-tours, so an ILP imposes a single POI sequence, at most one visit per POI, and exactly L visits.MarkovPath uses the transition matrix; Rank+MarkovPath applies the same sub-tour constraints while optimizing the combined ranking-and-transition score.Source: §3.3 · pp. 3–4

4 Experiment on Flickr Photos

• Evaluation uses leave-one-out cross-validation on Flickr-photo trajectories from Edinburgh, Glasgow, Melbourne, Osaka, and Toronto.Baselines include Random, popularity-based recommendations, POI-ranking methods, Markov transition methods, and variants with sub-tour constraints.Source: §4 · p. 4

4.1 Performance metrics

• Pairs-F1 scores ordered POI pairs, capturing both POI identity and visit order, unlike point-level F1.The cited examples have perfect point F1 but not perfect pairs-F1 because their recommended sequences differ from the ground truth.Source: §4.1 · p. 4, Figure 3 · p. 4

4.2 Results

• Across five datasets, problem-informed methods outperform Random on both metrics, and ranking variants outperform their transition-only counterparts.The comparison reports F1 and pairs-F1; the supplied table passages identify the metrics and dataset scope, but not cell values.Source: §4.2 · p. 4, Table 3 · p. 5, Table 4 · p. 5
• Sub-tour elimination improves F1, while most Markov-chain entries perform better on pairs-F1, indicating stronger transition-pattern agreement.The authors attribute the F1 gain to removing repeated-POI sub-tours under a length constraint.Source: §4.2 · p. 4, Table 3 · p. 5, Table 4 · p. 5
• PersTour outperforms PersTour-L on both metrics, but Melbourne results are inconsistent after ILP failures and time-limited suboptimal solutions.Twelve percent of Melbourne evaluations failed to find a feasible solution within two hours.Source: §4.2 · pp. 4–5

4.3 An Illustrative Example

• In the Edinburgh example, Rank+MarkovPath reproduces the ground-truth POIs and routes exactly, unlike the other illustrated recommendations.PoiRank selected the right POIs but different routes; Markov matched one intermediate route but missed a POI.Source: §4.3 · p. 5

5 Discussion and Conclusion

• The approach jointly optimizes POI preferences and routes, learning POI ranks from query features and transitions from previous trajectories.It investigates maximum-likelihood sequence recommendation and proposes an improved sequence method.Source: §5 · p. 5
• The paper proposes pairs-F1 to measure performance with respect to POI visiting order.The paper argues that evaluation should account for the order in which POIs are visited.Source: §5 · p. 5
• The approach improves on prior work in both traditional F1 and pairs-F1 across five Flickr-derived datasets.The paper concludes that trajectory recommendation should consider point and route information together.Source: §5 · p. 5

A POI Features for Ranking

• PoiRank uses POI- and query-specific features, scaled linearly so each feature’s observed minimum and maximum map to −1.0 and 1.0.Table 5 identifies the features used by rankSVM for a POI and query.Source: A POI Features for Ranking · p. 7, Table 5 · p. 7
• The figures show POI categories across five datasets and distributions of popularity, visit counts, and average visit duration.Figure 6 presents the distributions; Figure 5 presents the categories.Source: A POI Features for Ranking · p. 7, Figure 5 · p. 7, Figure 6 · p. 8

B Transition Probabilities

• POI-to-POI transition probabilities are factorized as products of transition probabilities between individual POI features.Table 6 lists the POI features used in the factorization.Source: B Transition Probabilities · p. 7, Table 6 · p. 7
• Feature transition matrices are estimated by maximum likelihood from counted transitions, with ϵ = 1 added before row normalization; their Kronecker product forms the POI transition matrix.Figure 7 visualizes the feature transition matrices for Melbourne.Source: B Transition Probabilities · p. 7, Figure 7 · p. 8
• The matrix sets self-transition probabilities to zero and distributes probability uniformly among POIs with identical discretized features.For identical-feature groups, the self-loop group probability is split among the other POIs, excluding the POI itself.Source: B Transition Probabilities · p. 8
• Feature combinations with no POIs are removed, and each remaining matrix row is normalized into a probability distribution.Source: B Transition Probabilities · p. 8

C.1 Dataset

• Flickr photos are mapped to Wikipedia POIs by Haversine distance, and first and last photo times approximate arrival and departure before temporally ordered visits are segmented into trajectories.Consecutive visits are split according to the time gap between them.Source: §C.1 · p. 9

C.2 Parameters

• PersTour and PersTour-L use a 0.5 trade-off parameter, rankSVM uses C = 10.0, and α for Rank+Markov variants is tuned by cross-validation.Trajectories with more than two POIs are split into roughly equal validation and test parts, with the tuning and testing parts reversed in a second run.Source: §C.2 · p. 9

• rankSVM from libsvmtools is used for ranking, while Gurobi Optimizer and lp_solve solve integer linear programs.Source: §C.3 · p. 9
• The dataset and code for the work are available in a repository.Source: §C.3 · p. 9
• The implementation identifies the software packages used for its ranking and optimization components.Source: §C.3 · p. 9

C.4 Performance metric

• Point-level F1 is the harmonic mean of precision and recall over visited POIs, but it ignores their visiting order.A score of 1 means the recommended and ground-truth trajectories contain exactly the same POI set; 0 means none of the ground-truth POIs was recommended.Source: §C.4 · p. 9
• Pairs-F1 measures both POI identity and visiting order by evaluating every pair of POIs, whether or not the pair is adjacent in the trajectory.A pair matches when its POIs appear in the same relative order in both trajectories.Source: §C.4 · p. 9
• Pairs-F1 ranges from 0 to 1; a score of 1 requires the same POIs in the same order, and it is set to 0 when no recommended POI pair matches.The number of matching pairs, Nc, counts pairs appearing in both trajectories with the same relative order.Source: §C.4 · p. 9