Inference and prediction of routes have become of interest over the past decade owing to a dramatic increase in package delivery and ride-sharing services. Given the underlying combinatorial structure and the incorporation of probabilities, route prediction involves techniques from both formal methods and machine learning. One promising approach for predicting routes uses decision diagrams that are augmented with probability values. However, the effectiveness of this approach depends on the size of the compiled decision diagrams. The scalability of the approach is limited owing to its empirical runtime and space complexity. In this work, our contributions are two-fold: first, we introduce a relaxed encoding that uses a linear number of variables with respect to the number of vertices in a road network graph to significantly reduce the size of resultant decision diagrams. Secondly, instead of a stepwise sampling procedure, we propose a single pass sampling-based route prediction. In our evaluations arising from a real-world road network, we demonstrate that the resulting system achieves around twice the quality of suggested routes while being an order of magnitude faster compared to state-of-the-art.

The fundamental problem of weighted sampling involves sampling of satisfying assignments of Boolean formulas, which specify sampling sets, and according to distributions defined by pre-specified weight functions to weight functions. The tight integration of sampling routines in various applications has highlighted the need for samplers to be incremental, i.e., samplers are expected to handle updates to weight functions. The primary contribution of this work is an efficient knowledge compilation-based weighted sampler, INC, designed for incremental sampling. INC builds on top of the recently proposed knowledge compilation language, OBDD[AND], and is accompanied by rigorous theoretical guarantees. Our extensive experiments demonstrate that INC is faster than state-of-the-art approach for majority of the evaluation. In particular, we observed a median of 1.69X runtime improvement over the prior state-of-the-art approach.

Accurate traffic forecasting is a fundamental challenge of location-based systems. Recent works were able to achieve state-of-the-art results by incorporating Graph Convolutional Networks (GCN) to capture spatial dependencies in the data. However, these works rely on a fixed latent feature representation of the underlying graph structure, failing to exploit the rich spatial information offered by the road network. In this paper, we propose the Topologically Enhanced Spatial-Temporal Graph Convolutional Network (TEST-GCN), a novel graph convolution model for road traffic speed forecasting based on floating car data, aiming to better capture the spatial dependencies in the data by fully exploiting the characteristics of the road network. We introduce the node and edge embedding layers, using topological attributes to iteratively improve the latent feature representation of the road network. We show that our model effectively captures both spatial and temporal dependencies in the data, consistently outperforming state-of-the-art methods in road traffic speed prediction, achieving approximately 50 % reduction in model size and 33% improvement in empirical computational times.

Traditional location-based service profiles user's traits by looking for patterns in historical mobility behaviors. Yet, from time to time, people are adventurous and would often like to go to unvisited places, or follow new transition paths. At that time, their next movements will be inconsistent with any previous patterns, making location-based recommendations inaccurate and irrelevant to user's real need. Under such circumstance, an alternative strategy is to figure out user's destination and intention before recommendation, where the ability to predict new and unusual mobility patterns plays a critical role. In this paper, we define the next location that breaks the earliest on-going patterns as a Point of Change (POC). To predict POCs, we introduce a mobility model, called ST-Pattern Network, to learn the occurrences of POCs under the regularity of spatial-temporal patterns. By computing the similarities of matched patterns, our model can online predict future POCs as well as fit recent trajectory via a pattern network. Experiments show 10% accuracy improvement on POC prediction can be achieved over traditional Markov models. Furthermore, we are able to categorize the POC into more refined scenarios so that different recommendations can be suggested under different circumstances.

Telecommunication companies possess mobility information of their phone users, containing accurate locations and velocities of commuters travelling in public transportation system. Although the value of telecommunication data is well believed under the smart city vision, there is no existing solution to transform the data into actionable items for better transportation, mainly due to the lack of appropriate data utilization scheme and the limited processing capability on massive data. This paper presents the first ever system implementation of real-time public transportation crowd prediction based on telecommunication data, relying on the analytical power of advanced neural network models and the computation power of parallel streaming analytic engines. By analyzing the feeds of caller detail record (CDR) from mobile users in interested regions, our system is able to predict the number of metro passengers entering stations, the number of waiting passengers on the platforms and other important metrics on the crowd density. New techniques, including geographical-spatial data processing, weight-sharing recurrent neural network, and parallel streaming analytical programming, are employed in the system. These new techniques enable accurate and efficient prediction outputs, to meet the real-world business requirements from public transportation system.

In order to overcome the limitation on small sizes of gene datasets, many meta-classification methods which ensemble classifiers with different datasets have been developed. However, due to discrepancies of the characteristics within heterogeneous or cross-platform datasets, the number of common and significant genes is usually small. Instead of matching common genes between heterogeneous datasets, we propose a novel solution, alternative feature mapping approach (AFM), to utilize related and discriminative gene expressions while not necessarily having exact matches. Genes in the training dataset are clustered and mapped to the test dataset as gene groups. Through analyzing the correlation within gene groups between training and test datasets, related significant genes can be applied for classification. We conducted experiments consisting of 8 heterogeneous datasets with different cancer types and platforms to test the effectiveness of AFM. Our experiments show that classification performance is greatly improved using suitable significant genes selected by AFM.