Measuring and Recommending Time-Sensitive Routes from Location-based Data

1 Introduction

Location-based Services (LBS), such as Foursquare and Gowalla, allow users to perform the action of location recording that pins the geographical information of current locations and time stamps onto their personal pages. By continuously recording such actions by users, a location sequences dataset can be generated. The rapid accumulation of location sequence data can not only collectively represent the real-world human activities, but also serve as a handy resource for constructing location-based recommendation systems. Since the user-moving records implicitly reveal how people travel around in an area with rich spatial and

This paper is an extended abstract of the ACM Transactions on Intelligent Systems and Technology (ACM TIST) publication [Hsieh et al., 2014]

temporal information, including longitude, latitude, and recording timestamp, one reasonable application leveraging such user-generated location sequence data is to construct and recommend travel routes. Indeed, many of existing works had recommended routes using GPS trajectories (e.g. [Wei et al., 2012;Yoon et al., 2011;Yuan et al., 2011]). Furthermore, using geo-tagged photos and check-in data can reveal how people sequentially visit places in an area. Using geo-tagged photos, Y. Arase et al. [Arase et al., 2010] mine frequent route patterns for recommendation. A.-J. Cheng et al. [Cheng et al., 2011] propose personalized travel recommendation using geo-tagged photos. X. Lu et al. [Lu et al., 2011] construct routes based on user preference querying locations. Zheng et al. [Zheng et al., 2013] present the activity trajectory similarity search which returns k check-in trajectories that cover the activity labels. Lu et al. [Lu et al., 2012] develop a personalized trip recommendation that scores attractions by social links and temporal properties. L.-Y. Wei et al. [Wei et al., 2012] infer the top-k detailed routes traveling a given location sequence within a specified travel time. Different from these works, we aim to perform knowledge discovery to construct the time-sensitive routes.

In this paper, instead of relying on past trajectories to recommend trip routes, we propose a novel time-sensitive route recommender system, TimeRouter, using location check-in data. We argue that a good route should consider four factors. (a) The popularity of a place: popular landmarks will likely attract more visitors. (b) The proper time to visit a place: the pleasure of visiting a place can be significantly diminished if arriving at the wrong time. Some places have a wider range of preferred visiting time while others are constrained to certain particular time slots. For example, most people do not want to visit a beach during boiling hot noon, but rather arrive in the late afternoon to enjoy the sunset scene. Sports game events usually take place at particular time period. (c) The amount of time transiting from one place to another: for example, if one has bought tickets to a football game at a stadium 2 hours away, then he or she shall logically choose to start traveling toward the stadium 2 hours ahead of the official kick off time instead of going to a nearby museum 30 minutes away then. (d) The visiting order of places: for example, going to the gym first then going to restaurant for dinner might be a better plan than the other way around since it is not healthy to exercise right after a meal.

In this work, we utilize check-in data to acquire the time-stamped geographical information. Check-in data provides explicit or implicit information that allows us to fulfill the abovementioned requirements for the sake of planning a proper trip route. First, we can distill from the check-in data the number of people who have visited a certain place, and thus derive the popularity of places. Second, users in LBS tend to perform check-in actions to keep track of their trips. As a result, we can obtain and consider the visiting order of places. Third, the check-in records contain the visiting time stamps of locations. Users in LBS are able to collectively reveal the proper visiting time of places. Fourth, followed by the check-in time stamps from existing routes, we are able to hypothesize the transit time between places. Equipped with such elements, we utilize the check-in data to recommend and construct trip routes.

Formally, the goal of this work is to recommend time-sensitive routes using time-stamped location sequence data according to user requirements. We propose to tackle two real-world demands of recommending time-sensitive routes. The first is to construct a time-sensitive route given a source location, and the second is to create a time-sensitive route given the source-destination pair of locations. Both queries consider the starting time of the trip. Given a source or source-destination query, our system will return a sequence of recommended places as the final route, in which each location can be visited at a proper time with a reasonable transit time from one place to another in the route. In addition, in the query, we also allow users to determine the extent of time-sensitivity of locations through specifying a time-sensitivity parameter. Time-sensitive routes are supposed to be more effective than a simple route without time stamp as it allows the users to better manage their time during the trip. Both queries are very common for real-world trip planning.

In this work, a statistical-based approach is proposed to model the time-sensitivity of location, and a novel search algorithm to recommend time-sensitive routes with respect to the queries. In general, our work consists of two important issues. First, we aim to design a goodness function, which integrates the abovementioned four requirements about a good trip route to measure the quality of a route. Second, given a query, we devise an effective and efficient search method, Guidance Search, to identify the places to be visited by optimizing the route goodness function.

2 Methodology

Notations. A location li is a tuple, li = (xi,yi), where xi is the longitude, yi is the latitude. A route is a sequence of locations with the corresponding time stamps, denoted by s=<(l1,t1),(l2,t2),..., (ln,tn)>, where n is the number of locations. The source query Qs=(ls,ts) contains a starting location ls with time stamp ts, and the source-destination query Qd=(ls,ts,ld) further contains a destination location ld, where k is the number of locations in the final route (either specified by users or determined automatically). A time-sensitive route is sr = <(l1,t1),...,(lk,tk)>, where l1 = lq, t1 = tq, and/or lk=ld.

Time-sensitive Route Construction problem. Given (a) routes derived from location check-in data, and (b) either the source query Qs=(ls,ts) or the source-destination query Qd=(ls,ts,ld), the goal is to construct a route sr=<(l1=ls,t1=ts),...,(lk,tk)> to optimize the time-sensitive route goodness function f(sr). A route with maximum route goodness score tends to be a preferred one. Note that lk is required to be ld for the source-destination query.

2.1 Measuring Route Goodness

We propose that a good trip route should consider the following four factors: (a) the popularity of a place, (b) the proper visiting time of a location, (c) the proper transit time traveling from one location to another, and (d) the visiting order of places in the route. We attempt to model these factors into the goodness function, and utilize such function to greedily selecting locations for the construction of the final trip route.

Route Popularity

If a route contains more popular places, it has higher potential to satisfy a user. The popularity of a place can be represented by the number of recording actions performed at that place. Given a route s=<(l1,t1),(l2,t2),...,(ln,tn)>, we define the popularity-based goodness function ���� � � ��� �� ���� �� , where ��� �� � ���������� , ����� is the number of recording actions performed on location ��, and ���� is the total number of recording actions among all locations.

Proper Visiting Time

We define a Temporal Visiting Distribution for a location l, TVDl (ti), as the probability distribution of a randomly picked recording action of location l occurs at time ti. Then we can determine whether it is proper to visit a place at a given time. We generate a thin Gaussian distribution ���� �� � � � whose mean value � is 8 with a small variance � � (e.g. standard deviation is 1), and measure the difference between the Gaussian distribution with the learnt TVD of such location by symmetric Kullback-Leibler (KL) Divergence. Consequently, the temporal visiting goodness function ������ � of a route s=<(l1,t1), (l2,t2), ..., (ln,tn)> is defined as a combination of the popularity of places together with the fitness of each location over time:

If the places in a route s are visited during the proper time period, the ������ � value would become higher.

Proper Transit Time

We treat the duration between two checked-in places as the summation of the visiting time of the first place plus the transportation time from one place to another. To model such 'visiting plus transit time' between places, we propose the Duration Distribution (DD) between locations li and lj, which is defined as the probability distribution over time duration t, ������ ��� , and can be obtained from the following random experiment: randomly pick two consecutive location recording actions (li,ti), (lj,tj) of a person, and calculate the probability that tj-ti=t. We consider only one-day trip, and therefore treat the outcome space of DD between hours 0 through 24. Given a pair of locations li and lj together with an assignment of a given duration � among them, we model � as a thin Gaussian distribution and compare it with ������ ��� by symmetric KL divergence. Given a route s, the goodness function of durations is defined by:

Visiting Order

We exploit n-gram language model to measure the goodness of the order of visits in a trip route from the location sequence corpus. Technically, we use the average value of the probabilities of uni-gram, bi-gram, and tri-gram to estimate the goodness of orders: ������ � � ���� � � ��� � ����� � ��. Higher forder(s) value represents better quality of route. Note that we utilize the add-one technique for smoothing.

2.2 Final Goodness Function

We divide the final goodness function into two parts and provide a weighting parameter � � ����� for users to determine the significance and balance of such two parts. The first part is the average temporal visiting goodness ������ � and the location transition goodness ��������� � . The second part is visiting order goodness ������ � . The final goodness function � � is defined as

A route � with higher value of � � is considered as a better route. Note that the parameter � provides users the flexibility to specify whether they prefer the time-sensitive routes.

2.3 Route Construction Algorithm

We develop the Guidance Search algorithm to recommend time-sensitive routes for the source and source-destination queries. Guidance Search, consisting of two parts, is a kind of best-first search that finds a least-cost path from a given initial node to the goal. The first is the heuristic satisfaction function, which is in charge of the guidance to determine the next most promising location towards the destination. The second is the backward checking mechanism that keeps the search tree (i.e., all the expanded routes starting from the source location) for reconstructing the route with higher satisfaction score.

We consider the route goodness function � � to design the heuristic satisfaction function � � � , which is to measure the satisfaction of selecting location � as the next visiting location considering the sub-route from source location �� to location � (i.e., �� � �) and from location � to destination location �� (i.e., � � ��). Therefore, we design � � � to have two parts: (1) time-sensitive route goodness function ���� � � �� � � , and (2) heuristic function ���� that considers both the time-sensitive goodness � � � �� and the geographical distance ��� � ��� of a sub-route from location � to destination ��. We use the geographical distance between � and �� as the steering force to direct the search process to move towards the destination location. When selecting next visiting location during the route construction, those locations with shorter distance to the destination has higher chance to be picked, if the rest of the criteria are equally satisfied. Moreover, because there could be many sub-routes from � to �� in the route database, we will compute all the scores and take the best one as the final � � value. Consequently, the heuristic function is formally written as:

where ��� � ��� is the set of sub-routes starting from � to ��. Eventually, the final heuristic satisfaction function is defined as:

where � � ����� is the parameter to control the strength of the guidance to the destination. Higher � indicates stronger guidance. When � � �, � � � is simply a greedy search with the backward checking mechanism, and can be used to tackle the source query (because in � � function, no destination information is needed). Note that � is the most important parameter in our system, which allows users to determine the time-sensitivity of locations in the final routes, according to user needs and scenarios.

The backward checking mechanism is the key to the best-first search in our algorithm. When exploiting the heuristic satisfaction function to choose the next location to visit, it is necessary to expand all neighbor locations to generate the satisfaction scores. We keep track of such scores in the search tree. When it is needed to select the next visiting location, not only the expanded locations from the current location, but also those had ever been expanded during the previous rounds can be considered. In other words, in addition to continue expanding the current location, the algorithm can possibly go backward to consider the previously expanded nodes for finding the ones with the highest satisfaction score.

We elaborate the details of Guidance Search algorithm as follows. We first construct the initial route �� by including the source location ��. A priority queue is employed for the purpose of the backward checking mechanism. Each element in the priority queue consists of a route � and the corresponding heuristic satisfaction score. The priority queue automatically sorts its elements according to their satisfaction scores. We add �� to initialize the priority queue. After setting the final route �� as the initial one ��, we perform the iterative expansion search process until the route �� is constructed up to length �. For each iteration, the last location ����� in the route �� with the highest satisfaction score is identified and each possible next visiting location ����� is put into a candidate set �. Then for each candidate of the next location �� , we can derive the heuristic satisfaction score � � ���� (if �� � �, we set the weighting parameter � � � for the function � � ; otherwise � � � � �). We put � � �� together with the corresponding route ���� into the priority queue. The priority queue will then pick the next best route and location to conduct the further expansions. Finally, the route �� is reported as the final route

3 Experiment

We use Gowalla dataset [Cho et al., 2011] to evaluate our proposed route construction method. Such dataset contains 6,442,890 check-in records from Feb. 2009 to Oct. 2010 on 1,280,969 locations. By regarding a route as a sequence of check-in locations of a user within a day, we have the route database containing 1,136,737 routes whose lengths are more than one (the average length of them is 4.09). We extract three subsets for the experiments, which corresponds to cities of New York (NY), San Francisco (SF), and Paris (PR). We test the effectiveness of our goodness model and demonstrate the performance of the proposed search methods by a time-sensitive location cloze test. Given some real trip routes with time stamp in each location, by removing some middle locations, the goal of cloze experiment is to test whether a method can successfully identify the removed locations. We use Hit Rate as the accuracy measure. Given N removals of locations over all routes, and assumed M places out of N is successfully predicted, the hit rate is defined as M/N. Higher hit rate indicates better quality. We compare our method with a strong greedy algorithm [Hsieh et al., 2012] and a series of baseline methods: (1) Distance-based approach: choose the closest location to the current spot as the next one. (2) Popular-based approach: choose the most popular spot of a given time in that city as the next one. It rates the path using the goodness function ���� � . (3) Forward heuristic: choose the location possessing the largest bi-gram probability with the previous location ���������� as the next location. (4) Backward heuristic: choose the location possessing the largest bi-gram probability with the next location ���������� as the next one.

In the cloze experiment, we vary the number of guessing instance per route and report the hit rate in three cities. Here we set � � ��� (i.e., ���� and ���� are considered as equally important). The results are shown in Figure. 1. In general, the hit rate of each method is decreasing while the number of guessing instance increases. Nevertheless, our method significantly outperforms the greedy search method [Hsieh et al., 2012] and other baselines.

Figure 1: Hit rates by varying the number of guessing instance per route (i.e., 1, 2, 3, 4, and 5) on SF, NY, PR (left to right).

4 Conclusion

We develop the TimeRouter system that measure and recommend time-sensitive trip routes based on user needs on source, destination, current time, and time-sensitivity. Experimental results encourage the promising performance and practicability of our route construction method. TimeRouter is mostly data-driven, which assures diverse results can be learned from different cities in which visiting patterns may vary with different culture and characteristics of the city. Moreover, despite that we emphasized on the check-in data, in fact any kinds of route data (e.g. GPS trajectory data) can be exploited in our framework.