Optimal location problems identify the best sites to set up new facilities for providing service to its users. Majority of the existing work in this space assumes that the users are static and the datasets are small. Such assumptions are too restrictive and unrealistic for reallife services such as setting up of fuel stations, upgradation of cellphone base-stations, etc. The placement of such services should, however, factor in the mobility patterns of its consumers, i.e., the user trajectories. For example, given a budget of k locations to set up fuel stations, the objective should be to cover the maximum number of user trajectories. In this doctoral work, we introduce top-k optimal location problems for large-scale trajectory-aware services. Since these problems are NP-hard, we design scalable techniques with bounded quality guarantees that work directly with user trajectories over city-scale road networks. Empirical evaluations show that the proposed heuristics are highly efficient, both in terms of space overhead and running time, as well as quite effective, with quality close to that of the optimal.
One of the most important problems in planning of services is
to identify the best locations to set up new facilities (or improve
existing facilities) with respect to a given service [
Majority of the existing works on OL problems assume that the
users of the service are static. Such an assumption is often too
prohibitive. For example, services such as mobile services, fuel
stations, bill boards, traffic monitoring systems, etc. are widely
accessed by users while commuting. Consequently, the placement of
such facilities require taking into consideration the mobility
patterns (or trajectories) of the users rather than their static locations
[
To illustrate the need for trajectory-aware planning of services, consider Fig. 1. There are seven candidate locations, S1; : : : ; S7, to set up a service, out of which five are either home or office locations. There are five users commuting between home and office locations whose trajectories are shown. Using this figure, we next motivate three scenarios of trajectory-aware services.
Scenario 1: A company wants to open two new fuel stations. A trajectory of a user is satisfied only if it passes through at least one of the fuel stations. If only the static locations are considered, i.e., any two out of the five office and residential areas are to be selected, no combination would satisfy all the trajectories. In contrast, if we factor in the mobility of the users, choosing S1 and S3 as the installation locations satisfies all trajectories. Note that it is not enough to simply look at trajectory counts in each possible installation location and then choosing the two most frequent ones. By that strategy, a location such as S2 would be chosen along with S1. This combination is not effective since the same trajectories pass through both, thereby reducing each other’s utilities (a process sometimes referred to as cannibalization in economics). Scenario 2: Suppose a mobile service provider wants to set up two base-stations to provide good quality of experience to the commuting users. In this case, a user is satisfied if it receives good service for a large fraction of its trajectory. The selection fS1; S2g satisfying 3 trajectories is the optimal choice. An alternative selection such as fS1; S3g can offer good quality of service only in a limited segment of the incident trajectories, thereby not satisfying even a single trajectory.
Scenario 3: Suppose a company plans to set up two fuel stations that minimize the maximum inconvenience, i.e. the extra distance travelled by a user to avail a service. The optimal solution is fS1; S3g (or fS2; S3g) with maximum inconvenience being 0. Any other solution would have non-zero maximum inconvenience since at least one user needs to travel non-zero extra distance to reach to the nearest fuel station.
The objective of this doctoral thesis is to develop an efficient framework for planning of large-scale trajectory-aware services such as the scenarios described above. More specifically, given n candidate service locations, the proposed models enable the service provider to identify the best k locations to set up new service or improve existing service by factoring in the trajectories of its users. The models allow the service providers to specify a wide range of objectives and constraints depending on the choice of service. To model various objectives, we associate a utility function Uj with each trajectory Tj in the problem. This utility function captures how well a trajectory is served by a given set of service locations. The goal is to determine k out of n candidate locations that maximize the sum of trajectory utilities Uj over all the trajectories.
Motivated by the above three scenarios, we study three classes of problems namely, TOPS, TUMP and TIPS, which are described in Sec. 2, 3 and 4, respectively.
The contributions and significance of this doctoral thesis are summarized as follows: ? Novelty: To the best of our knowledge, this is the first extensive work to study efficient computation of placement of large-scale trajectory-aware services . The proposed models are highly generic and can be easily adapted to meet various service requirements. ? Hardness: We show that the TOPS, TUMP and TIPS problems are NP-hard. We develop optimal algorithms for each of them and show why they are impractical. ? Efficiency: We develop several interesting heuristics for each of the three problems. The proposed solutions are highly efficient both in terms of space overhead and running time. ? Effectiveness: While the proposed heuristics have theoretically bounded quality guarantees, the empirical evaluations show that they are quite close to the optimal. ? Extensive Benchmarking: We benchmark the proposed solutions through extensive experimental evaluation over real and synthetic large-scale datasets. The impact of various parameters such as budget, coverage threshold, trajectory-length, city geometries, etc. are thoroughly evaluated across multiple large-scale datasets.
We next describe in detail the TOPS, TUMP and TIPS problems.
Referring to Scenario 1, here we consider the problem of OL queries for services such as fuel-stations, ATMs, convenience stores, bill boards, etc., that are typically demanded only intermittently, and not continuously throughout the trip.
Consider a road network G = fV; Eg over a geographical area where V = fv1; : : : ; vN g denotes the set of road intersections (usually referred to as vertices or nodes), and E denotes the road segments between two adjacent road intersections. To model the direction of the underlying traffic that passes over a road segment, we assume that the edges are directed. Assume a set of candidate sites S = fs1; ; sng V where a certain service or facility can be set up. The set S can be in addition to existing service locations. Without loss of generality, we can augment the vertices V to include all the sites. Thus, S V .
The set of trajectories over G is denoted by T = fT1; ; Tmg
where each trajectory Tj is a sequence of nodes Tj = fvj1 ; ; vjl g,
vji 2 V . The trajectories are usually recorded as GPS traces and
may contain arbitrary spatial points on the road network. For our
purpose, each trajectory is map-matched [
Suppose d(vi; vj ) denotes the shortest network distance along a directed path from node vi to vj , and dr(vi; vj ) denotes the shortest distance of a round-trip starting at node vi, visiting vj , and returning to vi, i.e., dr(vi; vj ) = d(vi; vj ) + d(vj ; vi). In general, d(vi; vj ) 6= d(vj ; vi), but dr(vi; vj ) = dr(vj ; vi). With a slight abuse of notation, assume that dr(Tj ; si) denotes the extra distance traveled by the user on trajectory Tj to avail a service at site si. Formally, dr(Tj ; si) = min8vk;vl2Tj fd(vk; si) + d(si; vl) d(vk; vl)g.
It is convenient for a user to avail a service only if its location is not too far off from her trajectory. Thus, beyond a distance , we assume that the utility offered by a site si to a trajectory Tj is 0. We call this user-specified distance as the coverage threshold.
DEFINITION 1 (COVERAGE). A site si covers a trajectory Tj if the distance dr(Tj ; si) is at most , where 0 is the coverage threshold.
For all sites within the coverage threshold , the user also specifies a preference function . The preference function (Tj ; si) assigns a score (normalized to [0; 1]) for a trajectory Tj and a site si that indicates how much si is preferred by the user on trajectory Tj . Higher values indicate higher preferences with 0 indicating no preference. In general, sites that are closer to the trajectory have higher preferences than those farther away.
DEFINITION 2 (PREFERENCE FUNCTION ). : (T ; S) ! [0; 1] is a real-valued preference function defined as follows: (f (dr(Tj ; si)) if dr(Tj ; si) (Tj ; si) = 0
The goal of the TOPS query is to report a set of k sites Q S; jQj = k, that maximizes the preference score over the set of trajectories. The preference score of a trajectory Tj over a set of sites Q is defined as the utility function Uj for Tj , which is simply the maximum score corresponding to the sites in Q, i.e., Uj = maxsi2Qf (Tj ; si)g.
The generic TOPS query formulation is stated next.
PROBLEM 1 (TOPS). Given a set of trajectories T , a set of candidate sites S that can host the services, the TOPS problem with query parameters (k; ; ) seeks to report the best k sites, Q S; jQj = k, that maximize the sum of trajectory utilities, i.e., Q = arg max Pm
j=1 Uj where Uj = maxsi2Qf (Tj ; si)g.
We show that the TOPS problem is NP-hard [
We propose a greedy approximation algorithm INC-G REEDY to
solve TOPS. This is based on the principle of maximizing marginal
gain. In successive k iterations, it picks a site that offers maximal
gain in the utility U . The approximation bound of this algorithm is
maxf1 1=e; k=ng. To improve the performance of this algorithm,
we use FM Sketches [
We first state one basic observation. If two sites are close, the sets of trajectories they cover are likely to have a high overlap. Hence, when k n, which is typically the case, the sites chosen in the answer set are likely to be distant from each other. The index structure, NETCLUS, is designed based on the above observation.
Clustering of sites based on similarities between set memberships (such as Jaccard similarity of trajectory sets covered by two sites) will not be useful since they depend on the coverage threshold which is available only at run time. Hence, we adopt distancebased clustering. If two sites are close to each other, their utilities as well as the sets of trajectories they cover are likely to be similar. Hence, it is unlikely for two sites belonging to the same cluster to be part of the answer set. Therefore, if INC-G REEDY is performed only on the clusters instead of the sites, the answer sets returned and their corresponding utilities are likely to be similar.
Our method follows two main phases: offline and online. In the offline phase, clusters are built at multiple resolutions. This forms the different index instances. A particular index instance is useful for a particular range of query coverage thresholds. In the online phase, when the query parameters are known, first the appropriate index instance is chosen. The INC-G REEDY algorithm is then run with the cluster representatives on that instance. We omit the details in the interest of space.
Next we outline the solution at a high level. Given the raw GPS
traces of user movements, they are map-matched [
We evaluate our heuristics on a publicly available and widely
used real dataset consisting of GPS traces of taxis from Beijing
[
To study the impact of city geographies, we also evaluate our solutions on three synthetic datasets that emulate trajectories in the patterns followed in New York, Atlanta and Bangalore. We use an online traffic generator tool, MNTG (http://mntg.cs.umn.edu/tg/ index.php) to generate the traffic traces.
We observe that NETCLUS is up to 2 orders of magnitude faster than INC-G REEDY while yielding solutions that are within 90% of that of INC-G REEDY. The use of FM sketches for efficiently computing the site offering maximal marginal utility, yields speed up of 3- 6 times. Importantly, while INC-G REEDY goes out of memory for 1:6 km on a 32 GB machine, NETCLUS requires less than 3 GB memory for different values of the query parameters. We also find that the longer trajectories are easier to serve than the shorter trajectories, as they can be served through a larger pool of candidate sites. In addition, NETCLUS can efficiently absorb dynamic updates such as change in trajectories or candidate locations.
Referring to Scenario 2, here we focus on cellular services that aim to provide good quality of experience (QoE) not just at few discrete points, but throughout the trip.
Consider a cellular network B = fB1, . . . , Bng of n base-stations spread across a region. A trajectory Tj is represented as a sequence of tuples of the form i = hBi; i; ii that captures the user experience. The user on this trajectory was connected to the base-station Bi 2 B for a time interval of i units and received a throughput of i bytes per unit of time. Note that i can be any metric as long as a greater i denotes better experience (e.g., throughput or packet success rate) when associated to a respective base-station. Henceforth, for brevity, we refer to this metric as throughput. These trajectories and i’s can be constructed by scanning the active transaction records maintained by the network operator.
For ease of notation, we write Bi 2 Tj if the base-station Bi 2 B lies on the trajectory Tj . The length of a trajectory Tj , denoted by jTj j, is simply the count of base-stations that lie on it. Suppose d denotes the maximum length of a trajectory.
For a trajectory Tj , a base-station Bi 2 Tj is a bottleneck basestation if it offers a degraded quality of service, e.g., an extremely low upload/download speed, a call-drop, etc. In our model, we assume that a base-station Bi acts as a bottleneck w.r.t. a trajectory Tj if the corresponding throughput is less than a threshold, i.e., i < . The value of is computed from a combination of network parameters. A base-station that is a bottleneck for one trajectory may not be a bottleneck for other trajectories since different users may experience different throughputs based on various factors such as data plan, time of the day, etc.
Our goal is to maximally improve the mobile user experience by selectively upgrading k out of n base-stations that act as bottlenecks on some trajectories. Suppose X = fx1; : : : ; xng denotes the boolean solution vector such that xi = 1 if and only if basestation Bi is chosen for upgradation and 0 otherwise.
Given a trajectory Tj , we define the weight wji for each basestation Bi 2 Tj , that accounts for the fraction of the total time that the user (on this trajectory) was connected to the base-station Bi. More precisely, wji = i . Suppose bji denotes a
PBi2Tj i bottleneck indicator variable that takes value 1 if the base-station Bi 2 Tj is a bottleneck base-station w.r.t. Tj , and 0 otherwise.
Given a trajectory Tj and solution X, we define a bottleneck utility function Wj as follows:
Wj =
X Bi2Tj ;bji=0 wji +
X Bi2Tj ;bji=1 wji:xi (2) Wj essentially captures the fraction of the total time when the user enjoys acceptable QoE on the trajectory Tj . If all the base-stations on Tj are non-bottleneck, then Wj = 1; otherwise, Wj < 1. Henceforth, we consider the bottleneck utility function as the default trajectory utility function.
Based on this, we next define a class of trajectories that enjoy satisfactory QoE after upgradation of the base-stations.
DEFINITION 3 ( - BOTTLENECK- FREE TRAJECTORY). A trajectory Tj 2 T is -bottleneck-free if its utility Wj where Wj is given by Eq. (2), and 2 [0; 1] is the bottleneck parameter.
Our aim is to maximize the number of trajectories with high utility. To do so, given the bottleneck utility function Wj , we map it to a step utility function Uj using a threshold (0 1), henceforth referred to as the bottleneck parameter:
Uj = (1 0 if Wj
PROBLEM 2 (TUMP( )). Given a base-station network B of size n, a budget parameter k, a bottleneck parameter , and a set of m trajectories T = fT1; : : : ; Tmg, each of which has an associated utility function Wj , determine the set of k base-stations to upgrade such that the sum of utilities P where Uj is given by Eq. (3).
We show that the TUMP( ) problem is NP-hard due to a
reduction from the k-Vertex Cover ( k-VC) problem [
Our problem formulation enables the network operator to suitably select the bottleneck parameter based on the application requirements. For example, = 1 is suitable for real-time applications such as voice calls or video conferences whereas = 0:8 may suffice for video streaming since video players can mask-off certain durations of low connectivity by buffering. Similarly, even = 0:5 may be enough for elastic applications such as background synchronization of emails.
Since the TUMP( ) problem is NP hard, we design four
approximation algorithms based on linear programming, and greedy
paradigm [
We show that DEC-G REEDY algorithm can be incrementally applied to an evolving network; i.e., as and when the operator allocates additional budget, this algorithm can be applied to incrementally evolve the network from one generation to another.
Among the different algorithms that we design for the TUMP problem, DEC-G REEDY provides the optimum balance between quality and running time. On thorough empirical evaluation across multiple datasets emulating different city topologies, it is observed that DEC-G REEDY offers significantly higher quality than the other algorithms, especially at low budgets and higher , i.e., higher QoE requirements. For example, with an upgrade budget of k = 20% and = 0:8, DEC-G REEDY returns solutions that serve 3- 8 times more number of users than an approach that uses a greedy locationbased base-station upgrade.
We also observe that the investment required to provide satisfactory QoE to mobile users is dependent on the population distributions and their road-network. Specifically, cities with a dense central business districts, such as New York, need less budget to satisfy a large segment of mobile users than cities where businesses are spread out (e.g., Atlanta).
Referring to Scenario 3, the next problem is related to the TOPS problem, which we refer to as Trajectory-aware Inconvenienceminimizing Placement of Services (TIPS), stated as follows:
PROBLEM 3 (TIPS). Given a set of trajectories T , a set of candidate sites S that can host the services, the TIPS problem with query parameter k seeks to report the best k sites, Q S ; jQj = k, that minimizes the maximum (average) inconvenience, i.e., the extra distance travelled by a commuting user in order to avail a service at her nearest service location. of the two versions of the problem. We are working towards a scalable implementation of these heuristics. For evaluation, we use the same real and synthetic datasets, as in the case of the TOPS problem. The preliminary results show that the proposed solutions are highly effective and efficient.
With expansion of cities, and growing urban population, more people are required to commute longer distances, and thereby generating new demands for various services such as fuel stations, food joints, mobile services, retail stores, etc. In this light, identifying the best service-locations is highly critical to the success of these trajectory-aware services. The large-scale road networks and high volume of trajectories to be served, make these problems extremely challenging. This doctoral thesis introduces three such optimal location problems, namely TOPS, TUMP, and TIPS and develop efficient and effective frameworks to solve them.