PaperlayerView exact revision on arXiv

Source-linked AI summary

NLPMM: a Next Location Predictor with Markov Modeling

Meng Chen, Yang Liu, Xiaohui Yu

arXiv:2003.07037v1cs.AIcs.SI

TL;DR

Next-location prediction must account for individual and collective movement patterns, sparse trajectories, and movement that varies over time. NLPMM models these patterns and builds time-aware models; experiments report that it significantly outperforms VMM and WhereNext on a real vehicle-record dataset.

  • Problem

    Existing methods may focus on only individual or collective patterns, struggle to construct meaningful frequent patterns from sparse trajectories, and omit time-dependent movement variation.

    Source: §1 · p. 2

  • Method

    NLPMM models individual and collective movement patterns and uses time-period clustering to build a separate model for each cluster.

    Source: §1 · p. 2

  • Results

    NLPMM significantly outperforms the state-of-the-art methods VMM and WhereNext on a real vehicle passage-record dataset.

    Source: §7 · p. 12

  • Takeaways & Limitations

    The experiments support NLPMM's use as a next-location predictor for vehicle records, including settings with sparse trajectories and time-varying movement patterns.

    Source: §1 · p. 2

    Time Binning uses equal-sized bins, which can fit movement patterns poorly when those patterns span different durations.

    Source: §5.2 · p. 7

Abstract

from arXiv · show

In this paper, we solve the problem of predicting the next locations of the moving objects with a historical dataset of trajectories. We present a Next Location Predictor with Markov Modeling (NLPMM) which has the following advantages: (1) it considers both individual and collective movement patterns in making prediction, (2) it is effective even when the trajectory data is sparse, (3) it considers the time factor and builds models that are suited to different time periods. We have conducted extensive experiments in a real dataset, and the results demonstrate the superiority of NLPMM over existing methods.

1 Introduction

The introduction frames next-location prediction as useful for location-based applications, while identifying gaps in how prior methods handle movement patterns, sparse trajectories, and time. NLPMM combines movement-pattern modeling with time-aware models, and experiments on real vehicle records report superiority over existing methods.

1 Introduction

  • Next-location prediction is motivated by applications such as location-based advertising and traffic forecasting or route recommendations.The introduction gives examples involving information about areas someone may pass and predicting vehicle locations.Source: §1 · p. 1
  • Prior methods focus on either individual or collective patterns, may lack meaningful frequent patterns for sparse trajectories, and often omit time-dependent movement variation.The introduction notes that some trajectories may contain only one record.Source: §1 · p. 2
  • NLPMM clusters time periods by movement-pattern similarity and builds a separate model for each cluster, reflecting cyclical similarities across periods.The examples include similarities between Mondays and between weekdays and weekends.Source: §1 · p. 2
  • NLPMM significantly outperforms state-of-the-art methods VMM and WhereNext on a real vehicle passage-record dataset.The dataset covers 31 days in a metropolitan area.Source: §1 · p. 2
  • NLPMM combines individual and collective movement patterns to predict a moving object's next location, including when trajectory data is sparse.The paper describes it as a holistic approach to prediction.Source: §1 · p. 2

2 Related Work

Related work spans route planning, long-range trajectory prediction, short-range next-location prediction, and trajectory mining from social-media data. The short-range approaches include methods based on individual movements and methods using movement histories across objects.

Route planning

  • Route-planning studies construct routes from GPS trajectories, including popular routes, k Best-Connected Trajectories, and fastest routes at a given departure time.The cited examples are.Source: §2 · p. 3

Long-range prediction

  • Long-range prediction studies forecast whole future trajectories or routes using prior GPS traces or traversed road segments.Source: §2 · p. 3

Short-range prediction

  • Short-range prediction targets the next location, using individual movement histories or histories from all moving objects.Examples include a per-road Probabilistic Suffix Tree, a hybrid model, a T-pattern tree, and frequent-trajectory mining.Source: §2 · p. 3

Social-media data

  • Social-media trajectory studies include route recommendation, pattern ranking and diversification, and predicting activity category before location.Source: §2 · p. 3

3 Preliminaries

The preliminaries define the trajectory and location terms used to specify next-location prediction. They also define directly reachable candidate locations and a prefix set of preceding location sequences.

Definitions

  • A sampling location is a point or region where an object's position is recorded, and a trajectory unit pairs a location identifier with a timestamp.Traffic-surveillance camera positions are an example of sampling locations.Source: §3 · p. 4
  • A trajectory is a time-ordered sequence of trajectory units, equivalently represented as location-and-timestamp pairs.Its sampling location sequence retains the ordered locations without timestamps.Source: §3 · p. 4
  • A candidate next location is directly reachable from the current sampling location; candidates can come from prior knowledge or historical trajectories.Source: §3 · p. 4
  • A prefix set of size N contains length-N sequences that immediately precede a specified location in trajectories' sampling-location sequences.Source: §3 · p. 4

4 Markov Modeling

NLPMM uses Markov models over sampling locations to combine collective and individual movement patterns. A Global Markov Model captures shared patterns, a Personal Markov Model addresses individual patterns and sparse data, and linear regression integrates their predictions.

4 Markov Modeling

  • Markov states represent sampling locations and transitions represent movement between locations; NLPMM combines global collective and personal individual models in its predictor.The GMM assumes objects often share similar movement patterns.Source: §4 · p. 4, §4.1 · p. 5

4.1 Global Markov Model

  • An order-N GMM predicts the next sampling location from the immediately preceding N locations, while variable-order modeling uses the longest matching suffix.It estimates next-location probabilities from observed frequencies following matching prefixes.Source: §4.1 · p. 5

4.2 Personal Markov Model

  • The PMM models each object's individual patterns and addresses sparse trajectories through variable-order models from longer trajectories and zero-order models from trajectory units.The paper reports that about 73% of its dataset's trajectories contain only one point.Source: §4.2 · pp. 5–6

4.3 Integration of GMM and PMM

  • Linear regression combines GMM and PMM probability vectors, with coefficients learned from training trajectories to predict the top k next locations.The predictor selects the k largest elements of its estimator.Source: §4.3 · p. 6

5 Time Factor

Movement patterns vary across time periods, so the paper explores time-aware models and ways to choose suitable periods. It contrasts equal-sized time bins with clustering bins that have similar transition distributions.

5.1 Observations and Discussions

  • The most probable next location changes by time period: vehicles favor the fifth location from 9:00 to 10:00 and the second from 14:00 to 15:00.Source: §5.1 · p. 6

5.2 Time Binning

  • Time Binning (TB) splits trajectories across M equal-sized time bins, trains an independent model per bin, and selects a model by timestamp.Source: §5.2 · p. 7
  • Equal-sized bins can fit movement patterns poorly because some patterns persist longer than others, and similar distributions can recur in nonadjacent periods.For example, the 11:00–12:00 distribution differs from 10:00–11:00 but resembles 14:00–15:00.Source: §5.2 · p. 7

5.3 Distributions Clustering

  • Distributions Clustering (DC) groups time bins by transition-probability similarity, using cosine similarity, then trains Q models on the resulting clusters.The clustering assigns bins to the most similar cluster center and recalculates centers until clusters stop changing or the iteration limit is reached.Source: §5.3 · pp. 7–8
  • NLPMM-DC combines distributions clustering with an order-N Markov model, using both just-passed locations and the time factor for prediction.Source: §5.3 · p. 8

6 Performance evaluation

Experiments evaluate NLPMM on real vehicle-passage trajectories, testing its components, time-aware variants, and comparison with existing methods.

6.1 Datasets and Settings

  • The dataset contains 10,344,058 vehicle-passage records collected over 31 days, from about 300 camera locations averaging approximately 3 kilometers apart.Source: §6.1 · pp. 8–9

6.2 Pre-processing

  • About 73% of 6,521,841 trajectories contain one point; 1,760,897 longer trajectories are used to count candidate next locations.Source: §6.2 · p. 9

6.3 Evaluation Metrics

  • Evaluation uses prediction coverage, accuracy, one-error, and average precision to measure coverage, correct-list inclusion, top-1 error, and ranked-list quality.Source: §6.3 · p. 9

6.4 Evaluation of NLPMM

  • Across 50 runs, averaged results show accuracy improves from Markov order N=1 to N=2 for all models and reaches its maximum at N=3.Source: §6.4 · p. 9
  • At k=10, accuracy is 0.88 despite an average of 43 candidate next locations; NLPMM gives the best results, while GMM and NLPMM outperform PMM.Source: Figure 2 · p. 10, §6.4 · p. 10

6.5 Effect of the Time Factor

  • NLPMM-TB performance deteriorates below bin size 8; for NLPMM-DC, one-error and average precision improve through five clusters, then worsen.The reported explanation is that too many or too few clusters hurt cluster cohesiveness or separation.Source: §6.5 · pp. 10–11
  • NLPMM-TB and NLPMM-DC outperform NLPMM on one-error and average precision, with NLPMM-DC performing best.Source: Table 1 · p. 11, §6.5 · p. 11

6.6 Comparison with existing methods

  • NLPMM-DC performs best in prediction coverage and exceeds VMM and WhereNext in accuracy at every training-set size.The comparison evaluates coverage and accuracy.Source: Figure 4 · p. 11, §6.6 · pp. 11–12

7 Conclusions

The paper proposes NLPMM, combining global and personal Markov models with time-aware variants, and reports that it significantly outperforms VMM and WhereNext on real vehicle-passage records.

7 Conclusions

  • NLPMM combines a Global Markov Model and a Personal Markov Model to predict a moving object's next sampling location from its trajectory sequence.Source: §7 · p. 12
  • Time Binning and Distributions Clustering partition the time span into finer periods for training time-aware models.Source: §7 · p. 12
  • Experiments on real vehicle-passage records show NLPMM significantly outperforming VMM and WhereNext.Source: §7 · p. 12
Loading 2003.07037v1…