Sequential recommenders aim to enhance prediction accuracy by leveraging user interaction sequences, with transformer-based models showing particularly strong performance. Among them, cold-start sequential recommenders are particularly challenging because these models typically require extensive historical data to perform optimally. Some works attempt to address this issue by enhancing the adaptive ability of the sequence recommenders with meta-learning approaches. However, they are unsuitable for enhancing the popular Transformer-based sequence recommenders: MAML-based models cannot adapt the large number of parameters of Transformers, while transition-based and metric-based meta-learning models rely on unique architectures that are incompatible with Transformer-based frameworks. Also, they usually lack mechanisms to recognize and cater to multiple interests within short interaction sequences. To address these limitations, we propose MESA, a meta-modulation plugin module specifically designed to enhance the cold-start recommendation of Transformer-based sequential recommender systems. (1) We design a meta-modulation method to directly modulate the parameters in Transformer-based sequence encoders, thus enabling the model to adapt more effectively to new users in cold-start scenarios. (2) Additionally, MESA integrates the Mixture of Experts (MoE) mechanism, which refines sequence representations by utilizing multiple experts, each focusing on different aspects of user interests. This structure enhances the personalization of the recommendation by effectively handling diverse user interests within the sequences. Experiments demonstrate the effectiveness of MESA in cold-start scenarios. Our codes are available here : https://github.com/Mushroom-cat/MESA .

Graph Contrastive Learning (GCL) has recently garnered significant attention for enhancing recommender systems. Most existing GCL-based methods perturb the raw data graph to generate views, performing contrastive learning across these views to learn generalizable representations. However, most of these methods rely on data- or model-based augmentation techniques that may disrupt interest consistency. In this paper, we propose a novel interest-aware augmentation approach based on diffusion models to address this issue. Specifically, we leverage a conditional diffusion model to generate interest-consistent views by conditioning on node interaction information, ensuring that the generated views align with the interests of the nodes. Based on this augmentation method, we introduce DiffCL, a graph contrastive learning framework for recommendation. Furthermore, we propose an easy-to-hard generation strategy. By progressively adjusting the starting point of the reverse denoising process, this strategy further enhances effective contrastive learning. We evaluate DiffCL on three public real-world datasets, and results indicate that our method outperforms state-of-the-art techniques, demonstrating its effectiveness.

As a powerful tool to alleviate the data sparsity and cold-start problems in traditional recommender systems, cross-domain recommendation hinges on addressing two fundamental questions: how to transfer knowledge and what to transfer. Regarding the two questions, existing methods have limitations, such as restricted domain connections, inadequate representation disentanglement, and insufficient knowledge transfer. To overcome these challenges, we propose a novel model, KDCLM, which integrates sophisticated knowledge distillation and contrastive learning mechanisms within a multi-view graph architecture. The proposed model comprises two views—a local view and a global view—both of which construct multiple graphs based on user–item interactions to establish richer domain connections. Specifically, the local view incorporates two contrastive learning mechanisms: one for aligning domain-invariant representations and another for differentiating domain-specific representations, which jointly achieve effective representation disentanglement. In addition, we employ knowledge distillation between the global heterogeneous user–item interaction graph and the homogeneous user–user and item–item relationship graphs to facilitate sufficient knowledge transfer. Through extensive experiments on real-world cross-domain recommendation tasks, our proposed KDCLM model demonstrates significant improvements over current state-of-the-art methods. We release our source code at https://github.com/fanydan/KDCLM .

Social recommendation systems leverage both user-user (u-u) social relations and user-item (u-i) collaborative interactions to improve recommendation quality. Despite their effectiveness, existing models often struggle with task-irrelevant information and misalignment between social and collaborative signals and the downstream recommendation task, leading to suboptimal performance. To address these limitations, we propose a novel framework for Effective and Consistent Information Extraction for Social Recommendation (ECSR). Our approach focuses on two key modules: (1) a task-irrelevant information discarding module that filters out noisy signals from both social relations and user-item interactions, and (2) a task-relevant information alignment module that captures both shared and view-specific task-relevant information, ensuring alignment with the recommendation objective. By integrating them into a unified form, our method extracts minimal and sufficient statistics, which significantly enhance the model's ability to predict user preferences. We validate ECSR on three real-world social recommendation datasets, demonstrating that it consistently outperforms state-of-the-art baselines.

Designing effective negative sampling strategies is crucial for training Multi-Modal Recommendation (MMRec) models, as it helps address the issues of sparse user-item interactions and facilitates the learning of high-dimensional modality features. However, most existing methods randomly sample non-interacted items as negative ones, which frequently result in easy negatives. They limit the model's ability to accurately capture user preferences. In this paper, we propose to Generate Difficulty-aware Negative Samples via conditional diffusion for MMRec (denoted as GDNSM). Leveraging the rich semantic and contextual information from multi-modal features, our method generates hard negative samples with varying difficulty levels, tailored to user preferences. They force the model to learn finer-grained distinctions between positive and negative samples, enhancing its ability to inferring user preferences. To avoid unstable training, we design a dynamic difficulty scheduling mechanism that schedules the negative samples from easy to hard for model training, ensuring both stability and effectiveness. Extensive experiments on three real-world datasets demonstrate that the effectiveness of our models.

The integration of social information into recommender systems (RSs) has gained significant popularity for enhancing recommendation performance and user experience. However, this practice introduces substantial privacy risks, particularly concerning the leakage of sensitive social relationships. While prior research has primarily focused on user-level and interaction-level privacy risks, the social relation-level privacy risks remain largely unexplored. To fill this gap, we investigate social privacy risks through membership inference attacks (MIA) and propose a Social relation-level MIA (SMIA) framework. Two key challenges arise: (1) the adversary can only access the recommended item IDs, which provide indirect and limited information about social relationships, and (2) extracting socially relevant preferences from recommendation results is inherently difficult. To tackle the first challenge, we leverage shadow models to transform sparse item IDs into dense features, enabling adversaries to effectively utilize recommendation outputs. For the second challenge, SMIA employs a dual-branch learning approach that disentangles social and behavioral preferences. Therefore, we can extract socially relevant signals from the disentangled preferences.Extensive experiments on real-world datasets demonstrate that both social and general RSs are highly vulnerable to such attacks, highlighting the urgent need for robust privacy protection mechanisms. To defend against these attacks, we introduce a Socially Adversarial Learning (SAL) defense mechanism that selectively obscures sensitive social information in user representations during training, effectively reducing privacy leakage. We further evaluate the effectiveness of our defense and discuss future directions for developing privacy-preserving mechanisms in social RSs.

User cold-start recommendation presents a significant challenge for recommender systems, affecting their overall effectiveness. Meta-learning-based methods have been introduced to address this issue. These methods treat the user cold-start recommendation problem as a few-shot learning task, where each user represents a unique task. The objective is to acquire shared initialization parameters that can be effectively applied across all cold-start users. Subsequently, these shared parameters are fine-tuned into personalized parameters using individual interaction data. Recent studies argue that shared parameters are unsuitable for all users with an implicit grouping distribution of user preference. Therefore, they propose adaptive-initialization-based methods, which first differentiate tasks based on user preferences and then generate task-adaptive initialization parameters using task representations. However, both the meta-learning and adaptive-initialization-based manners ignore discovering the adaptive capability of update strategies in the process of transferring initialization parameters to personalized parameters. Instead, they rely on task-shared optimization strategies, leading the model to fall into an overfitting or underfitting situation. In response to this, we propose a dual-adaptive update strategies-enhanced meta-optimization framework (DAUS) for user cold-start recommendation. First, we integrate dual-adaptive update strategies to enhance the adaptive capability of transferring initialization parameters. This involves incorporating both task-adaptive optimization hyperparameters and objectives. Second, we design a multifaceted task encoder , which can provide diverse task information to differentiate between tasks, including explicit task features (task relevance, training signals) and other implicit task information. Extensive experiments based on three real-world datasets demonstrate that our DAUS outperforms the state-of-the-art methods. The source code is available at https://github.com/XuHao-bit/DAUS .

Crowdsourcing has become a popular paradigm for collecting large-scale labeled datasets by leveraging numerous annotators. However, these annotators often provide noisy labels due to varying expertise. Truth inference aims to infer accurate consensus labels from noisy crowdsourced annotations. Existing approaches rely heavily on hand-engineered assumptions or ground truth data, limiting their applicability. To address this, we propose GOVERN, a graph contrastive learning framework for truth inference without such external supervision. GOVERN employs a novel graph data augmentation strategy to generate views capturing worker coordination patterns. A contrastive objective then encourages invariant representations across views, enabling the discovery of features related to the hidden consensus. Further, a label correction method based on k-nearest neighbors refines noisy pseudo-labels to supervise model training. Comprehensive experiments on 9 real-world datasets demonstrate that GOVERN outperforms state-of-the-art truth inference techniques.

Graph-based social recommendation improves the prediction accuracy of recommendation by leveraging high-order neighboring information contained in social relations. However, most of them ignore the problem that social relations can be noisy for recommendation. Several studies attempt to tackle this problem by performing social graph denoising, but they suffer from 1) adaptability issues for other graph-based social recommendation models and 2) insufficiency issues for user social representation learning. To address the limitations, we propose a model-agnostic graph denoising module (denoted as MADM) which works as a plug-and-play module to provide refined social structure for base models. Meanwhile, to propel user social representations to be minimal and sufficient for recommendation, MADM further employs mutual information maximization (MIM) between user social representations and the interaction graph and realizes two ways of MIM: contrastive learning and forward predictive learning. We provide theoretical insights and guarantees from the perspectives of Information Theory and Multi-view Learning to explain its rationality. Extensive experiments on three real-world datasets demonstrate the effectiveness of MADM.

Information networks generally exhibit three characteristics, namely dynamicity, heterogeneity, and node attribute diversity. However, most existing network embedding approaches only consider two of the three when embedding each node into low-dimensional space. Adding to such an existing approach a technique of processing the remaining characteristic can easily cause incompatibility. One solution to process the three characteristics together is to treat the dynamic heterogeneous attributed network (DHAN) as a temporal sequence of heterogeneous attributed network (HAN) snapshots. For example, existing graph convolutional networks (GCNs)-based DHAN embedding approaches embed the HAN snapshots to get static representations offline, and then dynamically capture temporal dependencies between adjacent snapshots online to maintain fresh representations of the DHAN. However, those approaches encounter the convergence problem when stacking multiple convolutional layers to capture more topological information. Some other existing approaches dynamically update the representations of HAN snapshots online, neglecting the efficiency requirement of online scenarios and the temporal dependencies between snapshots. To address the two issues, we propose a new framework called Dynamic Heterogeneous Attributed Network Embedding (DHANE), consisting of a static model MGAT and a dynamic model NICE. MGAT captures more topological information while maintaining GCN convergence by performing metagraph-based attention in each convolutional layer. NICE preserves network freshness while reducing the computational load of the update by only examining network changes and updating their embedding representations. Extensive experiments show that DHANE achieves up to 27× speedup and 9.1-26.4% higher accuracy on several real dynamic heterogeneous attributed networks for online classification.

Sequential recommendation is a critical part of the flourishing online applications by suggesting appealing items on users’ next interactions, where global dependencies among items have proven to be indispensable for enhancing the quality of item representations toward a better understanding of user dynamic preferences. Existing methods rely on pre-defined graphs with shallow Graph Neural Networks to capture such necessary dependencies due to the constraint of the over-smoothing problem. However, this graph representation learning paradigm makes them difficult to satisfy the original expectation because of noisy graph structures and the limited ability of shallow architectures for modeling high-order relations. In this paper, we propose a novel Graph Diffusion Representation-enhanced Attention Network for sequential recommendation, which explores the construction of deeper networks by utilizing graph diffusion on adaptive graph structures for generating expressive item representations. Specifically, we design an adaptive graph generation strategy via leveraging similarity learning between item embeddings, automatically optimizing the input graph topology under the guidance of downstream recommendation tasks. Afterward, we propose a novel graph diffusion paradigm with robustness to over-smoothing, which enriches the learned item representations with sufficient global dependencies for attention-based sequential modeling. Moreover, extensive experiments demonstrate the effectiveness of our approach over state-of-the-art baselines.

Deep learning-based recommender systems have achieved remarkable success in recent years. However, these methods usually heavily rely on labeled data (i.e., user-item interactions), suffering from problems such as data sparsity and cold-start. Self-supervised learning, an emerging paradigm that extracts information from unlabeled data, provides insights into addressing these problems. Specifically, contrastive self-supervised learning, due to its flexibility and promising performance, has attracted considerable interest and recently become a dominant branch in self-supervised learning-based recommendation methods. In this survey, we provide an up-to-date and comprehensive review of current contrastive self-supervised learning-based recommendation methods. Firstly, we propose a unified framework for these methods. We then introduce a taxonomy based on the key components of the framework, including view generation strategy, contrastive task, and contrastive objective. For each component, we provide detailed descriptions and discussions to guide the choice of the appropriate method. Finally, we outline open issues and promising directions for future research.

Review-based recommender systems explore semantic aspects of users’ preferences by incorporating user-generated reviews into rating-based models. Recent works have demonstrated the potential of review information to improve the recommendation capacity. However, most existing studies rely on optimizing review-based representation learning part, thus failing to explicitly capture the fine-grained semantic aspects, and also ignoring the intrinsic correlation between ratings and reviews. To address these problems, we propose a multi-aspect graph contrastive learning framework, named MAGCL, with three distinctive designs: (i) a multi-aspect representation learning module, which projects semantic relations to different subspaces by decoupling review information, and then obtains high-order decoupled representations in each aspect via graph encoder. (ii) the contrastive learning module performs graph contrastive learning to capture the correlation between rating and review patterns, which utilize unlabeled data to generate self-supervised signals and, in turn, relieve the data sparsity problem of supervision signals. (iii) the multi-task learning module conducts joint training to learn high-order structure-aware yet self-discriminative node representations by combining recommendation task and self-supervised task, which helps alleviate the over-smoothing problem. Extensive experiments are conducted on four real-world review datasets and the results show the superiority of the proposed framework MAGCL compared with several state of the arts. We also provide further analysis on multi-aspect representations and graph contrastive learning to verify the advantage of proposed framework.

Cross-domain recommendation (CDR), which leverages information collected from other domains, has been empirically demonstrated to effectively alleviate data sparsity and cold-start problems encountered in traditional recommendation systems. However, current CDR methods, including those considering time information, do not jointly model the general and current interests within and across domains, which is pivotal for accurately predicting users’ future interactions. In this article, we propose a Contrastive learning-enhanced Multi-View interest learning model (CMVCDR) for cross-domain sequential recommendation. Specifically, we design a static view and a sequential view to model uses’ general interests and current interests, respectively. We divide a user’s general interest representation into a domain-invariant part and a domain-specific part. A cross-domain contrastive learning objective is introduced to impose constraints for optimizing these representations. In the sequential view, we first devise an attention mechanism guided by users’ domain-invariant interest representations to distill cross-domain knowledge pertaining to domain-invariant factors while reducing noise from irrelevant factors. We further design a domain-specific interest-guided temporal information aggregation mechanism to generate users’ current interest representations. Extensive experiments demonstrate the effectiveness of our proposed model compared with state-of-the-art methods.

User cold-start recommendation is one of the most challenging problems that limit the effectiveness of recommender systems. Meta-learning-based methods are introduced to address this problem by learning initialization parameters for cold-start tasks. Recent studies attempt to enhance the initialization methods. They first represent each task by the cold-start user and interacted items. Then they distinguish tasks based on the task relevance to learn adaptive initialization. However, this manner is based on the assumption that user preferences can be reflected by the interacted items saliently, which is not always true in reality. In addition, we argue that previous approaches suffer from their adaptive framework (e.g., adaptive initialization), which reduces the adaptability in the process of transferring meta-knowledge to personalized RSs. In response to the issues, we propose a task-difficulty-aware meta-learning with adaptive update strategies (TDAS) for user cold-start recommendation. First, we design a task difficulty encoder, which can represent user preference salience, task relevance, and other task characteristics by modeling task difficulty information. Second, we adopt a novel framework with task-adaptive local update strategies by optimizing the initialization parameters with task-adaptive per-step and per-layer hyperparameters. Extensive experiments based on three real-world datasets demonstrate that our TDAS outperforms the state-of-the-art methods. The source code is available at https://github.com/XuHao-bit/TDAS.

The issue of user cold-start poses a long-standing challenge to recommendation systems, due to the scarce interactions of new users. Recently, meta-learning based studies treat each cold-start user as a user-specific few-shot task and then derive meta-knowledge about fast model adaptation across training users. However, existing solutions mostly do not clearly distinguish the concept of new users and the concept of novel preferences, leading to over-reliance on meta-learning based adaptability to novel patterns. In addition, we also argue that the existing meta-training task construction inherently suffers from the memorization overfitting issue, which inevitably hinders meta-generalization to new users. In response to the aforementioned issues, we propose a preference learning decoupling framework, which is enhanced with meta-augmentation (PDMA), for user cold-start recommendation. To rescue the meta-learning from unnecessary adaptation to common patterns, our framework decouples preference learning for a cold-start user into two complementary aspects: common preference transfer, and novel preference adaptation. To handle the memorization overfitting issue, we further propose to augment meta-training users by injecting attribute-based noises, to achieve mutually-exclusive tasks. Extensive experiments on benchmark datasets demonstrate that our framework achieves superior performance improvements against state-of-the-art methods. We also show that our proposed framework is effective in alleviating memorization overfitting.

Next Point-of-Interest (POI) recommendation is an essential part of the flourishing location-based applications, where the demands of users are not only conditioned by their recent check-in behaviors but also by the critical influence stemming from geographical dependencies among POIs. Existing methods leverage Graph Neural Networks with the aid of pre-defined POI graphs to capture such indispensable correlations for modeling user preferences, assuming that the appropriate geographical dependencies among POIs could be pre-determined. However, the pre-defined graph structures are always far from the optimal graph topology due to noise and adaptability issues, which may decrease the expressivity of learned POI representations as well as the credibility of modeling user preferences. In this paper, we propose a novel Adaptive Graph Representation-enhanced Attention Network (AGRAN) for next POI recommendation, which explores the utilization of graph structure learning to replace the pre-defined static graphs for learning more expressive representations of POIs. In particular, we develop an adaptive POI graph matrix and learn it via similarity learning with POI embeddings, automatically capturing the underlying geographical dependencies for representation learning. Afterward, we incorporate the learned representations of POIs and personalized spatial-temporal information with an extension to the self-attention mechanism for capturing dynamic user preferences. Extensive experiments conducted on two real-world datasets validate the superior performance of our proposed method over state-of-the-art baselines.

Graph Convolutional Networks (GCNs) have been widely used for collaborative filtering, due to their effectiveness in exploiting high-order collaborative signals. However, two issues have not been well addressed by existing studies. First, usually only one kind of information is utilized, i.e., user preference in user-item graphs or item dependency in item-item graphs. Second, they usually adopt static graphs, which cannot retain the temporal evolution of the information. These can limit the recommendation quality. To address these limitations, we propose to mine three kinds of information (user preference, item dependency, and user behavior similarity) and their temporal evolution by constructing multiple discrete dynamic heterogeneous graphs (i.e., a user-item dynamic graph, an item-item dynamic graph, and a user-subseq dynamic graph) from interaction data. A novel network (PDGCN) is proposed to learn the representations of users and items in these dynamic graphs. Moreover, we designed a structural neighbor aggregation module with novel pooling and convolution operations to aggregate the features of structural neighbors. We also design a temporal neighbor aggregation module based on self-attention mechanism to aggregate the features of temporal neighbors. We conduct extensive experiments on four real-world datasets. The results indicate that our approach outperforms several competing methods in terms of Hit Ratio (HR) and Normalized Discounted Cumulative Gain (NDCG). Dynamic graphs are also shown to be effective in improving recommendation performance.

Textual reviews contain rich semantic information that is useful for making better recommendation, as such semantic information may indicate more fine-grained preferences of users. Recent efforts make considerable improvement on recommendation by integrating textual reviews in rating-based recommendations. However, there still exist major challenges on integrating textual reviews for recommendation. On the one hand, most existing works focus on learning a single representation from reviews but ignoring complex relations between users (or items) and reviews, which may fail to capture user preferences and item attributes together. On the other hand, these works independently learn latent representations from ratings and reviews while omitting correlations between rating-based features and review-based features, which may harm recommendation performance. In this article, we capture the aspect-aware relations by constructing heterogeneous graphs from reviews. Furthermore, we propose a new recommendation model, namely AHOR, to jointly distill rating-based features and review-based features, which are derived from ratings and reviews, respectively. To explore the multi-hop connectivity information between users, items, and aspects, a novel graph neural network is introduced to learn aspect-aware high-order representations. Experiments based on public datasets show that our approach outperforms state-of-the-art methods. We also provide detailed analysis on the high-order signals and the aspect importance to show the interpretability of our proposed model.

User cold-start scenarios pose great challenges to recommendation systems in accurately capturing user preferences with sparse interaction records. Besides incorporating auxiliary information to enrich user/item representations, recent studies under the schema of meta-learning focus on quickly adapting personalized recommendation models based on cold-start users’ scarce interactions. The majority of meta-learning based recommendation methods follow a bi-level optimization paradigm and learn globally shared initialization across all cold-start recommendation tasks. In addition, to further facilitate the ability of fast adaptation, existing methods have made efforts to tailor task-specific prior knowledge by identifying the individual characteristics of each task. However, we argue that multi-view commonalities between existing users and cold-start users are also essential for precisely distinguishing new tasks, but not comprehensively modeled in previous studies. In this article, we propose a multifaceted relation-aware meta-learning approach namely MeCM for user cold-start recommendation, which enhances task-adaptive initialization customization by extracting multiple views of task relevance. We design a dual customization framework consisting of two successive phases including cluster-level customization and task-level customization. Specifically, MeCM first extracts multifaceted semantic relations between tasks and refines task commonalities into task clusters maintained with memory networks (MNs). Globally learned fast weights corresponding to task clusters are queried to perform cluster-level customization. Then task-level customization is triggered based on contextual information of the target task via interaction-wise encoding. Extensive experiments on real-world datasets demonstrate the superior performance of our model over state-of-the-art meta-learning-based recommendation methods.

Traditional recommendation systems are faced with two long-standing obstacles, namely data sparsity and cold-start problems, which promote the emergence and development of Cross-Domain Recommendation (CDR). The core idea of CDR is to leverage information collected from other domains to alleviate the two problems in one domain. Since the early 2010s, many efforts have been engaged for cross-domain recommendation. Recently, with the development of deep learning and neural networks, a large number of methods have emerged. However, there is a limited number of systematic surveys on CDR, especially regarding the latest proposed methods as well as the recommendation scenarios and recommendation tasks they address. In this survey article, we first proposed a two-level taxonomy of cross-domain recommendation that classifies different recommendation scenarios and recommendation tasks. We then introduce and summarize existing cross-domain recommendation approaches under different recommendation scenarios in a structured manner. We also organize datasets commonly used. We conclude this survey by providing several potential research directions about this field.

Next Point-of-Interest (POI) recommendation plays a critical role in many location-based applications as it provides personalized suggestions on attractive destinations for users. Since users' next movement is highly related to the historical visits, sequential methods such as recurrent neural networks are widely used in this task for modeling check-in behaviors. However, existing methods mainly focus on modeling the sequential regularity of check-in sequences but pay little attention to the intrinsic characteristics of POIs, neglecting the entanglement of the diverse influence stemming from different aspects of POIs. In this paper, we propose a novel Disentangled Representation-enhanced Attention Network (DRAN) for next POI recommendation, which leverages the disentangled representations to explicitly model different aspects and corresponding influence for representing a POI more precisely. Specifically, we first design a propagation rule to learn graph-based disentangled representations by refining two types of POI relation graphs, making full use of the distance-based and transition-based influence for representation learning. Then, we extend the attention architecture to aggregate personalized spatio-temporal information for modeling dynamic user preferences on the next timestamp, while maintaining the different components of disentangled representations independent. Extensive experiments on two real-world datasets demonstrate the superior performance of our model to state-of-the-art approaches. Further studies confirm the effectiveness of DRAN in representation disentanglement.

Prediction tasks about students have practical significance for both student and college. Making multiple predictions about students is an important part of a smart campus. For instance, predicting whether a student will fail to graduate can alert the student affairs office to take predictive measures to help the student improve his/her academic performance. With the development of information technology in colleges, we can collect digital footprints that encode heterogeneous behaviors continuously. In this article, we focus on modeling heterogeneous behaviors and making multiple predictions together, since some prediction tasks are related and learning the model for a specific task may have the data sparsity problem. To this end, we propose a variant of Long-Short Term Memory (LSTM) and a soft-attention mechanism. The proposed LSTM is able to learn the student profile-aware representation from heterogeneous behavior sequences. The proposed soft-attention mechanism can dynamically learn different importance degrees of different days for every student. In this way, heterogeneous behaviors can be well modeled. In order to model interactions among multiple prediction tasks, we propose a co-attention mechanism based unit. With the help of the stacked units, we can explicitly control the knowledge transfer among multiple tasks. We design three motivating behavior prediction tasks based on a real-world dataset collected from a college. Qualitative and quantitative experiments on the three prediction tasks have demonstrated the effectiveness of our model.

The task of next Point-of-Interest (POI) recommendation aims at recommending a list of POIs for a user to visit at the next timestamp based on his/her previous interactions, which is valuable for both location-based service providers and users. Recent state-of-the-art studies mainly employ recurrent neural network (RNN) based methods to model user check-in behaviors according to user’s historical check-in sequences. However, most of the existing RNN-based methods merely capture geographical influences depending on physical distance or successive relation among POIs. They are insufficient to capture the high-order complex geographical influences among POI networks, which are essential for estimating user preferences. To address this limitation, we propose a novel Graph-based Spatial Dependency modeling (GSD) module, which focuses on explicitly modeling complex geographical influences by leveraging graph embedding. GSD captures two types of geographical influences, i.e., distance-based and transition-based influences from designed POI semantic graphs. Additionally, we propose a novel Graph-enhanced Spatial-Temporal network (GSTN), which incorporates user spatial and temporal dependencies for next POI recommendation. Specifically, GSTN consists of a Long Short-Term Memory (LSTM) network for user-specific temporal dependencies modeling and GSD for user spatial dependencies learning. Finally, we evaluate the proposed model using three real-world datasets. Extensive experiments demonstrate the effectiveness of GSD in capturing various geographical influences and the improvement of GSTN over state-of-the-art methods.

Non-parallel text style transfer aims to rephrase a sentence with another style while reserving its content relying on non-parallel data. Most existing methods can be divided into two groups: 1) separating content and style of the input text and 2) directly modeling the style transfer process. To the best of our knowledge, all these existing works lack fine-grained supervisory signals during training, which leads to difficulty in achieving a good balance between content preservation and style satisfaction. However, the study on supervisors which could provide fine-grained supervisory signals for training transfer models has received relatively less attention. Thus, we propose a self-attentional discriminator and a training strategy for training an attentional transfer model by leveraging the fine-grained supervisory signals from the proposed discriminator. Specifically, our discriminator provides token-wise style/content weights by performing self-attention between the sentence vector and the token embeddings, which forms a shortcut in back-propagation leading to more accurate gradients. The style/content weights also pose a better content alignment constraint and improve the interpretability of the training procedure by identifying stylized tokens. The training of our transfer model is end-to-end via Gumbel-Softmax with the pre-trained discriminator. Experiments on two datasets with automatic and human evaluations as well as theoretical and empirical analysis demonstrate the effectiveness of our method.1

Sequential recommendation which aims to predict a user's next interaction based on his/her previous behaviors, has attracted great attention. Recent studies mainly employ deep recurrent neural networks or self-attention networks to capture dynamic user preferences. However, existing methods merely focus on modeling users' clear interests in interacted items. We argue that for an interaction, the user may also have ambiguous interests in items that are semantically related to the interacted one. For comprehensively capturing user preferences, it is beneficial to discover potential interests from historical interactions at a broader itemset level. Therefore, in this paper, we propose a knowledge graph enhanced sequential recommendation model namely KGIE, which focuses on enhancing user interest modeling with knowledge-enriched itemsets by incorporating the knowledge graph. Specifically, in addition to item-level interest modeling with interacted items, we further construct knowledge-enriched itemsets that are extracted via high-order knowledge associations with the interacted items. For capturing personalized itemset-level interests, we design an attentive aggregation unit to combine item embeddings considering both inherent and contextual personalization signals. Furthermore, to balance the contributions of both two levels of interest modeling, we adaptively learn high-level preference representations with a gating fusion unit. Extensive experiments on three real-world datasets demonstrate the superior performance beyond state-of-the-art methods and recommendation interpretability of our model.

Air pollution is an important environmental issue of increasing concern, which impacts human health. Accurate air quality prediction is crucial for avoiding people suffering from serious air pollution. Most of the prior works focus on capturing the temporal trend of air quality for each monitoring station. Recent deep learning based methods also model spatial dependencies among neighboring stations. However, we observe that besides geospatially adjacent stations, the stations which share similar functionalities or consistent temporal patterns could also have strong dependencies. In this paper, we propose an Attentive Temporal Graph Convolutional Network (ATGCN) to model diverse inter-station relationships for air quality prediction of citywide stations. Specifically, we first encode three types of relationships among stations including spatial adjacency, functional similarity, and temporal pattern similarity into graphs. Then we design parallel encoding modules, which respectively incorporate attentive graph convolution operations into the Gated Recurrent Units (GRUs) to iteratively aggregate features from related stations with different graphs. Furthermore, augmented with an attention-based fusion unit, decoding modules with a similar structure to the encoding modules are designed to generate multi-step predictions for all stations. The experiments on two real-world datasets demonstrate the superior performance of our model beyond state-of-the-art methods.

Among various recommendation methods, latent factor models are usually considered to be state-of-the-art techniques, which aim to learn user and item embeddings for predicting user-item preferences. When applying latent factor models to the recommendation with implicit feedback, the quality of embeddings always suffers from inadequate positive feedback and noisy negative feedback. Inspired by the idea of NSVD that represents users based on their interacted items, this article proposes a dual-embedding based deep latent factor method for recommendation with implicit feedback. In addition to learning a primitive embedding for a user (resp. item), we represent each user (resp. item) with an additional embedding from the perspective of the interacted items (resp. users) and propose attentive neural methods to discriminate the importance of interacted users/items for dual-embedding learning. We design two dual-embedding based deep latent factor models, DELF and DESEQ, for pure collaborative filtering and temporal collaborative filtering (i.e., sequential recommendation), respectively. The novel attempt of the proposed models is to capture each user-item interaction with four deep representations that are subtly fused for preference prediction. We conducted extensive experiments on four real-world datasets. The results verify the effectiveness of user/item dual embeddings and the superior performance of our methods on item recommendation.

Crowd flow prediction is a vital problem for an intelligent transportation system construction in a smart city. It plays a crucial role in traffic management and behavioral analysis, thus it has raised great attention from many researchers. However, predicting crowd flows timely and accurately is a challenging task that is affected by many complex factors such as the dependencies of adjacent regions or recent crowd flows. Existing models mainly focus on capturing such dependencies in spatial or temporal domains and fail to model relations between crowd flows of distant regions. We notice that each region has a relatively fixed daily flow and some regions (even very far away from each other) may share similar flow patterns which show strong correlations among them. In this article, we propose a novel model named Double-Encoder which follows a general encoder–decoder framework for multi-step citywide crowd flow prediction. The model consists of two encoder modules named ST-Encoder and FR-Encoder to model spatial-temporal dependencies and daily flow correlations, respectively. We conduct extensive experiments on two real-world datasets to evaluate the performance of the proposed model and show that our model consistently outperforms state-of-the-art methods.

For the emerging mobility-on-demand services, it is of great significance to predict passenger demands based on historical mobility trips towards better vehicle distribution. Prior works have focused on predicting next-step passenger demands at selected locations or hotspots. However, we argue that multi-step citywide passenger demands encapsulate both time-varying demand trends and global statuses, and hence are more beneficial to avoiding demand-service mismatching and developing effective vehicle distribution/scheduling strategies. Furthermore, we find that adaptations of single-step methods are unable to achieve robust prediction with high accuracy for further steps. In this paper, we propose an end-to-end deep neural network model to the prediction task. We employ an encoder-decoder framework based on convolutional and ConvLSTM units to identify complex features that capture spatiotemporal influence and pickup-dropoff interactions on citywide passenger demands. We introduce a multi-level attention model (global attention and temporal attention) to emphasize the effects of latent citywide mobility regularities and capture relevant temporal dependencies. We evaluate our proposed method using real-world mobility trips (taxis and bikes) and the experimental results show that our method achieves higher prediction accuracy than the state-of-the-art approaches.

Purchase intentions have a great impact on future purchases and thus can be exploited for making recommendations. However, purchase intentions are typically complex and may change from time to time. Through empirical study with two e-commerce datasets, we observe that behaviors of multiple types can indicate user intentions and a user may have multiple coexisting category-level intentions that evolve over time. In this article, we propose a novel Intention-Aware Recommender System (IARS) which consists of four components for mining such complex intentions from user behaviors of multiple types. In the first component, we utilize several Recurrent Neural Networks (RNNs) and an attention layer to model diverse user intentions simultaneously and design two kinds of Multi-behavior GRU (MGRU) cells to deal with heterogeneous behaviors. To reveal user intentions, we carefully design three tasks that share representations from MGRUs. The next-item recommendation is the main task and leverages attention to select user intentions according to candidate items. The remaining two (item prediction and sequence comparison) are auxiliary tasks and can reveal user intentions. Extensive experiments on the two real-world datasets demonstrate the effectiveness of our models compared with several state-of-the-art recommendation methods in terms of hit ratio and NDCG.

Prediction tasks about students such as predicting students' academic performances have practical real-world significance at both the student level and the college level. With the rapid construction of smart campuses, colleges not only offer residence and academic programs but also record students' daily life. The digital footprints provide an opportunity to offer better solutions for prediction tasks. In this paper, we aim to propose a general deep neural network which can jointly model student heterogeneous daily behaviors generated from digital footprints and social influence to deal with prediction tasks. To this end, we design a variant of LSTM and a novel attention mechanism to model the daily behavior sequence. The proposed LSTM is able to consider context information (e.g., weather conditions) while modeling the daily behavior sequence. The proposed attention mechanism can dynamically learn the different importance degrees of different days for every student. Based on behavior information, we propose an unsupervised way to construct a social network to model social influence. Moreover, we design a residual network based decoder to model the complex interactions between the features and get the predicted values such as future academic performances. Qualitative and quantitative experiments on two real-world datasets collected from a college have demonstrated the effectiveness of our model.

Business location selection is crucial to the success of businesses. Traditional approaches like manual survey investigate multiple factors, such as foot traffic, neighborhood structure, and available workforce, which are typically hard to measure. In this article, we propose to explore both satellite data (e.g., satellite images and nighttime light data) and urban data for business location selection tasks of various businesses. We extract discriminative features from the two kinds of data and perform empirical analysis to evaluate the correlation between extracted features and the business popularity of locations. A novel neural network approach named R 2 Net is proposed to learn deep interactions among features and predict the business popularity of locations. The proposed approach is trained with a regression-and-ranking combined loss function to preserve accurate popularity estimation and the ranking order of locations simultaneously. To support the location selection for multiple businesses, we propose an approach named AR 2 Net with three attention modules, which enable the approach to focus on different latent features according to business types. Comprehensive experiments on a real-world dataset demonstrate that the satellite features are effective and our models outperform the state-of-the-art methods in terms of four metrics.

The increasing amount of trajectory data facilitates a wide spectrum of practical applications in which large numbers of trajectory range and similarity queries are issued continuously. This calls for high-throughput trajectory query processing. Traditional in-memory databases lack considerations of the unique features of trajectories, while specialized trajectory query processing systems are typically designed for only one type of trajectory queries. This paper introduces GAT, a unified GPU-accelerated framework to process batch trajectory queries with the objective of high throughput. GAT follows the filtering-and-verification paradigm where we develop a novel index GTIDX for effectively filtering invalid trajectories on the CPU, and exploit the massive parallelism of the GPU for verification. To optimize the performance of GAT, we first greedily partition batch queries to reduce the amortized query processing latency. We then apply the Morton-based encoding method to coalesce data access requests from the GPU cores, and maintain a hash table to avoid redundant data transfer between CPU and GPU. To achieve load balance, we group size-varying cells into balanced blocks with similar numbers of trajectory points. Extensive experiments have been conducted over real-life trajectory datasets. The results show that GAT is efficient, scalable, and achieves high throughput with acceptable indexing cost.

Cooperation among the traffic signals enables vehicles to move through intersections more quickly. Conventional transportation approaches implement cooperation by pre-calculating the offsets between two intersections. Such pre-calculated offsets are not suitable for dynamic traffic environments. To enable cooperation of traffic signals, in this paper, we propose a model, CoLight, which uses graph attentional networks to facilitate communication. Specifically, for a target intersection in a network, CoLight can not only incorporate the temporal and spatial influences of neighboring intersections to the target intersection, but also build up index-free modeling of neighboring intersections. To the best of our knowledge, we are the first to use graph attentional networks in the setting of reinforcement learning for traffic signal control and to conduct experiments on the large-scale road network with hundreds of traffic signals. In experiments, we demonstrate that by learning the communication, the proposed model can achieve superior performance against the state-of-the-art methods.

Latent factor models (LFMs) such as matrix factorization have achieved the state-of-the-art performance among various collaborative filtering approaches for recommendation. Despite the high recommendation accuracy of LFMs, a critical issue to be resolved is their lack of interpretability. Extensive efforts have been devoted to interpreting the prediction results of LFMs. However, they either rely on auxiliary information which may not be available in practice, or sacrifice recommendation accuracy for interpretability. Influence functions, stemming from robust statistics, have been developed to understand the effect of training points on the predictions of black-box models. Inspired by this, we propose a novel explanation method named FIA (Fast Influence Analysis) to understand the prediction of trained LFMs by tracing back to the training data with influence functions. We present how to employ influence functions to measure the impact of historical user-item interactions on the prediction results of LFMs and provide intuitive neighbor-style explanations based on the most influential interactions. Our proposed FIA exploits the characteristics of two important LFMs, matrix factorization and neural collaborative filtering, and is capable of accelerating the overall influence analysis process. We provide a detailed complexity analysis for FIA over LFMs and conduct extensive experiments to evaluate its performance using real-world datasets. The results demonstrate the effectiveness and efficiency of FIA, and the usefulness of the generated explanations for the recommendation results.

Air quality has gained much attention in recent years and is of great importance to protecting people’s health. Due to the influence of multiple factors, the limited air quality monitoring stations deployed in cities are unable to provide fine-grained air quality information. One cost-effective way is to infer air quality with records from existing monitoring stations. However, the severe data sparsity problem (e.g., only 0.2% data are known) leads to the failure of most inference methods. We observe that remote sensing data are of high quality and have a strong correlation with the air quality. Therefore, we propose to integrate remote sensing data and ubiquitous urban data for the air quality inference. But there are two main challenges, i.e., data heterogeneity and incompleteness of the remote sensing data. To address the challenges, we propose a two-stage approach. In the first stage, we infer and predict air quality conditions of some places leveraging the remote sensing data and meteorological data with two proposed ANN-based methods, respectively. This stage significantly alleviates the data sparsity problem. In the second stage, the records and estimated air quality data are put in a tensor. A tensor decomposition method is applied to complete the tensor. The features extracted from urban data are classified into the spatial features (i.e., road features and POI features) and the temporal features (i.e., meteorological features) as the constraints to further address the data sparsity problem. In addition, an iterative training framework is proposed to improve the inference performance. Experiments on a real-world dataset show that our approach outperforms state-of-the-art methods, such as U-Air.

The increasing amount of trajectory data facilitates a wide spectrum of practical applications. In many such applications, large numbers of trajectory range and similarity queries are issued continuously, which calls for high-throughput trajectory query processing. Traditional in-memory databases lack considerations of the unique features of trajectories, thus suffering from inferior performance. Existing trajectory query processing systems are typically designed for only one type of trajectory queries, i.e., either range or similarity query, but not for both. Inspired by the massive parallelism on GPUs, in this paper, we develop a GPU-accelerated framework, named GAT, to support both types of trajectory queries (i.e., both range and similarity queries) with high throughput. For similarity queries, we adopt the Edit Distance on Real sequence (EDR) as the similarity measure which is accurate and robust to noise in real-world trajectories. GAT employs a GPU-friendly index called GTIDX to effectively filter invalid trajectories for both range and similarity queries, and exploits the GPU to perform parallel verifications. To accelerate the verification process on the GPU, we apply the Morton-based encoding method to reorganize trajectory points and facilitate coalesced data accesses for individual point data in global memory, which reduces the global memory bandwidth requirement significantly. We also propose a technique of grouping size-varying cells into balanced blocks with similar numbers of trajectory points, to achieve load balancing among the Streaming Multiprocessors (SMs) of the GPU. We conduct extensive experiments to evaluate the performance of GAT using two real-life trajectory datasets. The results show that GAT is scalable and achieves high throughput with acceptable indexing cost.

With the prosperity of the location-based social networks, next Point-of-Interest (POI) recommendation has become an important service and received much attention in recent years. The next POI is dynamically determined by the mobility pattern and various contexts associated with user check-in sequence. However, exploring spatial-temporal mobility patterns and incorporating heterogeneous contextual factors for recommendation are challenging issues to be resolved. In this paper, we introduce a novel neural network model named TMCA (Temporal and Multi-level Context Attention) for next POI recommendation. Our model employs the LSTM-based encoder-decoder framework, which is able to automatically learn deep spatial-temporal representations for historical check-in activities and integrate multiple contextual factors using the embedding method in a unified manner. We further propose the temporal and multi-level context attention mechanisms to adaptively select relevant check-in activities and contextual factors for next POI preference prediction. Extensive experiments have been conducted using two real-world check-in datasets. The results verify (1) the superior performance of our proposed method in different evaluation metrics, compared with several state-of-the-art methods; and (2) the effectiveness of the temporal and multi-level context attention mechanisms on recommendation performance.

This paper studies the problem of time series forecasting. A time series is defined as a sequence of data points listed in time order. Many real-life time series data are driven by multiple latent components which occur at different frequencies. Existing solutions to time series forecasting fail to identify and discriminate these frequency-domain components. Inspired by the recent advent of signal processing and speech recognition techniques that decompose a time series signal into its time-frequency representation - a scalogram (or spectrogram), this paper proposes to explicitly disclose frequency-domain information from a univariate time series using wavelet transform, towards improving forecasting accuracy. Based on the transformed data, we leverage different neural networks to capture local time-frequency features and global long-term trend simultaneously. We further employ the attention mechanism to fuse local and global features in an effective manner. The experimental results on real time series show that our proposed approach achieves better performance than various baseline methods.

Dockless shared bikes, which aim at providing a more flexible and convenient solution to the first-and-last mile connection, come into China and expand to other countries at a very impressing speed. The expansion of shared bike business in new cities brings many challenges among which, the most critical one is the parking chaos caused by too many bikes yet insufficient demands. To allow possible actions to be taken in advance, this paper studies the problem of detecting parking hotspots in a new city where no dockless shared bike has been deployed. We propose to measure road hotness by bike density with the help of the Kernal Density Estimation. We extract useful features from multi-source urban data and introduce a novel domain adaption network for transferring hotspots knowledge learned from one city with shared bikes to a new city. The extensive experimental results demonstrate the effectiveness of our proposed approach compared with various baselines.

Recently, dockless shared bike services have achieved great success and reinvented bike sharing business in China. When expanding bike sharing business into a new city, most start-ups always wish to find out how to cover the whole city with a suitable bike distribution. In this paper, we study the problem of inferring bike distribution in new cities, which is challenging. As no dockless bikes are deployed in the new city, we propose to learn insights on bike distribution from cities populated with dockless bikes. We exploit multi-source data to identify important features that affect bike distributions and develop a novel inference model combining Factor Analysis and Convolutional Neural Network techniques. The extensive experiments on real-life datasets show that the proposed solution provides significantly more accurate inference results compared with competitive prediction methods.

Predicting passenger pickup/dropoff demands based on historical mobility trips has been of great importance towards better vehicle distribution for the emerging mobility-on-demand (MOD) services. Prior works focused on predicting next-step passenger demands at selected locations or hotspots. However, we argue that multi-step citywide passenger demands encapsulate both time-varying demand trends and global statuses, and hence are more beneficial to avoiding demand-service mismatching and developing effective vehicle distribution/scheduling strategies. In this paper, we propose an end-to-end deep neural network solution to the prediction task. We employ the encoder-decoder framework based on convolutional and ConvLSTM units to identify complex features that capture spatiotemporal influences and pickup-dropoff interactions on citywide passenger demands. A novel attention model is incorporated to emphasize the effects of latent citywide mobility regularities. We evaluate our proposed method using real-word mobility trips (taxis and bikes) and the experimental results show that our method achieves higher prediction accuracy than the adaptations of the state-of-the-art approaches.

Understanding air travel choice behavior of air passengers is of great significance for various purposes such as travel demand prediction and trip recommendation. Existing approaches based on surveys can only provide aggregate level air travel choice behavior of passengers and they fail to provide comprehensive information for personalized services. In this paper we focus on modeling individual level air travel choice behavior of passengers, which is valuable for recommendations and personalized services. We employ a probabilistic model to represent individual level air travel choice behavior based on a large dataset of historical booking records, leveraging several key factors, such as takeoff time, arrival time, elapsed time between reservation and takeoff, price, and seat class. However, each passenger has only a limited number of historical booking records, causing a serious data sparsity problem. To this end, we propose a mixed kernel density estimation (mix-KDE) approach for each passenger with a mixture model that combines probabilistic estimation of both regularity of the individual himself and social conformity of similar passengers. The proposed model is trained and evaluated via the expectation-maximization (EM) algorithm with a huge dataset of booking records of over 10 million air passengers from a popular online travel agency in China. Experimental results demonstrate that our mix-KDE approach outperforms the Gaussian mixture model (GMM) and the simple kernel density estimation in the presence of the sparsity issue.

With the growth of the economy, the air quality is becoming a serious issue, especially for those developing countries, such as China. Therefore, it is very important for the public and the government to access real-time air quality information. Unfortunately, the limited number of air quality monitoring stations is unable to provide fine-grained air quality information in a huge city, such as Beijing. One cost-effective approach for obtaining fine-grained air quality information is to infer air quality with those measured data at the monitoring stations. However, existing inference techniques have poor performance because of the extreme data sparsity problem (e.g., only 0.2% data are known). We observe that remote sensing has been a high-quality data source about urban dynamics. In this paper, we propose to integrate remote sensing data and ubiquitous urban data for air quality inference. There are two main challenges, i.e., data heterogeneity and incomplete remote sensing data. In response to the challenges, we propose a two-stage inference approach. In the first stage, we use the AOT remote sensing data and the meteorological data to infer the air quality values with an Artificial Neural Network (ANN). After this stage, we significantly reduce the percentage of empty cells in the tensor representing the spatio-temporal air quality values. In the second stage, we propose a tensor decomposition method to infer the complete set of air quality values. We use the spatial features (i.e., road features and POI features) and the temporal features (i.e., meteorological features) as the constraints in the tensor decomposition process. Experiments with real data sets show that our approach has profound performance advantage over the state-of-the-art methods, such as U-Air.

Nowadays most metro advertising systems schedule advertising slots on digital advertising screens to achieve the maximum exposure to passengers by exploring passenger demand models. However, our empirical results show that these passenger demand models experience uncertainty at fine temporal granularity (e.g., per min). As a result, for fine-grained advertisements (shorter than one minute), a scheduling based on these demand models cannot achieve the maximum advertisement exposure. To address this issue, we propose an online advertising approach, called EveryoneCounts, based on an uncertain passenger demand model. It combines coarse-grained statistical demand modeling and fine-grained Bayesian demand modeling by leveraging realtime card-swiping records along with both passenger mobility patterns and travel periods within metro systems. Based on this uncertain demand model, it schedules advertising time online based on robust receding horizon control to maximize the advertisement exposure. We evaluate the proposed approach based on an one-month sample from our 530 GB real-world metro fare dataset with 16 million cards. The results show that our approach provides a 61.5% lower traffic prediction error and 20% improvement on advertising efficiency on average.

The process of map matching takes a sequence of possibly noisy GPS coordinates from a vehicle trace and estimates the actual road positions---a crucial first step needed by many GPS applications. There has been a plethora of methods for map matching published, but most of them are evaluated on low-noise datasets obtained from a planned route. And comparisons with other methods are very limited. Based on our previous unifying framework used to catalog different mathematical formulas in many published methods, we evaluate representative algorithms using the low-noise dataset from the GIS Cup 2012 and a high-noise dataset collected from Shanghai downtown. Our experiments reveal that global max-weight and global geometrical map matching methods are the most accurate, but each has its weaknesses. We therefore propose a new map matching algorithm that integrates Fréchet distance with global weight optimization, which is more accurate across all sampling intervals.

This paper describes a point-polygon query program we submitted to the ACM SIGSPATIAL Cup 2013. Point-polygon topological relationship query is one of the core functions for commercial spatial databases, and also an active research topic in academia. Spatial indices are the key to achieve top performance. However, different datasets or query patterns require different indices for optimal performance. Based on the patterns of the training dataset, we build a hierarchy of indices, including polygon index, edge index, and interval index, which help find polygons near a point, calculate the distance from a point to a polygon, and determine whether a point is inside a polygon, respectively. Using the provided training dataset, these three indices reduce the computation time of "WITHIN n" query by 90%, 10%, and 50%, respectively. We build a large dataset with more than 1 million samples and 520 polygons by cloning and offsetting the training dataset 15 and 13 times, respectively. Our program finishes the "WITHIN 1000" query in only one second on a 4-core 3.3GHz Xeon Processor.

This paper describes a map matching program submitted to the ACM SIGSPATIAL Cup 2012. We first summarize existing map matching algorithms into three categories, and compare their performance thoroughly. In general, global max-weight methods using the Viterbi dynamic programming algorithm are the most accurate but the accuracy varies at different sampling intervals using different weight functions. Our submission selects a hybrid that improves upon the best two weight functions such that its accuracy is better than both and the performance is robust against varying sampling rates. In addition, we employ many optimization techniques to reduce the overall latency, as the scoring heavily emphasizes on speed. Using the training dataset with manually corrected ground truth, our Java-based program matched all 14,436 samples in 5 seconds on a dual-core 3.3 GHz iCore 3 processor, and achieved 98.9% accuracy.

We address the problem of inferring road maps from large-scale GPS traces that have relatively low resolution and sampling frequency. Unlike past published work that requires high-resolution traces with dense sampling, we focus on situations with coarse granularity data, such as that obtained from thousands of taxis in Shanghai, which transmit their location as seldom as once per minute. Such data sources can be made available inexpensively as byproducts of existing processes, rather than having to drive every road with high-quality GPS instrumentation just for map building - and having to re-drive roads for periodic updates. Although the challenges in using opportunistic probe data are significant, successful mining algorithms could potentially enable the creation of continuously updated maps at very low cost.