We study a novel problem of influence maximization in trajectory databases that is very useful in precise locationaware advertising. It finds k best trajectories to be attached with a given advertisement and maximizes the expected influence among a large group of audience. We show that the problem is NP-hard and propose both exact and approximate solutions to find the best set of trajectories. We also extend our problem to support the scenario when there are a group of advertisements. We validate our approach via extensive experiments with real datasets.

In this paper, we study a novel problem of influence maximization in trajectory databases that is very useful in precise location-aware advertising. It finds k best trajectories to be attached with a given advertisement and maximizes the expected influence among a large group of audience. We show that the problem is NP-hard and propose both exact and approximate solutions to find the best set of trajectories. In the exact solution, we devise an expansion-based framework that enumerates trajectory combinations in a best-first manner and propose three types of upper bound estimation techniques to facilitate early termination. In addition, we propose a novel trajectory index to reduce the influence calculation cost. To support large k, we propose a greedy solution with an approximation ratio of (1 - 1/e), whose performance is further optimized by a new proposed cluster-based method. We also propose a threshold method that can support any approximation ratio ϵ ∈ (0, 1]. In addition, we extend our problem to support the scenario when there are a group of advertisements. In our experiments, we use real datasets to construct user profiles, motion patterns, and trajectory databases. The experimental results verified the efficiency of our proposed methods.

Trip time prediction is an important problem. Taxi passengers often want to know when they will arrive at their destinations. We design a method of predicting taxi trip time by finding historical similar trips. Trips are clustered based on origin, destination, and start time. Then similar trips are mapped to road networks to find frequent sub-trajectories that are used to model travel time of the various parts of the routes. Experimental results show this method is effective.

Taxi waiting queues or passenger waiting queues usually reflect the imbalance between taxi supply and demand, which consequently decrease a city’s trac system productivity and commuters’ satisfaction. In this paper, we present a queue detection and analysis system to conduct analytics on both taxi and passenger queues. The system utilizes the event-driven taxi traces and the taxi state transition knowledge to detect queue locations at a coordinate level and subsequently identify 4 di↵erent types of queue context (e.g., only passengers queuing or only taxis queuing). More specifically, it adopts the novel and easy-to-implement algorithms to selectively extract taxi pickup events and their critical features. The extracted taxi pickup locations are then used to detect queue locations, and the extracted critical features are used to infer queue context. The extensive empirical evaluations, which run on daily 12.4 million taxi trace records from nearly 15000 taxis in Singapore, demonstrate the high accuracy and stability of the queue analytics results. Finally, we discuss the real world deployment issues and the gained insights from the queue analysis results.

CDR (Call Detail Records) data is more easily available than other network related data (such as GPS data) as most telecommunications service providers (TSPs) maintain such data. By analyzing it one can find mobility patterns of most of the population thus leading to efficient urban planning, disease and traffic control, etc. But its granularity is low as the latitude and longitude (lat-lon) of a cell tower is used as the current location of all mobile phones that are connected to the cell tower at that time. Granularity can range between 10s of metres to several kms depending on population density of a locality. This is one reason why, although there are many existing systems on visualizing mobility of people based on GPS data, there is hardly any existing system for CDR. We develop a Mobility Visualization System (MoVis) for visualizing mobility of people from their CDR records. First of all, given the CDR records of a user, we determine her stay regions (places where she stays for a significant amount of time). Trajectories of phone events (and lat-lon of cell towers) between stay regions are extracted as her trips. Start and end times of a trip are estimated using linear extrapolation. Based on the start and end times, temporal patterns are extracted. Trips with sufficient number of intermediate points are mapped to transport network that consists of train lines, bus routes and expressways. We use Kernel density estimation to visualize the most common path for a given origin and destination. Based on this we create a round-the-clock visualization of mobility of people over the entire city separately for weekdays and weekends. At the end we show the validation results.

In this paper, we propose a generic framework to learn context-aware latent representations for context-aware collaborative filtering. Contextual contents are combined via a function to produce the context influence factor, which is then combined with each latent factor to derive latent representations. We instantiate the generic framework using biased Matrix Factorization as the base model. A Stochastic Gradient Descent (SGD) based optimization procedure is developed to fit the model by jointly learning the weight of each context and latent factors. Experiments conducted over three real-world datasets demonstrate that our model significantly outperforms not only the base model but also the representative context-aware recommendation models.

One major problem of using location data collected from mobile cellular networks for mobility modelling is the oscillation phenomenon. An oscillation occurs when a mobile phone intermittently switches between cell towers instead of connecting to the nearest cell tower. For the purpose of mobility modeling, the location data needs to be cleansed to approximate the mobile device's actual location. However, this constitutes a challenge because the mobile device's true location is not known. In this paper, we study the oscillation resolution problem. We propose an algorithm framework called DECRE (Detect, Expand, Check, Remove) to detect and remove oscillation logs. To make informed decisions DECRE includes four steps: Detect, to identify log sequences that may contain oscillation using a few heuristics based on the concepts of stable period and moving at impossible speed, Expand, to look before and after suspicious records to gain more information, Check, to check whether a cell tower is observed repeatedly (which is a strong indication of oscillation), and Remove, resolving oscillation by selecting a cell tower to approximate the mobile device's actual location. Our experimental results on travel diaries show that our oscillation resolution approach is able to remove records that are far from mobile device's ground-truth locations, improve the quality of the location data, and performs better than an existing method. Our performance study on large scale cell tower data shows that the MapReduce implementation of our approach is able to process 1 Terabyte of cell tower data in five hours using a small cluster.

Personal mobile data are being extensively collected by various service providers, in the form of data stream. Most service providers promise their customers for not misusing their data by paper-based agreement. However, the customers have no way to know whether the agreements are strictly followed or not, unless any scandals of private data misuse are revealed. To guarantee the correct use of customers' personal data and assure them of the service safety, system-level data privacy control between the data owners (i.e., Customers) and the data users (i.e., Service providers) is in compelling need. Inspired by the concept of Hippocratic data management, we design and implement a system, Hip Stream to systemically enforce different Hippocratic principles to preserve data providers' privacy when they send their data stream for services. In this paper, we describe the architecture of the Hip Stream system and demonstrate how it meets those privacy principles.

Geographic objects associated with descriptive texts are becoming prevalent, justifying the need for spatial-keyword queries that consider both locations and textual descriptions of the objects. Specifically, the relevance of an object to a query is measured by spatial-textual similarity that is based on both spatial proximity and textual similarity. In this article, we introduce the Reverse Spatial-Keyword k -Nearest Neighbor (RSK k NN) query, which finds those objects that have the query as one of their k -nearest spatial-textual objects. The RSK k NN queries have numerous applications in online maps and GIS decision support systems. To answer RSK k NN queries efficiently, we propose a hybrid index tree, called IUR-tree (Intersection-Union R-tree) that effectively combines location proximity with textual similarity. Subsequently, we design a branch-and-bound search algorithm based on the IUR-tree. To accelerate the query processing, we improve IUR-tree by leveraging the distribution of textual description, leading to some variants of the IUR-tree called Clustered IUR-tree (CIUR-tree) and combined clustered IUR-tree (C 2 IUR-tree), for each of which we develop optimized algorithms. We also provide a theoretical cost model to analyze the efficiency of our algorithms. Our empirical studies show that the proposed algorithms are efficient and scalable.

The Electronic Road Pricing (ERP) system was implemented by the Land Transport Authority of Singapore to control traffic by road pricing since 1998. To better understand the traffic condition and improve the pricing scheme, the government initiated the next generation ERP (ERP 2) project, which aims to use the Global Navigation Satellite System (GNSS) collecting positional data from vehicles for analysis. However, most drivers fear of being monitored once the government installs the devices in their vehicles to collect GPS data. The existing data stream management systems (DSMS) centralize both data management and privacy control at server site. This framework assumes DSMS server is secure and trustable, and protects providers' data from illegal access by data users. In ERP 2, the DSMS server is maintained by the government, i.e., data user. Thus, the existing framework is not adoptable. We propose a novel framework in which privacy protection is pushed to data provider site. By doing this, the system could be safer and more efficient. Our framework can be used for the situations such as ERP 2, i.e., data providers would like to control their own privacy policies and/or the workload of DSMS server needs to be reduced.

Path prediction is useful in a wide range of applications. Most of the existing solutions, however, are based on eager learning methods where models and patterns are extracted from historical trajectories and then used for future prediction. Since such approaches are committed to a set of statistically significant models or patterns, problems can arise in dynamic environments where the underlying models change quickly or where the regions are not covered with statistically significant models or patterns.

Path prediction is presently an important area of research with a wide range of applications. However, most of the existing path prediction solutions are based on eager learning methods which commit to a model or a set of patterns extracted from historical trajectories. Such methods do not perform very well in dynamic environments where the objects' trajectories are affected by many irregular factors which are not captured by pre-defined models or patterns. In this demonstration, we present the "R2-D2" system that supports probabilistic path prediction in dynamic environments. The core of our system is a "semi-lazy" learning approach to probabilistic path prediction which builds a prediction model on the fly using historical trajectories that are selected dynamically based on the trajectories of target objects. Our "R2-D2" system has a visual interface that shows how our path prediction algorithm works on several real-world datasets. It also allows us to experiment with various parameter settings.

We present a novel elastic system architecture called Plug Cloud, which aims to increase the power of low-compute (and possibly mobile) devices, such as tablets, through distributing high-compute tasks, such as rendering, data analysis and visualization, to a set of Plug Computers [1, 2] that can be added or removed from the system incrementally. These devices are connected through a wired/wireless connection and the network is formed seamlessly with zero configurations. Plug Cloud allows users of low-compute devices to acquire more processing power externally on demand by plugging one or more plug-computers as needed. Furthermore, it allows a user to remove the plug-computer safely at any time without bringing down the whole system. This makes an elastic network where it can expand and shrink automatically with one or more plug-computers being added or removed from the system. This innovative architecture forms a personal cloud infrastructure on demand to support users' computational needs. We have implemented a computer graphics rendering application using Plug Cloud architecture. We will demo our architecture and prototype system using a tablet and several plug-computers.

Big data management and analysis has become a hot topic in academic and industrial research. In fact, a large portion of big data in service today are initially streaming data. To preserve the privacy of such data that are collected from data streams, the most efficient way is to control the process of data collection according to corresponding privacy polices. In this paper, we design a framework to support data stream management with privacy-preserving capabilities. In particular, we focus on two premier principles of data privacy, limited disclosure and limited collection. With these two principles guaranteed, the archived data will not necessarily be checked for privacy protection, before analysis and other operations can be done.

We demonstrate a system that monitors the taxi availability at taxi stands by mining real-time taxi trajectory data streams. The system includes a server-side trajectory data stream processing and mining program and a client-side mobile application for Android smart phones. The server program continuously monitors for each taxi stand the numbers of taxis queueing at the taxi stand, the numbers of taxis that will pass the taxi stand, as well as the traffic conditions in the area around the stand. It delivers real time taxi and traffic information to mobile users via Restful web services. The client-side location-based mobile application consumes these services to help mobile users make informed transportation choices. For example the availability of taxis might yet be a deterrent when traffic is congested. Real world taxi trajectory data from more than 14000 taxis are used in the demo.

In mobile sensor networks (MSNs), it is common for the base station to issue {\em data acquisition} queries requesting for data to be sensed from specific regions of the data space. Such kind of queries are especially important in MSNs for reconnaissance and disaster rescue applications. In this paper, we investigate how multiple data acquisition queries can be answered quickly in sparse mobile sensor networks. Because of the sparseness and mobility, the number of sensors is limited, the connection is intermittent and the topology is unpredictable. To effectively handle the above challenges, we design distributed schemes where mobile sensors strategically relocate themselves to proper locations to collaboratively facilitate efficient query processing and enable sharing over space and time. We first propose a novel scheme, {\em Dynamic}, that enables queries to share resources at runtime while sensors are greedily relocated to benefit the processing of each query. We also design another scheme, {\em aMST}, that optimizes a batch of queries as a whole and utilizes a Minimum Steiner Tree to guide the execution of all queries in the batch. In addition, a parameter is defined to guide the selection of the most appropriate scheme to adapt to the environment. Our extensive performance study shows the effectiveness of our proposed schemes.

The MaxBRNN problem finds a region such that setting up a new service site within this region would guarantee the maximum number of customers by proximity. This problem assumes that each customer only uses the service provided by his/her nearest service site. However, in reality, a customer tends to go to his/her k nearest service sites. To handle this, MaxBRNN can be extended to the MaxBRkNN problem which finds an optimal region such that setting up a service site in this region guarantees the maximum number of customers who would consider the site as one of their k nearest service locations. We further generalize the MaxBRkNN problem to reflect the real world scenario where customers may have different preferences for different service sites, and at the same time, service sites may have preferred targeted customers. In this paper, we present an efficient solution called MaxFirst to solve this generalized MaxBRkNN problem. The algorithm works by partitioning the space into quadrants and searches only in those quadrants that potentially contain an optimal region. During the space partitioning, we compute the upper and lower bounds of the size of a quadrant's BRkNN, and use these bounds to prune the unpromising quadrants. Experiment results show that MaxFirst can be two to three orders of magnitude faster than the state-of-the-art algorithm.

The processing of a Continuous Reverse k-Nearest-Neighbor (CRkNN) query on moving objects can be divided into two sub tasks: continuous filter, and continuous refinement. The algorithms for the two tasks can be completely independent. Existing CRkNN solutions employ Continuous k-Nearest-Neighbor (CkNN) queries for both continuous filter and continuous refinement. We analyze the CkNN based solution and point out that when k > 1 the refinement cost becomes the system bottleneck. We propose a new continuous refinement method called CRange-k. In CRange- k, we transform the continuous verification problem into a Continuous Range-k query, which is also defined in this paper, and process it efficiently. Experimental study shows that the CRkNN solution based on our CRange-k refinement method is more efficient and scalable than the state-of-the- art CRkNN solution.

A Reverse k -Nearest-Neighbor (RkNN) query finds the objects that take the query object as one of their k nearest neighbors. In this paper we propose new solutions for evaluating RkNN queries and its variant bichromatic RkNN queries on 2-dimensional location data. We present an algorithm named INCH that can compute a RkNN query's search region (from which the query result candidates are drawn). In our RkNN evaluation algorithm called FINCH, the search region restricts the search space, and the search region is tightened each time a new result candidate is found. We also propose a method that enables us to apply any RkNN algorithm on bichromatic RkNN queries. With that, our FINCH algorithm is also used to evaluate bichromatic RkNN queries. Experiments show that our solutions are more efficient than existing algorithms.

A moving k-nearest-neighbor (MKNN) query is a continuous k-nearest-neighbor (KNN) query issued by a moving object. As both the query owner and other mobile objects are moving, the influenced area (i.e., cells in the cellular networks), and query result of a MKNN query change with time. Existing processing techniques for MKNN queries are all centralized approaches which rely on the location update messages from moving objects. However, these approaches typically employ complex data structures and algorithms. Moreover, the server may not be able to cope with a high location report rate which is necessary to ensure accurate and correct answers. In this paper, we propose a distributed strategy to process MKNN queries in real-time. In our scheme, called disMKNN, the server and moving objects collaborate to maintain the KNN of a MKNN query. While the server keeps track of a MKNN query's influenced cells, moving objects within the cells monitor their own relationships (i.e., whether they are part of the KNN answers) to the query. Results of an extensive performance study show the effectiveness of disMKNN.

In this paper, we propose iSEE, a set of algorithms for efficient processing of continuous k-nearest-neighbor (CKNN) queries over moving objects. iSEE utilizes a grid index and incrementally updates the queries' results based on moving objects' explicit location update messages. We have three innovations in iSEE: a Visit Order Builder (VOB) method that dynamically constructs a query's optimal visit order to the cells in the grid index with low cost, an Efficient Expand (EFEX) algorithm which avoids unnecessary and redundant searching when updating a query's result, and an efficient algorithm that quickly identifies the cells that should be updated after a query's result is changed. Experimental results show that iSEE achieves a 2X speedup, when compared with the state-of-the-art CPM scheme.

Short-range wireless technologies such as IEEE802.11 and Bluetooth enable mobile hosts in broadcast systems to manage cache cooperatively. In nonuniform broadcast systems, hot data are broadcast more frequently than cold data are. Cooperative cache management schemes adaptive to nonuniform broadcast are desirable. In this paper, we first propose a Keep Requesting (KR) extension for existing cooperative cache management schemes, then we propose two novel schemes: Global-Cache-Miss initiated Caching Management (GCM) and Motion-aware Caching Management (MCM). Extensive experiments show that GCM and MCM improve response time, help conserve energy, and adapt to nonuniform broadcast.