Current benchmarks evaluate the performance of RAG methods from various perspectives, they share a common assumption that user queries used for retrieval are error-free. However, in real-world interactions between users and LLMs, query entry errors are frequent. The impact of these errors on current RAG methods against such errors remains largely unexplored. To bridge this gap, we propose QE-RAG, the first robust RAG benchmark designed specifically to evaluate performance against query entry errors. We analyze the impact of these errors on LLM outputs and find that corrupted queries degrade model performance, which can be mitigated through query correction and training a robust retriever for retrieving relevant documents. Based on these insights, we propose a contrastive learning-based robust retriever training method and a retrieval-augmented query correction method. Extensive experiments reveal that: (1) state-of-the-art RAG methods including sequential, branching, and iterative methods, exhibit poor robustness to query entry errors; (2) our method enhances the robustness of RAG when handling query entry errors and it's compatible with existing RAG methods, further improving their robustness.

The remarkable text understanding and generation capabilities of large language models (LLMs) have revitalized the field of general recommendation based on implicit user feedback. Rather than deploying LLMs directly as recommendation models, a more flexible paradigm leverages their ability to interpret users' historical interactions and semantic contexts to extract structured profiles that characterize user preferences. These profiles can be further transformed into actionable high-dimensional representations, serving as powerful signals to augment and strengthen recommendation models. However, the mechanism by which such profiles enhance recommendation performance within the feature space remains insufficiently understood. Moreover, existing studies predominantly rely on nonlinear alignment and fusion strategies to incorporate these profiles, which often lead to semantic loss and fail to fully exploit their potential. To address these limitations, we revisit profiles from a retrieval perspective and propose a simple yet effective recommendation framework built upon distribution shaping (ProMax) in this paper. We begin by employing dense retrieval to uncover the collaborative relationships between user and item profiles within the feature space. Based on this insight, we introduce a dual distribution-reshaping process, in which the profile distribution acts as a guiding signal to steer the recommendation model toward learning user preferences for unseen items beyond the scope of observed interactions. We apply ProMax to four classic recommendation methods on three public datasets. The results indicate that ProMax substantially improves base model performance and outperforms existing LLM-based recommendation approaches.

Traffic prediction plays a pivotal role in contemporary web technologies, motivating various intelligent web services such as route planning and remote traffic management. Many recent proposals that target deep learning for traffic prediction solely leverage historical traffic observations to predict future ones. However, traffic prediction is always susceptible to different factors such as road networks and social events, exhibiting different modalities. Most existing methods focus on a single modality, failing to capture the comprehensive traffic patterns among various factors, resulting in sub-optimal performance. Web-sourced geo-images, e.g., satellite imagery, encompass comprehensive contextual information and offer an effective way to represent diverse modalities. To unleash the power of such geo-images, we propose VisionST, a Vision-augmented Spatial-Temporal Neural Network, which coordinates cross-modal traffic prediction with interactive geo-image encoding. To bolster resilience against highly intricate and overlapping traffic patterns, VisionST features a visual semantic extraction mechanism and a pattern-guided aggregation mechanism. The former extracts node-level visual tokens and node-to-node visual relation patterns from geo-referenced images. The latter generates relation patterns that encompass visual, spatial, and temporal aspects, constraining nodes to interact with these relation patterns for contextual information interaction. Extensive experiments on real large-scale datasets offer insight into the effectiveness of the proposed solutions, showing that VisionST consistently outperforms state-of-the-art baselines.

Time series anomaly detection aims to identify samples that deviate from a normal sample distribution in a time series, enabling various web-centric applications. Most existing approaches are static, targeting pre-defined types of anomalies. These methods thus fail to work well on streaming time series with changing data distributions and anomaly formats. To contend with such streaming time series and to accommodate memory constraints, we propose the first data-efficient streaming time series anomaly detection framework, called DESS. To accumulate historical knowledge, DESS includes a novel evolving proxy generation module to synthesize a small but informative proxy summarizing the historical data, facilitating data efficiency. Next, DESS employs an innovative heterogeneous temporal feature extraction module to explicitly capture correlations of multi-level time series semantics. Finally, DESS enables fast streaming anomaly detection by employing a parameter-efficient training scheme that only activates a subset of lightweight parameters while ensuring performance. Extensive experiments on real data offer insight into the effectiveness and efficiency of DESS, showing that it is able to outperform the best baselines by up to 17.53% while reducing the training time by up to 64.88%.

Spatio-temporal data proliferates in numerous real-world domains, such as transportation, weather, and energy. Spatio-temporal deep learning models aims to utilize useful patterns in such data to support tasks like prediction, imputation, and anomaly detection. However, previousone-to-onedeep learning models designed for specific tasks typically require separate training for each use case, leading to increased computational and storage costs. To address this issue,one-to-manyspatio-temporal foundation models have emerged, offering a unified framework capable of solving multiple spatio-temporal tasks. These foundation models achieve remarkable success by learning general knowledge with spatio-temporal data or transferring the general capabilities of pre-trained language models. While previous surveys have explored spatio-temporal data and methodologies separately, they have ignored a comprehensive examination of how foundation models are designed, selected, pre-trained, and adapted. As a result, the overall pipeline for spatio-temporal foundation models remains unclear. To bridge this gap, we innovatively provide an up-to-date review of previous spatio-temporal foundation models from the pipeline perspective. The pipeline begins with an introduction to different types of spatio-temporal data, followed by details of data preprocessing and embedding techniques. The pipeline then presents a novel data property taxonomy to divide existing methods according to data sources and dependencies, providing efficient and effective model design and selection for researchers. On this basis, we further illustrate the training objectives of primitive models, as well as the adaptation techniques of transferred models. Overall, our survey provides a clear and structured pipeline to understand the connection between core elements of spatio-temporal foundation models while guiding researchers to get started quickly. Additionally, we introduce emerging opportunities such as multi-objective training in the field of spatio-temporal foundation models, providing valuable insights for researchers and practitioners.

With the proliferation of GPS-equipped edge devices, huge trajectory data are generated and accumulated in various domains, driving numerous urban applications. However, due to the limited data acquisition capabilities of edge devices, many trajectories are often recorded at low sampling rates, reducing the effectiveness of these applications. To address this issue, we aim to recover high-sample-rate trajectories from low-sample-rate ones enhancing the usability of trajectory data. Recent approaches to trajectory recovery often assume centralized data storage, which can lead to catastrophic forgetting, where previously learned knowledge is entirely forgotten when new data arrives. This not only poses privacy risks but also degrades performance in decentralized settings where data streams into the system incrementally. To enable decentralized training and streaming trajectory recovery, we propose aLightweight incremental framework for federatedTrajectoryRecovery, called LightTR+, which is based on a client-server architecture. Given the limited processing capabilities of edge devices, LightTR+ includes a lightweight local trajectory embedding module that enhances computational efficiency without compromising feature extraction capabilities. To mitigate catastrophic forgetting, we propose an intra-domain knowledge distillation module. Additionally, LightTR+ features a meta-knowledge enhanced local-global training scheme, which reduces communication costs between the server and clients, further improving efficiency. Extensive experiments offer insight into the effectiveness and efficiency of LightTR+.

Velocity control in autonomous driving is an emerging technology that has achieved rapid progress over the last decade. However, existing velocity control studies ignore cascading disturbances in multi-lane scenarios and usually ignore the negative impact caused by harsh velocity decisions. To address these issues, we propose a reinforcement learning-based framework, called RISE (contRol velocIty for autonomouSvEhicle) to make velocity decisions for an autonomous vehicle in multi-lane traffic scenarios. To detect latent disturbances in the traffic flow, we propose a novel state encoder to learn the spatio-temporal correlation between different vehicles based on a well-designed impact graph. Afterward, we introduce an actor-critic paradigm to make velocity decisions with the aid of a hybrid reward function considering four optimization objectives: safety, efficiency, comfort, and impact. In particular, the impact term can penalize the harsh decisions of the autonomous vehicle, thus encouraging it to reduce the negative impacts on traffic flow. Further, we propose an improved RISE (RISE++) framework that incorporates a motion prediction model to augment state features for reasonable decisions, a modification of the reward function for energy efficiency, and a multi-worker paradigm for training efficiency. Extensive experiments offer evidence that the proposed framework can advance the state of the art in terms of effectiveness and efficiency.

Autonomous driving is an emerging technology that has developed rapidly over the last decade, with decision-making remaining a critical challenge, particularly due to its significant role in traffic congestion. In this paper, we propose a novel perception-and-decision framework, calledHEAD, which consists of an enHanced pErception module and a mAneuverDecision module to address this challenge. In the enhanced perception module, a graph-based state prediction model with a strategy of phantom vehicle construction is proposed to address incomplete vehicle features and predict future states in parallel. Then in the maneuver decision module, a deep reinforcement learning-based model is designed to learn a driving policy based on a parameterized action Markov decision process. A hybrid reward function takes into account aspects of safety, efficiency, comfort, and impact to guide the autonomous vehicle to make optimal maneuver decisions. To make our framework applicable to more scenarios, we further propose an improvedHEAD(HEAD++) framework that makes the autonomous vehicle adapt to various road structures, such as lane merging and diverging scenarios. Besides, we develop a style tuning module inHEAD++, which supports personalized driving style tuning. To mitigate high training costs, an efficient style tuning method with approximate gradient descent is proposed to reduce the number of training iterations. Extensive experiments demonstrate the effectiveness of our framework. Compared to state-of-the-art methods,HEAD++ reduces overall traffic disturbance by 23.3%-40.9%, lowers collision risk by 4.5%-17.8%, and improves passenger comfort by 13.1%-30.5%, while maintaining high traffic efficiency.

Trust relationships play a crucial role in various domains, such as social spam detection, retweet behavior analytics, and recommendation systems. Trust is often implicit and difficult to observe directly in the real world, as it is driven by people's underlying intentions and motivations. Therefore, when evaluating trust, it is critical to analyze not only user behavior data but also the intentions behind these behaviors that lead to trust. Existing trust evaluation methods often neglect the underlying reasons behind connections, such as shared hobbies or belonging to the same community. Therefore, these methods cannot differentiate the genuine intentions that lead to trust, resulting in an inaccurate evaluation of hidden trust relationships. To address this issue, we propose a novel Intent-based model for Trust Evaluation (INTRUST). This model can distinguish the intent behind high-order information in social communities using hypergraphs. Initially, we used hyperedges to represent high-order correlations between user-to-item and user-to-user interactions. Then, we construct K intent prototypes, which serve as foundational elements to build trust. Furthermore, we distinguish K-independent intent subgraphs from these high order correlations. To enhance the generalization and robustness of the model, we employ self-supervised learning and construct contrastive views at the node-level, hyperedge-level, and node hyperedge-level. Extensive experiments on real-world datasets demonstrate that our model outperforms state-of-the-art approaches in terms of trust evaluation accuracy and efficiency.

Spatio-temporal data intelligence, which includes sensing, managing, and mining large-scale data across space and time, plays a pivotal role in understanding complex systems in real-world applications, such as urban computing and smart cities. With the rapid evolution of foundation models and their growing potential to transform spatio-temporal analytics, we propose a comprehensive half-day workshop (with at least 5 accepted papers, 3 keynote talks, 1 panel discussion, and over 50 attendees) at CIKM 2025, catering to professionals, researchers, and practitioners who are interested in spatio-temporal data intelligence and foundation models to address real-world challenges. The workshop will not only offer a platform for knowledge exchange but also acknowledge outstanding contributions through a distinguished Best Paper Award. A dedicated panel discussion will explore recent advances, emerging trends, and open challenges in integrating spatio-temporal data and emerging machine learning techniques, fostering dialogue between academia and industry. Note that this will be the eleventh time that our core members have organized a similar workshop. The previous 10 workshops were hosted in top-tier data mining and management venues, e.g., SIGKDD, WWW, and IJCAI, each of which attracted over 60 participants and 25 submissions on average.

In the realm of multi-behavior sequential recommendation (MBSR), the complexity and heterogeneity of user interactions pose substantial challenges for sequence modeling. Existing studies involve significant efforts in combining different modules to learn more expressive multi-behavior sequence representations or designing strategies to extract user preferences related to the target behavior. Despite their effectiveness, these methods neglect a thorough analysis of how behavioral information shapes the probability distribution for next-item prediction, which is crucial for accurately modeling user preferences. To this end, we first analyze the learning distribution of MBSR, shedding light on the significance of target behavior in next-item prediction. Building upon this insight, we propose a Behavior-Aware Regularization approach for multi-behavior sequential Rec ommendation (BAR4Rec), where we introduce a regularization loss function to preserve the intrinsic constraints of target behavior. In this way, the target probability distribution is extracted from the whole distribution and naturally evolves into a more compatible and tractable form, thus facilitating model design and training. We evaluate the proposed method on three real-world datasets, and the results validate the efficacy of our approach.

Traffic accidents are one of the leading causes of death in the world. As an important part of the design of traffic roads, tunnels bring convenience but also have huge safety risks. To monitor road safety in real time and give timely warnings for drivers in tunnels, where the light is dark, the space is limited, and the signal is unstable, we study the problem of traffic safety evaluation based on macroscopic traffic features in road tunnels. In particular, we transform the problem into a four-classification problem. To overcome the long collection cycle of traffic crash data, we use the time-to-collision index as the standard for dividing safety levels of road sections in tunnels. To achieve the goal of collecting data in real time under the environment constraints of tunnels, we use macroscopic traffic features as input in our model. Specifically, we design a deep learning model, where the lane block can extract the interaction information of sequential road segments in the same lane, and the prediction block can integrate the results of the individual prediction of each lane and the overall prediction. An extensive emprical study with real data offers insight into the effectiveness and efficiency of the proposed model.

With the rapid advancement of mobile networks and the widespread use of mobile devices, spatial crowdsourcing, which involves assigning location-based tasks to mobile workers, has gained significant attention. However, most existing research focuses on task assignment at the current moment, overlooking the fluctuating demand and supply between tasks and workers over time. To address this issue, we introduce an adaptive task assignment problem, which aims to maximize the number of assigned tasks by dynamically adjusting task assignments in response to changing demand and supply. We develop a spatial crowdsourcing framework, namely demand-based adaptive task assignment with dynamic worker availability windows, which consists of two components including task demand prediction and task assignment. In the first component, we construct a graph adjacency matrix representing the demand dependency relationships in different regions and employ a multivariate time series learning approach to predict future task demands. In the task assignment component, we adjust tasks to workers based on these predictions, worker availability windows, and the current task assignments, where each worker has an availability window that indicates the time periods they are available for task assignments. To reduce the search space of task assignments and be efficient, we propose a worker dependency separation approach based on graph partition and a task value function with reinforcement learning. Experiments on real data demonstrate that our proposals are both effective and efficient.

Similar subtrajectory search (SimSub) aims to find a subtrajectory (i.e., a segment) from a data trajectory (the trajectory to be queried) that closely resembles the query trajectory. Compared with similar trajectory search, SimSub can capture finer-grained similarity and is vital for various trajectory analysis tasks, such as trajectory clustering and join. However, SimSub may return a subtrajectory with extremely limited length, e.g., a single point, which may not align with the expectations of real-world applications. To solve this issue, we propose a constrained SimSub (cSimSub) problem, where the length of the returned subtrajectory must be greater than or equal to a user-specified integer$C$. We demonstrate that this problem can be solved exactly with a time complexity equivalent to$C$times the complexity of the trajectory distance measurement, given that the distance function can be computed using dynamic programming (DP). We also observe that when$C=1$, the solution of cSimSub differs from the vanilla trajectory distance computation (e.g., DTW) only in the state initialization of the DP matrix. Moreover, SimSub focuses on finding a subtrajectory with successive point indexes, which limits its applicability in certain scenarios, e.g., trajectory simplification. Thus, we extend it to sSimSub for trajectory simplification, aiming to find the most similar non-continuous subsequence of a trajectory to itself, with a length constraint of$C$. The subsequence, i.e., the simplified subtrajectory, obtained from sSimSub can achieve the best self-similarity. We conduct experiments on three public available datasets to demonstrate the effectiveness of the proposals. The results show that integrating sSimSub into typical query methods, e.g., KNN query, can achieve higher accuracy of these methods in simplified trajectory databases compared with other well-known trajectory simplification algorithms.

Movement trajectory similarity computation is important when supporting functionalities such as outlier detection and prediction that may, in turn, fuel a variety of transportation-related applications. Recent trajectory similarity learning solutions often assume that trajectories are available at a central location. Yet, we are witnessing the decentralized collection of increasingly massive volumes of trajectories due to the deployment of edge devices. To enable decentralized training and improved privacy, we propose a federated trajectory similarity learning framework that features privacy-preserving clustering based on a client-server architecture. The framework encompasses local, client-side trajectory preprocessing and representation learning. This is combined with a novel privacy-preserving clustering mechanism that ensures consistent model updates between clients and the server, thus alleviating the effects of trajectory heterogeneity across clients. In addition, the framework features a hierarchical central aggregation mechanism that supports clustered federated learning. Experiments on real data offer evidence that the effectiveness of the proposed framework performs as intended.

The rapid development of smart devices has fostered the growth of Spatial Crowdsourcing (SC), where workers complete spatial tasks by traveling to specific locations. Task assignment is a key issue in SC due to the inherent complexity of matching workers with these spatial tasks efficiently. Previous studies on task assignment have primarily focused on optimizing worker-task matching within a single, centralized area, often ignoring scenarios that involve multiple independent service centers across an area. To address this gap, we introduce a collaborative multi-center task assignment problem, which focuses on scenarios where an SC platform manages multiple independent service centers within an area, shifting the focus from worker-level cooperation to exploring the solutions specific to multi-center coordination. We target the imbalances between available workers and unassigned tasks among different centers, aiming to maximize the total number of assigned tasks and minimize unfairness in inter-center collaboration. In particular, we propose an Iterative Multi-center Task Assignment and Optimization (IMTAO) framework. IMTAO operates in two phases: (1) center-independent task assignment based on an efficient sequential task assignment algorithm, and (2) inter-center workforce transfer based on a game-theoretic multi-center collaboration algorithm that ensures fair collaboration through bi-directional optimization. Extensive experiments demonstrate the efficiency and effectiveness of IMTAO in enhancing task assignment and improving collaboration fairness compared to baseline methods.

Road traffic forecasting is crucial in real-world intelligent transportation scenarios like traffic dispatching and path planning in city management and personal traveling. Spatio-temporal graph neural networks (STGNNs) stand out as the mainstream solution in this task. Nevertheless, the quadratic complexity of remarkable dynamic spatial modeling-based STGNNs has become the bottleneck over large-scale traffic data. From the spatial data management perspective, we present a novel Transformer framework called PatchSTG to efficiently and dynamically model spatial dependencies for large-scale traffic forecasting with interpretability and fidelity. Specifically, we design a novel irregular spatial patching to reduce the number of points involved in the dynamic calculation of Transformer. The irregular spatial patching first utilizes the leaf K-dimensional tree (KDTree) to recursively partition irregularly distributed traffic points into leaf nodes with a small capacity, and then merges leaf nodes belonging to the same subtree into occupancy-equaled and non-overlapped patches through padding and backtracking. Based on the patched data, depth and breadth attention are used interchangeably in the encoder to dynamically learn local and global spatial knowledge from points in a patch and points with the same index of patches. Experimental results on four real world large-scale traffic datasets show that our PatchSTG achieves train speed and memory utilization improvements up to 10x and 4x with the state-of-the-art performance.

Recently, the personalization of Large Language Models (LLMs) to generate content that aligns with individual user preferences has garnered widespread attention. Personalized Retrieval-Augmented Generation (RAG), which retrieves relevant documents from the user's history to reflect their preferences and enhance LLM generation, is one commonly used approach for personalization. However, existing personalized RAG methods do not consider that the histories of similar users can also assist in personalized generation for the current user, meaning that collaborative information between users can also benefit personalized generation. Inspired by the application of collaborative filtering in recommender systems, we propose a method called CFRAG, which adapts Collaborative Filtering to RAG for personalized text generation. However, this presents two challenges: (1) how to incorporate collaborative information without explicit user similarity labels? (2) how to retrieve documents that support personalized LLM generation? For Challenge 1, we use contrastive learning to train user embeddings to retrieve similar users and introduce collaborative information. For Challenge 2, we design a personalized retriever and reranker to retrieve the top-k documents from these users' histories. We take into account the user's preference during retrieval and reranking. Then we leverage feedback from the LLM to fine-tune the personalized retriever and reranker, enabling them to retrieve documents that meet the personalized generation needs of the LLM. Experimental results on the Language Model Personalization (LaMP) benchmark validate the effectiveness of CFRAG. Further analysis confirms the importance of incorporating collaborative information.

Retrieval-Augmented Generation (RAG) systems for Large Language Models (LLMs) have shown promise in knowledge-intensive tasks, yet their reasoning capabilities, particularly for complex multi-step reasoning, remain limited. Although recent approaches have explored integrating RAG with chain-of-thought reasoning or incorporating test-time search with process reward model (PRM), these methods face several untrustworthy challenges, including lack of explanations, bias in PRM training data, early-step bias in PRM scores, and ignoring post-training that fails to fully optimize reasoning potential. To address these issues, we propose Retrieval-Augmented Reasoning through Trustworthy Process Rewarding (ReARTeR), a framework that enhances RAG systems' reasoning capabilities through both post-training and test-time scaling. At test time, ReARTeR introduces Trustworthy Process Rewarding via a Process Reward Model for accurate scalar scoring and a Process Explanation Model (PEM) for generating natural language explanations, enabling step refinement. During post-training, we leverage Monte Carlo Tree Search guided by Trustworthy Process Rewarding to collect high-quality step-level preference data, which is used to optimize the model through Iterative Preference Optimization. ReARTeR tackles three key challenges: (1) misalignment between PRM and PEM, addressed through off-policy preference learning; (2) bias in PRM training data, mitigated by a balanced annotation method and incorporating stronger annotations for difficult examples; and (3) early-step bias in PRM, resolved via a temporal-difference-based look-ahead search strategy. Experimental results on multi-step reasoning benchmarks demonstrate that ReARTeR significantly improves reasoning performance, highlighting its potential to advance the reasoning capability of RAG systems.

Sequential recommender systems (SRSs) excel in capturing users' dynamic interests, thus playing a key role in various industrial applications. The popularity of SRSs has also driven emerging research on their security aspects, where data poisoning attack for targeted item promotion is a typical example. Existing attack mechanisms primarily focus on increasing the ranks of target items in the recommendation list by injecting carefully crafted interactions (i.e., poisoning sequences), which comes at the cost of demoting users' real preferences. Consequently, noticeable recommendation accuracy drops are observed, restricting the stealthiness of the attack. Additionally, the generated poisoning sequences are prone to substantial repetition of target items, which is a result of the unitary objective of boosting their overall exposure and lack of effective diversity regularizations. Such homogeneity not only compromises the authenticity of these sequences, but also limits the attack effectiveness, as it ignores the opportunity to establish sequential dependencies between the target and many more items in the SRS. To address the issues outlined, we propose a Diversity-aware Dual-promotion Sequential Poisoning attack method named DDSP for SRSs. Specifically, by theoretically revealing the conflict between recommendation and existing attack objectives, we design a revamped attack objective that promotes the target item while maintaining the relevance of preferred items in a user's ranking list. We further develop a diversity-aware, auto-regressive poisoning sequence generator, where a re-ranking method is in place to sequentially pick the optimal items by integrating diversity constraints. By attacking two representative SRSs on three real-world datasets, comprehensive experimental results demonstrate that DDSP outperforms state-of-the-art attack methods in attack effectiveness. Moreover, DDSP achieves the strongest stealthiness with its lowest impact on recommendation accuracy.

Sequential Recommendation (SR) plays a pivotal role in recommender systems by tailoring recommendations to user preferences based on their non-stationary historical interactions. Achieving high-quality performance in SR requires attention to both item representation and diversity. However, designing an SR method that simultaneously optimizes these merits remains a long-standing challenge. In this study, we address this issue by integrating recent generative Diffusion Models (DM) into SR. DM has demonstrated utility in representation learning and diverse image generation. Nevertheless, a straightforward combination of SR and DM leads to sub-optimal performance due to discrepancies in learning objectives (recommendation vs. noise reconstruction) and the respective learning spaces (non-stationary vs. stationary). To overcome this, we propose a novel framework called DimeRec (Di ffusion with multi-interest enhanced Rec ommender). DimeRec synergistically combines a guidance extraction module (GEM) and a generative diffusion aggregation module (DAM). The GEM extracts crucial stationary guidance signals from the user's non-stationary interaction history, while the DAM employs a generative diffusion process conditioned on GEM's outputs to reconstruct and generate consistent recommendations. Our numerical experiments demonstrate that DimeRec significantly outperforms established baseline methods across three publicly available datasets. Furthermore, we have successfully deployed DimeRec on a large-scale short video recommendation platform, serving hundreds of millions of users. Live A/B testing confirms that our method improves both users' time spent and result diversification.

Recent research on query generation has focused on using Large Language Models (LLMs), which, despite achieving state-of-the-art performance, also introduce hallucination issues in generated queries. In this work, we categorize these issues into relevance hallucination and factuality hallucination, proposing a new typology for hallucinations arising from LLM-based query generation. We present an effective approach to decouple content from form in LLM-generated queries, preserving the factual knowledge extracted and integrated from inputs while leveraging the LLM's linguistic capabilities to construct syntactic structures, including function words. Specifically, we introduce a model-agnostic and training-free method that transforms the Large Language Model into a Pointer-Generator (LargePiG), where the pointer attention distribution utilizes the LLM's inherent attention weights, and the copy probability is derived from the difference between the vocabulary distribution in the model's high layers and the last layer. To validate the effectiveness of LargePiG, we constructed two datasets for assessing hallucination issues in query generation, covering both document and video scenarios. Empirical studies on various LLMs demonstrated LargePiG's superiority across both datasets. Additional experiments further verified that LargePiG reduces hallucination in large vision-language models and enhances the accuracy of document-based question-answering and factuality evaluation tasks. The source code and dataset are available at https://github.com/Jeryi-Sun/LargePiG.

Content-based Recommender Systems (CRSs) play a crucial role in shaping user experiences in e-commerce, online advertising, and personalized recommendations. However, due to the vast amount of categorical features, the embedding tables used in CRS models pose a significant storage bottleneck for real-world deployment, especially on resource-constrained devices. To address this problem, various embedding pruning methods have been proposed, but most existing ones require expensive retraining steps for each target parameter budget, leading to enormous computation costs. In reality, this computation cost is a major hurdle in real-world applications with diverse storage requirements, such as federated learning and streaming settings. In this paper, we propose Shapley Value-guided Embedding Reduction (Shaver) as our response. With Shaver, we view the problem from a cooperative game perspective, and quantify each embedding parameter's contribution with Shapley values to facilitate contribution-based parameter pruning. To address the inherently high computation costs of Shapley values, we propose an efficient and unbiased method to estimate Shapley values of a CRS's embedding parameters. Moreover, in the pruning stage, we put forward a field-aware codebook to mitigate the information loss in the traditional zero-out treatment. Through extensive experiments on three real-world datasets, Shaver has demonstrated competitive performance with lightweight recommendation models across various parameter budgets. The source code is available at https://github.com/chenxing1999/shaver.

Approximate nearest neighbor search is fundamental in information retrieval. Previous partition-based methods enhance search efficiency by probing partial partitions, yet they face two common issues. In the query phase, a common strategy is to probe partitions based on the distance ranks of a query to partition centroids, which inevitably probes irrelevant partitions as it ignores data distribution. In the partition construction phase, all partition-based methods face the boundary problem that separates a query's nearest neighbors to multiple partitions, resulting in a long-tailed kNN distribution and degrading the optimal nprobe (i.e., the number of probing partitions). To address this gap, we propose LIRA, a LearnIng-based queRy-aware pArtition framework. Specifically, we propose a probing model to directly probe the partitions containing the kNN of a query, which can reduce probing waste and allow for query-aware probing with nprobe individually. Moreover, we incorporate the probing model into a learning-based redundancy strategy to mitigate the adverse impact of the long-tailed kNN distribution on search efficiency. Extensive experiments on real-world vector datasets demonstrate the superiority of LIRA in the trade-off among accuracy, latency, and query fan-out. The codes are available at https://github.com/SimoneZeng/LIRA-ANN-search.

In the realm of big data and cloud analytics, efficiently managing and retrieving high-dimensional data presents a critical challenge. Traditional indexes often struggle with the storage overhead inherent in large datasets. There is a growing interest in the adoption of Small Materialize Aggregation (SMA) among cloud database vendors due to its ability to maintain lightweight block-level metadata, facilitating efficient block skipping. However, SMA performance relies heavily on data layout. This is especially critical in scenarios with wide tables containing hundreds of dimensions, where the curse of dimensionality exacerbates the issue. In this paper, we propose AdaCurve , a novel approach aimed at enhancing block skipping in high-dimensional datasets through adaptive optimization of data layout. Unlike conventional static and non-adaptive space-filling curves (SFCs), AdaCurve leverages machine learning to develop an adaptive curve---a dynamically adjusting optimal projection function tailored to high-dimensional workloads and data characteristics. We introduce an attention-based network to handle high-dimensional data and a learnable objective for training adaptive curves in an end-to-end manner. Extensive experiments conducted on the Spark with real-world datasets demonstrate the effectiveness of AdaCurve . We have shown that AdaCurve effectively scales to datasets with dimensions of up to 1,000 columns, achieving a 2.8× improvement in block skipping compared to SFCs.

Accurate time series forecasting is crucial for optimizing resource allocation, industrial production, and urban management, particularly with the growth of cyber-physical and IoT systems. However, limited training sample availability in fields like physics and biology poses significant challenges. Existing models struggle to capture long-term dependencies and to model diverse meta-knowledge explicitly in few-shot scenarios. To address these issues, we propose MetaGP, a meta-learning-based Gaussian process latent variable model that uses a Gaussian process kernel function to capture long-term dependencies and to maintain strong correlations in time series. We also introduce Kernel Association Search (KAS) as a novel meta-learning component to explicitly model meta-knowledge, thereby enhancing both interpretability and prediction accuracy. We study MetaGP on simulated and real-world few-shot datasets, showing that it is capable of state-of-the-art prediction accuracy. We also find that MetaGP can capture long-term dependencies and can model meta-knowledge, thereby providing valuable insights into complex time series patterns.

The widespread deployment of wireless and mobile devices results in a proliferation of decentralized spatio-temporal data. Many recent proposals that target deep learning for spatio-temporal prediction assume that all data is available at a central location and suffers from so-called catastrophic forgetting, where previously learned knowledge is entirely forgotten when new data arrives. Such proposals may face data privacy concerns and may experience deteriorating prediction performance when applied in decentralized settings where data streams into the system. To bridge the gap between decentralized training and spatio-temporal prediction on streaming data, we propose a unified federated continuous learning framework, which uses a horizontal federated learning mechanism for protecting data privacy and includes a global replay buffer with synthetic spatio-temporal data generated by the previously learned global model. For each client, we fuse the current training data with synthetic spatio-temporal data using a spatio-temporal mixup mechanism to preserve historical knowledge effectively, thus avoiding catastrophic forgetting. To enable holistic representation preservation, the local models at clients each integrates a general spatio-temporal autoencoder with a spatio-temporal simple siamese network that aims to ensure prediction accuracy and avoid holistic feature loss. Extensive experiments on real data offer insight into the effectiveness of the proposed framework.

Recommender systems mitigate information overload by offering personalized suggestions to users. As the interactions between users and items can inherently be depicted as a bipartite graph, recent years have seen a surge in the interest in harnessing graph neural networks (GNNs) for enhancing recommender systems. However, a notable limitation of current GNN-based recommendation models is their exclusive emphasis on positive feedback, while disregarding the potentially insightful negative feedback. In this article, we introduce Pone-GNN, a novel recommendation model that synergistically integrates both Po sitive and ne gative feedback in G raph N eural N etworks. Pone-GNN utilizes dual embeddings–interest embeddings for capturing a user’s likes and disinterest embeddings for a user’s dislikes. Also, Pone-GNN performs message passing for both positive and negative feedback, and integrates two sets of embeddings through contrastive learning, which is crucial for extracting robust and discriminative embeddings. Our comprehensive experimental analysis demonstrates that Pone-GNN outperforms state-of-the-art models on diverse real-world recommendation datasets. For example, Pone-GNN achieves a 6.15% increase in relative nDCG@10 compared to the runner-up on the KuaiRec dataset.

The performance of modern database management systems highly relies on hundreds of adjustable knobs. Traditionally, these knobs are manually adjusted by database administrators, a process that is both inefficient and ineffective for tuning large-scale databases in cloud environments. Recent research has explored the use of machine learning techniques to enable the automatic tuning of database configurations. Although most existing learning-based methods achieve satisfactory results on static workloads, they often experience performance degradation and low sampling efficiency in real-world environments. According to our study, this is primarily due to a lack of safety guarantees during the configuration sampling process. To address the aforementioned issues, we propose SafeTune, an online tuning system that adapts to dynamic workloads. Our core idea is to filter out a large number of configurations with potential risks during the configuration sampling process. We employ a two-stage filtering approach: The first stage utilizes a semi-supervised outlier ensemble with feature learning to achieve high-quality feature representation. The second stage employs a ranking-based classifier to refine the filtering process. In addition, to alleviate the cold-start problem, we leverage the historical tuning experience to provide high-quality initial samples during the initialization phase. We conducted comprehensive evaluations on static and dynamic workloads. In comparison to offline baseline methods, SafeTune reduces 95.6%-98.6% unsafe configuration suggestions. In contrast with state-of-the-art methods, SafeTune has improved cumulative performance by 10.5%-46.6% and tuning speed by 15.1%-35.4%.

In large-scale recommendation systems, modeling long-term user interests is progressively gaining attention among researchers and practitioners. Existing work, such as SIM and TWIN, typically employs a two-stage approach to model long-term user behavior sequences for efficiency concerns. The first stage rapidly retrieves a subset of sequences related to the target item from a long sequence using a search-based mechanism namely the General Search Unit (GSU), while the second stage calculates the interest scores using the Exact Search Unit (ESU) on the retrieved results. Given the extensive length of user behavior sequences spanning the entire life cycle, potentially reaching up to 10^6 in scale, there is currently no effective solution for fully modeling such expansive user interests. To overcome this issue, we introduced TWIN-V2, an enhancement of TWIN, where a divide-and-conquer approach is applied to compress life-cycle behaviors and uncover more accurate and diverse user interests. Specifically, a hierarchical clustering method groups items with similar characteristics in life-cycle behaviors into a single cluster during the offline phase. By limiting the size of clusters, we can compress behavior sequences well beyond the magnitude of 10^5 to a length manageable for online inference in GSU retrieval. Cluster-aware target attention extracts comprehensive and multi-faceted long-term interests of users, thereby making the final recommendation results more accurate and diverse. Extensive offline experiments on a multi-billion-scale industrial dataset and online A/B tests have demonstrated the effectiveness of TWIN-V2. Under an efficient deployment framework, TWIN-V2 has been successfully deployed to the primary traffic that serves hundreds of millions of daily active users at Kuaishou.

Recent advancements in Large Language Models (LLMs) have attracted considerable interest among researchers to leverage these models to enhance Recommender Systems (RSs). Existing work predominantly utilizes LLMs to generate knowledge-rich texts or utilizes LLM-derived embeddings as features to improve RSs. Although the extensive world knowledge embedded in LLMs generally benefits RSs, the application can only take a limited number of users and items as inputs, without adequately exploiting collaborative filtering information. Considering its crucial role in RSs, one key challenge in enhancing RSs with LLMs lies in providing better collaborative filtering information through LLMs. In this paper, drawing inspiration from the in-context learning and chain of thought reasoning in LLMs, we propose the Large Language Models enhanced Collaborative Filtering (LLM-CF) framework, which distills the world knowledge and reasoning capabilities of LLMs into collaborative filtering. We also explored a concise and efficient instruction-tuning method, which improves the recommendation capabilities of LLMs while preserving their general functionalities (e.g., not decreasing on the LLM benchmark). Comprehensive experiments on three real-world datasets demonstrate that LLM-CF significantly enhances several backbone recommendation models and consistently outperforms competitive baselines, showcasing its effectiveness in distilling the world knowledge and reasoning capabilities of LLM into collaborative filtering.

A series of studies apply machine learning to assist cost-based query optimizers in DBMS, emphasizing incorporating uncertainty predictions to guide decision-making. While these approaches have demonstrated advancement in some benchmarks, their drawbacks, such as unstable performance, stem from the inherent challenges of using machine learning models to predict the cost of execution plans and the lack of exploration of the intrinsic characteristics of suboptimal plans. In this paper, we introduce an alert system for query optimization, which is built upon cost models to reduce the selection of regressed plans. The key insight is that there are differences in the predictive uncertainty that lead to query optimization and the regression of execution plans. We investigate the causes of these differences in uncertainty and design a discriminator to filter out execution plans with higher risks of regression. The alert system can be integrated with various cost models, enhancing the robustness of query optimizers. In our experiments, the system further reduces execution time by 20% compared to learned optimizers. Meanwhile, the proportion of optimized queries reduced by the alert system is just 15% of the proportion of regressed queries diminished.

The widespread deployment of wireless and mobile devices results in a proliferation of spatio-temporal data that is used in applications, e.g., traffic prediction, human mobility mining, and air quality prediction, where spatio-temporal prediction is often essential to enable safety, predictability, or reliability. Many recent proposals that target deep learning for spatio-temporal prediction suffer from so-called catastrophic forgetting, where previously learned knowledge is entirely forgotten when new data arrives. Such proposals may experience deteriorating prediction performance when applied in settings where data streams into the system. To enable spatio-temporal prediction on streaming data, we propose a unified replay- based continuous learning framework. The framework includes a replay buffer of previously learned samples that are fused with training data using a spatio-temporal mixup mechanism in order to preserve historical knowledge effectively, thus avoiding catastrophic forgetting. To enable holistic representation preservation, the framework also integrates a general spatio-temporal autoencoder with a carefully designed spatio-temporal simple siamese (STSimSiam) network that aims to ensure prediction accuracy and avoid holistic feature loss by means of mutual information maximization. The framework further encompasses five spatio-temporal data augmentation methods to enhance the performance of STSimSiam. Extensive experiments on real data offer insight into the effectiveness of the proposed framework.

Searching for similar trajectories from a database is an important way for extracting human-understandable knowledge. However, due to the huge volume of trajectories and high computation complexity of distance between trajectories, it is difficult to search for exact results, which motivates the research of approximating approaches. In this study, we propose a learning to hash method for trajectory similarity computation and search, called Traj2Hash, which consists of a two-channel trajectory encoder and a hash layer to encode trajectories into Euclidean and Hamming space, respectively. The embeddings of trajectories obtained from the encoder are capable of preserving the reverse symmetric property and more representative due to the reverse augmentation and the lower-bound induced read-out layer. Moreover, we design a decomposed grid representation in the encoder to make the model lighter and better. In the model training phase, we combine a weighted mean squared error loss and a ranking-based hashing loss to enable the model similarity-aware and representations self-structured, respectively, in which a fast trajectory triplet generation method is leveraged to enrich the training corpus. Extensive experiments conducted on real data offer evidence of the effectiveness and efficiency of the proposed model.

The popularity of mobile devices has led to the increased attention of Spatial Crowdsourcing (SC), a framework that assigns location-sensitive tasks to mobile workers. Task recommendation is crucial in helping workers discover attractive tasks. Existing studies have focused on modeling workers' preferences from past task-performing patterns, but their performance is sub-optimal due to the strong coupling of sequentiality, spatiality, and temporality. Moreover, achieving the highest preference-based utility of workers in most of the existing task recommendation studies is inferior to the benefits of the SC platform and the satisfaction of workers in a long range, due to the lower task coverage rate and the poor diversity in a worker's recommended list. To address these problems, we propose a Diversity-Coverage Balanced Task Recommendation (DCBTaskRec) framework. Specifically, we first introduce a decoupled worker preference learning model that adopts self-attention networks as the backbone and decouples the modeling of multiple factors in attention scores. Additionally, we provide an optimal diveristy-aware approach to maximize the recommendation diversity while keeping high preference-based utility of workers to satisfy the multiple tastes of workers. From the side of the SC platform, we also provide two approaches (i.e., greedy coverage-aware approach and diversity-coverage balanced approach) to achieve high coverage and provide a trade-off between diversity and coverage, respectively. Extensive experiments offer insight into the effectiveness of the proposed framework.

In the era of observability, massive amounts of time series data have been collected to monitor the running status of the target system, where anomaly detection serves to identify observations that differ significantly from the remaining ones and is of utmost importance to enable value extraction from such data. While existing reconstruction-based methods have demonstrated favorable detection capabilities in the absence of labeled data, they still encounter issues of training bias on abnormal times and distribution shifts within time series. To address these issues, we propose a simple yet effective Temporal-Frequency Masked AutoEncoder (TFMAE) to detect anomalies in time series through a contrastive criterion. Specifically, TFMAE uses two Transformer-based autoencoders that respectively incorporate a window-based temporal masking strategy and an amplitude-based frequency masking strategy to learn knowledge without abnormal bias and reconstruct anomalies by the extracted normal information. Moreover, the dual autoencoder undergoes training through a contrastive objective function, which minimizes the discrepancy of representations from temporal-frequency masked autoencoders to highlight anomalies, as it helps alleviate the negative impact of distribution shifts. Finally, to prevent over-fitting, TFMAE adopts adversarial training during the training phase. Extensive experiments conducted on seven datasets provide evidence that our model is able to surpass the state-of-the-art in terms of anomaly detection accuracy.

Graph neural networks (GNNs) encounter significant computational challenges when handling large-scale graphs, which severely restricts their efficacy across diverse applications. To address this limitation, graph condensation has emerged as a promising technique, which constructs a small synthetic graph for efficiently training GNNs while retaining performance. However, due to the topology structure among nodes, graph condensation is limited to condensing only the observed training nodes and their corresponding structure, thus lacking the ability to effectively handle the unseen data. Consequently, the original large graph is still required in the inference stage to perform message passing to inductive nodes, resulting in substantial computational demands. To overcome this issue, we propose mapping-aware graph condensation (MCond), explicitly learning the one-to-many node mapping from original nodes to synthetic nodes to seamlessly integrate new nodes into the synthetic graph for inductive representation learning. This enables direct information propagation on the synthetic graph, which is much more efficient than on the original large graph. Specifically, MCond employs an alternating optimization scheme with innovative loss terms from transductive and inductive perspectives, facilitating the mutual promotion between graph condensation and node mapping learning. Extensive experiments demonstrate the efficacy of our approach in inductive inference. On the Reddit dataset, MCond achieves up to 121.5× inference speedup and 55.9× reduction in storage requirements compared with counterparts based on the original graph.

Trajectory streams are being generated from location-aware devices, such as smartphones and in-vehicle navigation systems. Due to the sensitive nature of the location data, directly sharing user trajectories suffers from privacy leakage issues. Local differential privacy (LDP), which perturbs sensitive data on the user side before it is shared or analyzed, emerges as a promising solution for private trajectory stream collection and analysis. Unfortunately, existing stream release approaches often neglect the rich spatial-temporal context information within trajectory streams, resulting in suboptimal utility and limited types of downstream applications. To this end, we propose RetraSyn, a novel real-time trajectory synthesis framework, which is able to perform on-the-f1y trajectory synthesis based on the mobility patterns privately extracted from users' trajectory streams. Thus, the downstream trajectory analysis can be performed on the high-utility synthesized data with privacy protection. We also take the genuine behaviors of real-world mobile travelers into consideration, ensuring authenticity and practicality. The key components of RetraSyn include the global mobility model, dynamic mobility update mechanism, real-time synthesis, and adaptive allocation strategy. We conduct extensive experiments on multiple real-world and synthetic trajectory datasets under various location-based utility metrics, encompassing both streaming and historical scenarios. The empirical results demonstrate the superiority and versatility of our proposed framework.

Cost estimation is of great importance in query optimization. However, traditional optimizers compute the cost based on heuristics, sacrificing accuracy for efficiency. In recent years, learning-based cost estimation models have achieved high accuracy. However, their poor robustness and inefficiency lead to their failure to meet the needs of practical scenarios. We propose a lightweight and Database-Agnostic Cost Estimation model (DACE) to address the above limitations. To further improve the effectiveness of DACE, we design a tree-structure-based loss adjustment strategy to learn sub-plan information and solve the information redundancy problem. As a pretrained estimator, DACE can efficiently make accurate predictions on unseen databases. For more complex scenarios, we fine-tune DACE with LoRA. The excellent efficiency allows DACE to adapt to challenging scenarios with minimal effort. As a pretrained encoder, DACE can improve the accuracy and robustness of other cost estimation models through knowledge integration and solve the notorious cold start problem. Extensive experiments have shown that DACE's accuracy, efficiency, and robustness are much better than existing methods.

With the proliferation of GPS-equipped edge devices, huge trajectory data is generated and accumulated in various domains, motivating a variety of urban applications. Due to the limited acquisition capabilities of edge devices, a lot of trajectories are recorded at a low sampling rate, which may lead to the effectiveness drop of urban applications. We aim to recover a high-sampled trajectory based on the low-sampled trajectory in free space, i.e., without road network information, to enhance the usability of trajectory data and support urban applications more effectively. Recent proposals targeting trajectory recovery often assume that trajectories are available at a central location, which fail to handle the decentralized trajectories and hurt privacy. To bridge the gap between decentralized training and trajectory recovery, we propose a lightweight framework, LightTR, for federated trajectory recovery based on a client-server architecture, while keeping the data decentralized and private in each client/platform center (e.g., each data center of a company). Specifically, considering the limited processing capabilities of edge devices, LightTR encompasses a light local trajectory embedding module that offers improved computational efficiency without compromising its feature extraction capabilities. LightTR also features a meta-knowledge enhanced local-global training scheme to reduce communication costs between the server and clients and thus further offer efficiency improvement. Extensive experiments demonstrate the effectiveness and efficiency of the proposed framework.

Contrastive learning, a powerful self-supervised learning paradigm, has shown its efficacy in learning embed dings from independent and identically distributed (IID) as well as non-IID data without relying on label information. Since high-quality discriminative embeddings form a rich embedding space, which benefits model performance on downstream tasks, it is necessary to study how to improve the quality of contrastive node embeddings in graph contrastive learning. However, there has been limited research on this area. In this paper, we investigate how to generate high-quality contrastive node embeddings based on an in-depth analysis of graph contrastive losses. Firstly, we propose a novel and effective method, GLATE, for estimating the temperatures in three mainstream graph contrastive losses during the training phase. Secondly, we conduct the derivation of GLATE, and the derivation results reveal the specific relationship between the quality of contrastive node embeddings and tem-peratures. Finally, the extensive experiments on 16 benchmark datasets demonstrate that GLATE consistently outperforms the state-of-the-art graph contrastive learning models in terms of both model performance and training efficiency.

Autonomous driving is an emerging technology that has advanced rapidly over the last decade. Modern transportation is expected to benefit greatly from a wise decision-making framework of autonomous vehicles, including the improvement of mobility and the minimization of risks and travel time. However, existing methods either ignore the complexity of environments only fitting straight roads, or ignore the impact on surrounding vehicles during optimization phases, leading to weak environmental adaptability and incomplete optimization objectives. To address these limitations, we propose a pArameterized decision-making framework with mU lti-modality percepTiOn based on deep reinforcement learning, called AUTO. We conduct a comprehensive perception to capture the state features of various traffic participants around the autonomous vehicle, based on which we design a graph-based model to learn a state representation of the multi-modal semantic features. To distinguish between lane-following and lane-changing, we decompose an action of the autonomous vehicle into a parameterized action structure that first decides whether to change lanes and then computes an exact action to execute. A hybrid reward function takes into account aspects of safety, traffic efficiency, passenger comfort, and impact to guide the framework to generate optimal actions. In addition, we design a regularization term and a multi-worker paradigm to enhance the training. Extensive experiments offer evidence that AUTO can advance state-of-the-art in terms of both macroscopic and microscopic effectiveness.

Trust plays an essential role in an individual's decision-making. Traditional trust prediction models rely on pairwise correlations to infer potential relationships between users. However, in the real world, interactions between users are usually complicated rather than pairwise only. Hypergraphs offer a flexible approach to modeling these complex high-order correlations (not just pairwise connections), since hypergraphs can leverage hyperedeges to link more than two nodes. However, most hypergraph-based methods are generic and cannot be well applied to the trust prediction task. In this paper, we propose an Adaptive Hypergraph Network for Trust Prediction (AHNTP), a novel approach that improves trust prediction accuracy by using higher-order correlations. AHNTP utilizes Motif-based PageRank to capture high-order social influence information. In addition, it constructs hypergroups from both node-level and structure-level attributes to incorporate complex correlation information. Furthermore, AHNTP leverages adaptive hypergraph Graph Convolutional Network (GCN) layers and multilayer perceptrons (MLPs) to generate comprehensive user embeddings, facilitating trust relationship prediction. To enhance model generalization and robustness, we introduce a novel supervised contrastive learning loss for optimization. Extensive experiments demonstrate the superiority of our model over the state-of-the-art approaches in terms of trust prediction accuracy.

Contact tracing query (CTQ) plays a crucial role in the prevention of epidemic diseases. In real-world applications, user trajectory, encompassing a wealth of sensitive information, is typically dispersed across various devices or organizations. Consequently, safeguarding user privacy becomes imperative in the context of CTQ. Simultaneously, for effective epidemic control, it is essential to identify contacts efficiently and accurately, enabling prompt implementation of necessary measures. However, existing CTQ studies face limitations as they struggle to concurrently meet the demands of privacy, accuracy and efficiency. This constraint impedes their practical application in real-world scenarios. To this end, we define the Federated Contact Tracing Query (F-CTQ) problem and propose the FedCTQ framework based on hierarchical federation. To the best of our knowledge, this is the first solution grounded in federation, offering a simultaneous fulfillment of privacy, accuracy and efficiency requirements. Specifically, to ensure the privacy of F-CTQ, we introduce a meticulously designed binary-based secret-sharing (BSS) scheme, which delivers an effective privacy guarantee for user data while preserving the accuracy of the query results. Concurrently, to enhance the efficiency of F-CTQ, we propose a binary-based distance tree (DistTree) index that maximizes computational resources for parallel queries. Based on DistTree, FedCTQ enables nearly the real-time and accurate execution of F-CTQ. Extensive experiments on four datasets demonstrate the superiority of FedCTQ, showcasing a remarkable performance improvement ranging from$4.7\times$to$14.8\times$over state-of-the-art approaches.

Nowadays, many platforms provide users with both search and recommendation services as important tools for accessing information. The phenomenon has led to a correlation between user search and recommendation behaviors, providing an opportunity to model user interests in a fine-grained way. Existing approaches either model user search and recommendation behaviors separately or overlook the different transitions between user search and recommendation behaviors. In this paper, we propose a framework named UniSAR that effectively models the different types of fine-grained behavior transitions for providing users a Unified Search And Recommendation service. Specifically, UniSAR models the user transition behaviors between search and recommendation through three steps: extraction, alignment, and fusion, which are respectively implemented by transformers equipped with pre-defined masks, contrastive learning that aligns the extracted fine-grained user transitions, and cross-attentions that fuse different transitions. To provide users with a unified service, the learned representations are fed into the downstream search and recommendation models. Joint learning on both search and recommendation data is employed to utilize the knowledge and enhance each other. Experimental results on two public datasets demonstrated the effectiveness of UniSAR in terms of enhancing both search and recommendation simultaneously. The experimental analysis further validates that UniSAR enhances the results by successfully modeling the user transition behaviors between search and recommendation.

To make room for privacy and efficiency, the deployment of many recommender systems is experiencing a shift from central servers to personal devices, where the federated recommender systems (FedRecs) and decentralized collaborative recommender systems (DecRecs) are arguably the two most representative paradigms. While both leverage knowledge (e.g., gradients) sharing to facilitate learning local models, FedRecs rely on a central server to coordinate the optimization process, yet in DecRecs, the knowledge sharing directly happens between clients. On the flip side, knowledge sharing also opens a backdoor for model poisoning attacks, where adversaries disguise themselves as benign clients and disseminate polluted knowledge to achieve malicious goals like promoting an item's exposure rate. Although research on such poisoning attacks provides valuable insights into finding security loopholes and corresponding countermeasures, existing attacks mostly focus on FedRecs, and are either inapplicable or ineffective for DecRecs. Compared with FedRecs where the tampered information can be universally distributed to all clients once uploaded to the cloud, each adversary in DecRecs can only communicate with neighbor clients of a small size, confining its impact to a limited range.

As an indispensable personalized service within Location-Based Social Networks (LBSNs), the Point-of-Interest (POI) recommendation aims to assist individuals in discovering attractive and engaging places. However, the accurate recommendation capability relies on the powerful server collecting a vast amount of users' historical check-in data, posing significant risks of privacy breaches. Although several collaborative learning (CL) frameworks for POI recommendation enhance recommendation resilience and allow users to keep personal data on-device, they still share personal knowledge to improve recommendation performance, thus leaving vulnerabilities for potential attackers. Given this, we design a new Physical Trajectory Inference Attack (PTIA) to expose users' historical trajectories. Specifically, for each user, we identify the set of interacted POIs by analyzing the aggregated information from the target POIs and their correlated POIs. We evaluate the effectiveness of PTIA on two real-world datasets across two types of decentralized CL frameworks for POI recommendation. Empirical results demonstrate that PTIA poses a significant threat to users' historical trajectories. Furthermore, Local Differential Privacy (LDP), the traditional privacy-preserving method for CL frameworks, has also been proven ineffective against PTIA. In light of this, we propose a novel defense mechanism (AGD) against PTIA based on an adversarial game to eliminate sensitive POIs and their information in correlated POIs. After conducting intensive experiments, AGD has been proven precise and practical, with minimal impact on recommendation performance.

The Probability Ranking Principle (PRP) has been considered as the foundational standard in the design of information retrieval (IR) systems. The principle requires an IR module's returned list of results to be ranked with respect to the underlying user interests, so as to maximize the results' utility. Nevertheless, we point out that it is inappropriate to indiscriminately apply PRP through every stage of a contemporary IR system. Such systems contain multiple stages (e.g., retrieval, pre-ranking, ranking, and re-ranking stages, as examined in this paper). The selection bias inherent in the model of each stage significantly influences the results that are ultimately presented to users. To address this issue, we propose an improved ranking principle for multi-stage systems, namely the Generalized Probability Ranking Principle (GPRP), to emphasize both the selection bias in each stage of the system pipeline as well as the underlying interest of users. We realize GPRP via a unified algorithmic framework named Full Stage Learning to Rank. Our core idea is to first estimate the selection bias in the subsequent stages and then learn a ranking model that best complies with the downstream modules' selection bias so as to deliver its top ranked results to the final ranked list in the system's output. We performed extensive experiment evaluations of our developed Full Stage Learning to Rank solution, using both simulations and online A/B tests in one of the leading short-video recommendation platforms. The algorithm is proved to be effective in both retrieval and ranking stages. Since deployed, the algorithm has brought consistent and significant performance gain to the platform.

High-dimensional approximate K nearest neighbor search (AKNN) is a fundamental task for various applications, including information retrieval. Most existing algorithms for AKNN can be decomposed into two main components, i.e., candidate generation and distance comparison operations (DCOs). While different methods have unique ways of generating candidates, they all share the same DCO process. In this study, we focus on accelerating the process of DCOs that dominates the time cost in most existing AKNN algorithms. To achieve this, we propose an Data-Aware Distance Estimation approach, called DADE , which approximates the exact distance in a lower-dimensional space. We theoretically prove that the distance estimation in DADE is unbiased in terms of data distribution. Furthermore, we propose an optimized estimation based on the unbiased distance estimation formulation. In addition, we propose a hypothesis testing approach to adaptively determine the number of dimensions needed to estimate the exact distance with sufficient confidence. We integrate DADE into widely-used AKNN search algorithms, e.g., IVF and HNSW , and conduct extensive experiments to demonstrate the superiority.

Portfolio management is an important yet challenging task in AI for FinTech, which aims to allocate investors' budgets among different assets to balance the risk and return of an investment. In this study, we propose a general M ulti-object I ve framework with contro LL able r I sk for p O rtfolio ma N agement ( MILLION ), which consists of two main phases, i.e., return-related maximization and risk control. Specifically, in the return-related maximization phase, we introduce two auxiliary objectives, i.e., return rate prediction, and return rate ranking, combined with portfolio optimization to remit the overfitting problem and improve the generalization of the trained model to future markets. Subsequently, in the risk control phase, we propose two methods, i.e., portfolio interpolation and portfolio improvement, to achieve fine-grained risk control and fast risk adaption to a user-specified risk level. For the portfolio interpolation method, we theoretically prove that the risk can be perfectly controlled if the to-be-set risk level is in a proper interval. In addition, we also show that the return rate of the adjusted portfolio after portfolio interpolation is no less than that of the min-variance optimization, as long as the model in the reward maximization phase is effective. Furthermore, the portfolio improvement method can achieve greater return rates while keeping the same risk level compared to portfolio interpolation. Extensive experiments are conducted on three real-world datasets. The results demonstrate the effectiveness and efficiency of the proposed framework.

The expanding instrumentation of processes throughout society with sensors yields a proliferation of time series data that may in turn enable important applications, e.g., related to transportation infrastructures or power grids. Machine-learning based methods are increasingly being used to extract value from such data. We provide means of reducing the resulting considerable computational and data storage costs. We achieve this by providing means of condensing large time series datasets such that models trained on the condensed data achieve performance comparable to those trained on the original, large data. Specifically, we propose a time series dataset condensation framework, TimeDC, that employs two-fold modal matching, encompassing frequency matching and training trajectory matching. Thus, TimeDC performs time series feature extraction and decomposition-driven frequency matching to preserve complex temporal dependencies in the reduced time series. Further, TimeDC employs curriculum training trajectory matching to ensure effective and generalized time series dataset condensation. To avoid memory overflow and to reduce the cost of dataset condensation, the framework includes an expert buffer storing pre-computed expert trajectories. Extensive experiments on real data offer insight into the effectiveness and efficiency of the proposed solutions.

Traffic forecasting is crucial for public safety and resource optimization, yet is very challenging due to the temporal changes and the dynamic spatial correlations. To capture these intricate dependencies, spatio-temporal networks, such as recurrent neural networks with graph convolution networks, are applied. However, traffic forecasting is still a non-trivial task because of three major challenges: 1) Previous spatio-temporal networks are based on end-to-end training and thus fail to handle the distribution shift in the non-stationary traffic time series. 2) Existing methods always utilize the one-hour input to forecast future traffic and the long-term historical trend knowledge is ignored. 3) The efficient and effective algorithm for modeling multi-scale spatial correlations is still lacking in prior networks. Therefore, in this paper, rather than proposing yet another end-to-end model, we provide a novel disentangle-fusion framework STWave+to mitigate the distribution shift issue. The framework first decouples the complex one-hour traffic data into stable trends and fluctuating events, followed by a dual-channel spatio-temporal network to model trends and events, respectively. Moreover, long-term trends are used as a self-supervised signal in STWave+to teach overall temporal information into one-hour trends through a contrastive loss. Finally, reasonable future traffic can be predicted through the adaptive fusion of one-hour trends and events. Additionally, we incorporate a novel query sampling strategy and multi-scale graph wavelet positional encoding into the full graph attention network to efficiently and effectively model dynamic hierarchical spatial correlations. Extensive experiments on four traffic datasets show the superiority of our approach,i.e., the higher forecasting accuracy with lower computational cost.

With an exponentially growing number of graphs from disparate repositories, there is a strong need to analyze a graph database containing an extensive collection of small- or medium-sized data graphs (eg chemical compounds). Although subgraph enumeration and subgraph mining have been proposed to bring insights into a graph database by a set of subgraph structures, they often end up with similar or homogenous topologies, which is undesirable in many graph applications. To address this limitation, we propose theTop-k Edge-Diversified Patterns Discovery problemto retrieve a set of subgraphs that cover the maximum number of edges in a database. To efficiently process such query, we present a generic and extensible framework called$\textsc {Ted}^+$which achieves a guaranteed approximation ratio to the optimal result. Three optimization strategies are further developed to improve the performance, and a lightweight version calledTedLiteis designed for even larger graph databases. Experimental studies on real-world datasets demonstrate the superiority of$\textsc {Ted}^+$to traditional techniques.

Automation in road vehicles is an emerging technology that has developed rapidly over the last decade. There have been many inter-disciplinary challenges posed on existing transportation infrastructure by autonomous vehicles. In this paper, we conduct an algorithmic study on when and how an autonomous vehicle should change its lane, which is a fundamental problem in vehicle automation field and root cause of most ‘phantom’ traffic jams. We propose a prediction-and-decision framework, called Cheetah (Changelanesmartforautonomous vehicle), which aims to optimize the lane changing maneuvers of autonomous vehicle while minimizing its impact on surrounding vehicles. In the prediction phase, Cheetah learns the spatio-temporal dynamics from historical trajectories of surrounding vehicles with a deep model (GAS-LED model) and predict their corresponding actions in the near future. A global attention mechanism and state sharing strategy are also incorporated to achieve higher accuracy and better convergence efficiency. Then in the decision phase, Cheetah looks for optimal lane change maneuvers for the autonomous vehicle by taking into account a few factors such as speed, impact on other vehicles and safety issues. A tree-based adaptive beam search algorithm is designed to reduce the search space and improve accuracy. In order to make our framework applicable to more scenarios, we further propose an improved Cheetah (Cheetah+) framework that makes the autonomous vehicle adapt for exiting a road and meet the requirement for driving comfort. Extensive experiments offer evidence that the proposed framework can advance the state of the art in terms of effectiveness and efficiency.

Spatial Crowdsourcing (SC) is finding widespread application in today's online world. As we have transitioned from desktop crowdsourcing applications (e.g., Wikipedia) to SC applications (e.g., Uber), there is a sense that SC systems must not only provide effective task assignment but also need to ensure privacy. To achieve these often-conflicting objectives, we propose a framework, Task Assignment with Federated Preference Learning, that performs task assignment based on worker preferences while keeping the data decentralized and private in each platform center (e.g., each delivery center of an SC company). The framework includes a federated preference learning phase and a task assignment phase. Specifically, in the first phase, we build a local preference model for each platform center based on historical data. We provide means of horizontal federated learning that makes it possible to collaboratively train these local preference models under the orchestration of a central server. Specifically, we provide a practical method that accelerates federated preference learning based on stochastic controlled averaging and achieves low communication costs while considering data heterogeneity among clients. The task assignment phase aims to achieve effective and efficient task assignment by considering workers’ preferences. Extensive evaluations on real data offer insight into the effectiveness and efficiency of the paper's proposals.

Uncertainty is an essential consideration for time series forecasting tasks. In this work, we focus on quantifying the uncertainty of traffic forecasting from a unified perspective. We develop a novel traffic forecasting framework, namely Deep Spatio-Temporal Uncertainty Quantification (DeepSTUQ), which can estimate both aleatoric and epistemic uncertainty. Specifically, we first leverage a spatio-temporal model to model the complex spatio-temporal correlations of traffic data. Subsequently, two independent sub-neural networks maximizing the heterogeneous log-likelihood are developed to estimate aleatoric uncertainty. To estimate epistemic uncertainty, we combine the merits of variational inference and deep ensembling by integrating the Monte Carlo dropout and the Adaptive Weight Averaging re-training methods, respectively. Furthermore, to relax the Gaussianity assumption, mitigate overfitting, and improve horizon-wise uncertainty quantification performance, we define a new calibration method called Multi-horizon Conformal Calibration (MHCC). Finally, we provide a theoretical analysis of the proposed unified approach based on the PAC-Bayes theory. Extensive experiments are conducted on four public datasets, and the empirical results suggest that the proposed method outperforms state-of-the-art methods in terms of both point prediction and uncertainty quantification.

Recent years have witnessed a revolution in Spatial Crowdsourcing (SC), in which people with mobile connectivity can perform spatio-temporal tasks that involve traveling to specified locations. In this paper, we identify and study in depth a new multi-center-based task allocation problem in the context of SC, where multiple allocation centers exist. In particular, we aim to maximize the total number of the allocated tasks while minimizing the allocated task number difference. To solve the problem, we propose a two-phase framework, called Task Allocation with Geographic Partition, consisting of a geographic partition and a task allocation phase. The first phase divides the whole study area based on the allocation centers by using both a basic Voronoi diagram-based algorithm and an adaptive weighted Voronoi diagram-based algorithm. In the allocation phase, we utilize a Reinforcement Learning method to achieve the task allocation, where a graph neural network with the attention mechanism is used to learn the embeddings of allocation centers, delivery points, and workers. To further improve the efficiency, we propose an early stopping optimization strategy for the adaptive weighted Voronoi diagram-based algorithm in the geographic partition phase and give a distance-constrained graph pruning strategy for the Reinforcement Learning method in the task allocation phase. Extensive experiments give insight into the effectiveness and efficiency of the proposed solutions.

To address privacy concerns and reduce network latency, there has been a recent trend of compressing cumbersome recommendation models trained on the cloud and deploying compact recommender models to resource-limited devices for the real-time recommendation. Existing solutions generally overlook device heterogeneity and user heterogeneity. They require devices with the same budget to share the same model and assume the available device resources (e.g., memory) are constant, which is not reflective of reality. Considering device and user heterogeneities as well as dynamic resource constraints, this paper proposes a Personalized Elastic Embedding Learning framework (PEEL) for the on-device recommendation, which generates Personalized Elastic Embeddings (PEEs) for devices with various memory budgets in a once-for-all manner, adapting to new or dynamic budgets, and addressing user preference diversity by assigning personalized embeddings for different groups of users. Specifically, it pretrains a global embedding table with collected user-item interaction instances and clusters users into groups. Then, it refines the embedding tables with local interaction instances within each group. PEEs are generated from the group-wise embedding blocks and their weights that indicate the contribution of each embedding block to the local recommendation performance. Given a memory budget, PEEL efficiently generates PEEs by selecting embedding blocks with the largest weights, making it adaptable to dynamic memory budgets on devices. Furthermore, a diversity-driven regularizer is implemented to encourage the expressiveness of embedding blocks, and a controller is utilized to optimize the weights. Extensive experiments are conducted on two public datasets, and the results show that PEEL yields superior performance on devices with heterogeneous and dynamic memory budgets.

Abstract With the widespread use of networked and geo-positioned mobile devices, e.g., smartphones, Spatial Crowdsourcing (SC), which refers to the assignment of location-based tasks to moving workers, is drawing increasing attention. One of the critical issues in SC is task assignment that allocates tasks to appropriate workers. We propose and study a novel SC problem, namely Coalition-based Task Assignment (CTA), where the spatial tasks (e.g., home improvement and furniture installation) may require more than one worker (forming a coalition) to cooperate to maximize the overall rewards of workers. We design a greedy and an equilibrium-based CTA approach. The greedy approach forms a set of worker coalitions greedily for performing tasks and uses an acceptance probability to identify high-value task assignments. In the equilibrium-based approach, workers form coalitions in sequence and update their strategies (i.e., selecting a best-response task), to maximize their own utility (i.e., the reward of the coalition they belong to) until a Nash equilibrium is reached. Since the equilibrium obtained is not unique and optimal in terms of total rewards, we further propose a simulated annealing scheme to find a better Nash equilibrium. To achieve fair task assignments, we optimize the framework to distribute rewards fairly among workers in a coalition based on their marginal contributions and give workers who arrive first at the SC platform highest priority. Extensive experiments demonstrate the efficiency and effectiveness of the proposed methods on real and synthetic data.

Recommendation retrievers commonly retrieve user potentially preferred items from numerous items, where the query and item representation are learned according to the dual encoders with the log-softmax loss. Under real scenarios, the number of items becomes considerably large, making it exceedingly difficult to calculate the partition function with the whole item corpus. Negative sampling, which samples a subset from the item corpus, is widely used to accelerate the model training. Among different samplers, the in-batch sampling is commonly adopted for online recommendation retrievers, which regards the other items within the mini-batch as the negative samples for the given query, owing to its time and memory efficiency. However, the sample selection bias occurs due to the skewed feedback, harming the retrieval quality. In this paper, we propose a negative sampling approach named Batch-Mix Negative Sampling (BMNS), which adopts batch mixing operation to generate additional negatives for model training. Concretely, BMNS first generates new negative items with the sampled mix coefficient from the Beta distribution, after which a tailored correct strategy guided by frequency is designed to match the sampled softmax loss. In this way, the effort of re-encoding items out of the mini-batch is reduced while also improving the representation space of the negative set. The empirical experiments on four real-world datasets demonstrate BMNS is superior to the competitive negative inbatch sampling method.

Autonomous driving is a rapidly advancing field that promises to revolutionize the transportation industry through an intelligent perception-and-decision paradigm. Despite decades of research, existing methods are limited in adapting to complex scenarios or expanding to unseen situations, which pose significant challenges to the development of autonomous driving. Inspired by the process of human learning to drive, autonomous vehicles can prioritize developing driving capabilities in basic scenarios and then extending the atomic abilities to more complex scenarios. To this end, we proposed a perception-and-decision framework, called ATEND, which consists of an adaptive perception module and a maneuver decision module. Specifically, the perception module based on Variational Autoencoder is proposed to map perceptual data of complex scenarios into basic scenarios. Then the reinforcement learning-based decision module can make high-level decisions in transformed scenarios. Once ATEND learns to drive in basic scenarios, it can achieve safe and efficient driving in real scenarios without additional training. Extensive experiments in different traffic scenarios evidence that the proposed framework advances the state of the art in terms of both macroscopic and microscopic effectiveness.

Autonomous driving systems (ADSs) have the potential to revolutionize transportation by improving traffic safety and efficiency. As the core component of ADSs, maneuver decision aims to make tactical decisions to accomplish road following, obstacle avoidance, and efficient driving. In this work, we consider a typical but rarely studied task, called Target-Lane-Entering (TLE), where an autonomous vehicle should enter a target lane before reaching an intersection to ensure a smooth transition to another road. For navigation-assisted autonomous driving, a maneuver decision module chooses the optimal timing to enter the target lane in each road section, thus avoiding rerouting and reducing travel time. To achieve the TLE task, we propose a ruLe-aided reINforcement lEarning framework, called LINE, which combines the advantages of RL-based policy and rule-based strategy, allowing the autonomous vehicle to make target-oriented maneuver decisions. Specifically, an RL-based policy with a hybrid reward function is able to make safe, efficient, and comfortable decisions while considering the factors of target lanes. Then a strategy of rule revision aims to help the policy learn from intervention and block the risk of missing target lanes. Extensive experiments based on the SUMO simulator confirm the effectiveness of our framework. The results show that LINE achieves state-of-the-art driving performance with over 95% task success rate.

With the proliferation of wireless and mobile devices, Spatial Crowdsourcing (SC) attracts increasing attention, where task assignment plays a critically important role. However, recent task assignment solutions in SC often assume that data is stored in a central station while ignoring the issue of privacy leakage. To enable decentralized training and privacy protection, we propose a federated task assignment framework with personalized location-preference learning, which performs efficient task assignment while keeping the data decentralized and private in each platform center (e.g., a delivery center of an SC company). The framework consists of two phases: personalized federated location-preference learning and task assignment. Specifically, in the first phase, we design a personalized location-preference learning model for each platform center by simultaneously considering the location information and data heterogeneity across platform centers. Based on workers' location preference, the task assignment phase aims to achieve effective and efficient task assignment by means of the Kuhn-Munkres (KM) algorithm and the newly proposed conditional degree-reduction algorithm. Extensive experiments on real-world data show the effectiveness of the proposed framework.

Autonomous driving is an emerging technology that has developed rapidly over the last decade. There have been numerous interdisciplinary challenges imposed on the current transportation system by autonomous vehicles. In this paper, we conduct an algorithmic study on the autonomous vehicle decision-making process, which is a fundamental problem in the vehicle automation field and the root cause of most traffic congestion. We propose a perception-and-decision framework, called HEAD, which consists of an enHanced pErception module and a mAneuver Decision module. HEAD aims to enable the autonomous vehicle to perform safe, efficient, and comfortable maneuvers with minimal impact on other vehicles. In the enhanced perception module, a graph-based state prediction model with a strategy of phantom vehicle construction is proposed to predict the one-step future states for multiple surrounding vehicles in parallel, which deals with sensor limitations such as limited detection range and poor detection accuracy under occlusions. Then in the maneuver decision module, a deep reinforcement learning-based model is designed to learn a policy for the autonomous vehicle to perform maneuvers in continuous action space w.r.t. a parameterized action Markov decision process. A hybrid reward function takes into account aspects of safety, efficiency, comfort, and impact to guide the autonomous vehicle to make optimal maneuver decisions. Extensive experiments offer evidence that HEAD can advance the state of the art in terms of both macroscopic and microscopic effectiveness.

The widespread use of positioning devices has given rise to many trajectories, with each having three explicit attributes: user ID, location ID, and time-stamp and an implicit attribute: activity type (akin to "topic" in text mining). To model these trajectories, existing works learn different attribute representations by either introducing latent activity types based on topic models or transforming the location and time context into a low-dimensional space via embedding techniques. In this paper, we propose a holistic approach named Human Mobility Representation Model (HMRM) to simultaneously produce the vector representations of all four (explicit and implicit) attributes. We evaluate HMRM on two real check-in datasets collected from Foursquare. Experimental results show that HMRM could not only improve the performance of capturing latent activity types, but also learn better trajectory embeddings.

Traffic prediction has drawn increasing attention due to its essential role in smart city applications. To achieve precise predictions, a large number of approaches have been proposed to model spatial dependencies and temporal dynamics. Despite their superior performance, most existing studies focus datasets that are usually in large geographic scales, e.g., citywide, while ignoring the results on specific regions. However, in many scenarios, for example, route planning on time-dependent road networks, only small regions are of interest. We name the task of answering forecasting requests from any query region of interest (ROI) as ROI-demand traffic prediction (RTP). In this paper, we make a primary observation that existing methods fail to jointly achieve effectiveness and efficiency for RTP. To address this issue, a novel model-agnostic framework based on pre-Training, Querying and fine-Tuning, named TQT, is proposed, which first customizes input data given an ROI, and then makes fast adaptation from pre-trained traffic prediction backbone models by fine-tuning. We evaluate TQT on two real-world traffic datasets, performing both flow and speed prediction tasks. Extensive experiment results demonstrate the effectiveness and efficiency of the proposed method.

Uncertainty is an essential consideration for time series forecasting tasks. In this work, we specifically focus on quantifying the uncertainty of traffic forecasting. To achieve this, we develop Deep Spatio-Temporal Uncertainty Quantification (DeepSTUQ), which can estimate both aleatoric and epistemic uncertainty. We first leverage a spatio-temporal model to model the complex spatio-temporal correlations of traffic data. Subsequently, two independent sub-neural networks maximizing the heterogeneous log-likelihood are developed to estimate aleatoric uncertainty. For estimating epistemic uncertainty, we combine the merits of variational inference and deep ensembling by integrating the Monte Carlo dropout and the Adaptive Weight Averaging re-training methods, respectively. Finally, we propose a post-processing calibration approach based on Temperature Scaling, which improves the model’s generalization ability to estimate uncertainty. Extensive experiments are conducted on four public datasets, and the empirical results suggest that the proposed method outperforms state-of-the-art methods in terms of both point prediction and uncertainty quantification.

Recommender systems aim at helping users to discover interesting items and assisting business owners to obtain more profits. Nonetheless, traditional recommendations fail to explore the varying importance of product characteristics for different product domains. In light of this, we propose a novel probabilistic model for recommendation, which could learn products’ characteristics in a fine-grained manner. Specifically, a user’s preference for a given product is modeled as a combination of visual and functional aspects. To make our method practical in large-scale industrial scenarios, we devise a computationally efficient learning algorithm to optimize VFPMF’s parameters. Experiments on four real-world datasets demonstrate the effectiveness and efficiency of our solution, compared with several state-of-the-art methods.

Recommender systems are able to learn user preferences based on user and item representations via their historical behaviors. To improve representation learning, recent recommendation models start leveraging information from various behavior types exhibited by users. In real-world scenarios, the user behavioral graph is not only multiplex but also dynamic, i.e., the graph evolves rapidly over time, with various types of nodes and edges added or deleted, which causes the Neighborhood Disturbance. Nevertheless, most existing methods neglect such streaming dynamics and thus need to be retrained once the graph has significantly evolved, making them unsuitable in the online learning environment. Furthermore, the Neighborhood Disturbance existing in dynamic graphs deteriorates the performance of neighbor-aggregation based graph models. To this end, we propose SUPA, a novel graph neural network for dynamic multiplex heterogeneous graphs. Compared to neighbor-aggregation architecture, SUPA develops a sample-update-propagate architecture to alleviate neighborhood disturbance. Specifically, for each new edge, SUPA samples an influenced subgraph, updates the representations of the two interactive nodes, and propagates the interaction information to the sampled subgraph. Furthermore, to train SUPA incrementally online, we propose InsLearn, an efficient workflow for single-pass training of large dynamic graphs. Extensive experimental results on six real-world datasets show that SUPA has a good generalization ability and is superior to sixteen state-of-the-art baseline methods. The source code is available at https://github.com/shatter15/SUPA.

A reliable autonomous driving system should take safe and efficient actions in constantly changing traffic. This requires the trajectory prediction model to continuously learn from incoming data and adapt to new scenarios. In the context of rapidly growing data volume, existing trajectory prediction models must retrain on all datasets to avoid forgetting previously learned knowledge when facing additional data from new environments. In contrast, the paradigm of continual learning solely necessitates training on new data, saving a significant amount of training overhead. Therefore, it is crucial to equip the trajectory prediction model with the ability of continual learning. In this paper, inspired by rehearsal and pseudo-rehearsal methods in continual learning, we propose a continual trajectory prediction framework with uncertainty-aware generative memory replay, CTP-UGR. Our framework effectively avoids excessive memory space requirements while generating trajectory data that is authentic, representative and discriminative for continual learning. Extensive experiments on two real-world datasets demonstrate our proposed CTP-UGR significantly outperforms other baselines in terms of both accuracy and catastrophic forgetting. Besides, our framework can be combined with other state-of-the-art trajectory prediction models to achieve better performance.

Query optimization is of great importance for the performance of a database, in which cardinality and cost estimation have a pivotal role. To enable accurate cardinality and cost estimation, we propose a novel framework based on bidirectional compressor and ensemble networks called BICE. In particular, we design a feature extractor composed of four sub-encoders, which can extract various types of information in a query plan tree and hybrid learning strategies for encoding. We encode joins based on a graph embedding method and design parallel networks for filters to improve the encoding efficiency. Then we propose a bidirectional LSTM-based compressor to learn the encoding and obtain fixed-length vectors, reducing the learning difficulty of the estimation model. Finally, we propose different data sampling strategies based on Bayesian neural networks and active learning, and an ensemble model is established based on transfer learning, which enables accurate estimation and adaptation to large-scale data queries. Extensive experiments offer insight into the effectiveness and efficiency of the proposed framework.

Due to the imbalanced nature of networked observational data, the causal effect predictions for some individuals can severely violate the positivity/overlap assumption, rendering unreliable estimations. Nevertheless, this potential risk of individual-level treatment effect estimation on networked data has been largely under-explored. To create a more trustworthy causal effect estimator, we propose the uncertainty-aware graph deep kernel learning (GraphDKL) framework with Lipschitz constraint to model the prediction uncertainty with Gaussian process and identify unreliable estimations. To the best of our knowledge, GraphDKL is the first framework to tackle the violation of positivity assumption when performing causal effect estimation with graphs. With extensive experiments, we demonstrate the superiority of our proposed method in uncertainty-aware causal effect estimation on networked data. The code of GraphDKL is available at https://github.com/uqhwen2/GraphDKL.

Graph Neural Networks (GNNs) have demonstrated promising results on exploiting node representations for many downstream tasks through supervised end-to-end training. To deal with the widespread label scarcity issue in real-world applications, Graph Contrastive Learning (GCL) is leveraged to train GNNs with limited or even no labels by maximizing the mutual information between nodes in its augmented views generated from the original graph. However, the distribution of graphs remains unconsidered in view generation, resulting in the ignorance of unseen edges in most existing literature, which is empirically shown to be able to improve GCL's performance in our experiments. To this end, we propose to incorporate graph generative adversarial networks (GANs) to learn the distribution of views for GCL, in order to i) automatically capture the characteristic of graphs for augmentations, and ii) jointly train the graph GAN model and the GCL model. Specifically, we present GACN, a novel Generative Adversarial Contrastive learning Network for graph representation learning. GACN develops a view generator and a view discriminator to generate augmented views automatically in an adversarial style. Then, GACN leverages these views to train a GNN encoder with two carefully designed self-supervised learning losses, including the graph contrastive loss and the Bayesian personalized ranking Loss. Furthermore, we design an optimization framework to train all GACN modules jointly. Extensive experiments on seven real-world datasets show that GACN is able to generate high-quality augmented views for GCL and is superior to twelve state-of-the-art baseline methods. Noticeably, our proposed GACN surprisingly discovers that the generated views in data augmentation finally conform to the well-known preferential attachment rule in online networks.

As an indispensable personalized service in Location-based Social Networks (LBSNs), the next Point-of-Interest (POI) recommendation aims to help people discover attractive and interesting places. Currently, most POI recommenders are based on the conventional centralized paradigm that heavily relies on the cloud to train the recommendation models with large volumes of collected users' sensitive check-in data. Although a few recent works have explored on-device frameworks for resilient and privacy-preserving POI recommendations, they invariably hold the assumption of model homogeneity for parameters/gradients aggregation and collaboration. However, users' mobile devices in the real world have various hardware configurations (e.g., compute resources), leading to heterogeneous on-device models with different architectures and sizes. In light of this, We propose a novel on-device POI recommendation framework, namely Model-Agnostic Collaborative learning for on-device POI recommendation (MAC), allowing users to customize their own model structures (e.g., dimension & number of hidden layers). To counteract the sparsity of on-device user data, we propose to pre-select neighbors for collaboration based on physical distances, category-level preferences, and social networks. To assimilate knowledge from the above-selected neighbors in an efficient and secure way, we adopt the knowledge distillation framework with mutual information maximization. Instead of sharing sensitive models/gradients, clients in MAC only share their soft decisions on a preloaded reference dataset. To filter out low-quality neighbors, we propose two sampling strategies, performance-triggered sampling and similarity-based sampling, to speed up the training process and obtain optimal recommenders. In addition, we design two novel approaches to generate more effective reference datasets while protecting users' privacy. Extensive experiments on two datasets have shown the superiority of MAC over advanced baselines.

Latent factor models are the most popular backbones for today's recommender systems owing to their prominent performance. Latent factor models represent users and items as real-valued embedding vectors for pairwise similarity computation, and all embeddings are traditionally restricted to a uniform size that is relatively large (e.g., 256-dimensional). With the exponentially expanding user base and item catalog in contemporary e commerce, this design is admittedly becoming memory-inefficient. To facilitate lightweight recommendation, reinforcement learning (RL) has recently opened up opportunities for identifying varying embedding sizes for different users/items. However, challenged by search efficiency and learning an optimal RL policy, existing RL-based methods are restricted to highly discrete, predefined embedding size choices. This leads to a largely overlooked potential of introducing finer granularity into embedding sizes to obtain better recommendation effectiveness under a given memory budget. In this paper, we propose continuous input embedding size search (CIESS), a novel RL-based method that operates on a continuous search space with arbitrary embedding sizes to choose from. In CIESS, we further present an innovative random walk-based exploration strategy to allow the RL policy to efficiently explore more candidate embedding sizes and converge to a better decision. CIESS is also model-agnostic and hence generalizable to a variety of latent factor RSs, whilst experiments on two real-world datasets have shown state-of-the-art performance of CIESS under different memory budgets when paired with three popular recommendation models.

Modern recommender systems often deal with a variety of user interactions, e.g., click, forward, purchase, etc., which requires the underlying recommender engines to fully understand and leverage multi-behavior data from users. Despite recent efforts towards making use of heterogeneous data, multi-behavior recommendation still faces great challenges. Firstly, sparse target signals and noisy auxiliary interactions remain an issue. Secondly, existing methods utilizing self-supervised learning (SSL) to tackle the data sparsity neglect the serious optimization imbalance between the SSL task and the target task. Hence, we propose a Multi-Behavior Self-Supervised Learning (MBSSL) framework together with an adaptive optimization method. Specifically, we devise a behavior-aware graph neural network incorporating the self-attention mechanism to capture behavior multiplicity and dependencies. To increase the robustness to data sparsity under the target behavior and noisy interactions from auxiliary behaviors, we propose a novel self-supervised learning paradigm to conduct node self-discrimination at both inter-behavior and intra-behavior levels. In addition, we develop a customized optimization strategy through hybrid manipulation on gradients to adaptively balance the self-supervised learning task and the main supervised recommendation task. Extensive experiments on five real-world datasets demonstrate the consistent improvements obtained by MBSSL over ten state-of-the-art (SOTA) baselines. We release our model implementation at: https://github.com/Scofield666/MBSSL.git.

In many complex systems, devices are typically monitored and generating massive multivariate time series. However, due to the complex patterns and little useful labeled data, it is a great challenge to detect anomalies from these time series data. Existing methods either rely on less regularizations, or require a large number of labeled data, leading to poor accuracy in anomaly detection. To overcome the limitations, in this paper, we propose an adversarial autoencoder anomaly detection and interpretation framework named DAEMON, which performs robustly for various datasets. The key idea is to use two discriminators to adversarially train an autoencoder to learn the normal pattern of multivariate time series, and thereafter use the reconstruction error to detect anomalies. The robustness of DAEMON is guaranteed by the regularization of hidden variables and reconstructed data using the adversarial generation method. An unsupervised approach used to detect anomalies is proposed. Moreover, in order to help operators better diagnose anomalies, DAEMON provides anomaly interpretation by computing the gradients of anomalous data. An extensive empirical study on real data offers evidence that the framework is capable of outperforming state-of-the-art methods in terms of the overall F1-score and interpretation accuracy for time series anomaly detection.

Trajectory-User Linking (TUL) aiming to identify users of anonymous trajectories, has recently received increasing attention due to its wide range of applications, such as criminal investigation and personalized recommendation systems. In this paper, we propose a flexible Semi-Supervised framework for Trajectory-User Linking, namely S2TUL, which includes five components: trajectory-level graph construction, trajectory relation modeling, location-level sequential modeling, a classification layer and greedy trajectory-user relinking. The first two components are proposed to model the relationships among trajectories, in which three homogeneous graphs and two heterogeneous graphs are firstly constructed and then delivered into the graph convolutional networks for converting the discrete identities to hidden representations. Since the graph constructions are irrelevant to the corresponding users, the unlabelled trajectories can also be included in the graphs, which enables the framework to be trained in a semi-supervised way. Afterwards, the location-level sequential modeling component is designed to capture fine-grained intra-trajectory information by passing the trajectories into the sequential neural networks. Finally, these two level representations are concatenated into a classification layer to predict the user of the input trajectory. In the testing phase, a greedy trajectory-user relinking method is proposed to assure the linking results satisfy the timespan overlap constraint. We conduct extensive experiments on three public datasets with six representative competitors. The evaluation results demonstrate the effectiveness of the proposed framework.

Learning fair and transferable representations of users that can be used for a wide spectrum of downstream tasks (specifically, machine learning models) has great potential in fairness-aware Web services. Existing studies focus on debiasing w.r.t. a small scale of (one or a handful of) fixed pre-defined sensitive attributes. However, in real practice, downstream data users can be interested in various protected groups and these are usually not known as prior. This requires the learned representations to be fair w.r.t. all possible sensitive attributes. We name this task universal fair representation learning, in which an exponential number of sensitive attributes need to be dealt with, bringing the challenges of unreasonable computational cost and un-guaranteed fairness constraints. To address these problems, we propose a controllable universal fair representation learning (CUFRL) method. An effective bound is first derived via the lens of mutual information to guarantee parity of the universal set of sensitive attributes while maintaining the accuracy of downstream tasks. We also theoretically establish that the number of sensitive attributes that need to be processed can be reduced from exponential to linear. Experiments on two public real-world datasets demonstrate CUFRL can achieve significantly better accuracy-fairness trade-off compared with baseline approaches.

Abstract Multi-key membership testing plays a crucial role in computing systems and networking applications, encompassing web search, mail systems, distributed databases, firewalls, and network routing. Traditional approaches, such as the Bloom filter, encounter limitations within this specific context. Addressing these challenges, we propose the Multi-key Learned Bloom Filter (MLBF), a hybrid method that combines machine learning techniques with the Bloom filter. The MLBF introduces a value-interaction-based multi-key classifier and a multi-key Bloom filter. Furthermore, we introduce an Interval-based MLBF approach, which categorizes keys into specific intervals based on data distribution to minimize the False Positive Rate (FPR). Additionally, MLBF incorporates an out-of-distribution (OOD) detection component to identify data shifts. Through extensive experimental evaluations on three authentic datasets, we demonstrate the superiority of the proposed MLBF in terms of FPR and query efficiency.

Query optimization has long been a fundamental yet challenging topic in the database field. With the prosperity of machine learning (ML), some recent works have shown the advantages of reinforcement learning (RL) based learned query optimizer. However, they suffer from fundamental limitations due to the data-driven nature of ML. Motivated by the ML characteristics and database maturity, we propose LEON -a framework for ML-aidEd query OptimizatioN. LEON improves the expert query optimizer to self-adjust to the particular deployment by leveraging ML and the fundamental knowledge in the expert query optimizer. To train the ML model, a pairwise ranking objective is proposed, which is substantially different from the previous regression objective. To help the optimizer to escape the local minima and avoid failure, a ranking and uncertainty-based exploration strategy is proposed, which discovers the valuable plans to aid the optimizer. Furthermore, an ML model-guided pruning is proposed to increase the planning efficiency without hurting too much performance. Extensive experiments offer evidence that the proposed framework can outperform the state-of-the-art methods in terms of end-to-end latency performance, training efficiency, and stability.

Some recent works have shown the advantages of reinforcement learning (RL) based learned query optimizers. These works often use the cost (i.e., the estimation of cost model) or the latency (i.e., execution time) as guidance signals for training their learned models. However, cost-based learning underperforms in latency and latency-based learning is time-intensive. In order to bypass such a dilemma, researchers attempt to transfer a learned value network from the cost domain to the latency domain. We recognize critical insights in cost/latency-based training, prompting us to transfer the reward function rather than the value network. Based on this idea, we propose a two-stage RL-based framework, BASE , to bridge the gap between cost and latency. After learning a policy based on cost signals in its first stage, BASE formulates transferring the reward function as a variant of inverse reinforcement learning. Intuitively, BASE learns to calibrate the reward function and updates the policy regarding the calibrated one in a mutually-improved manner. Extensive experiments exhibit the superiority of BASE on two benchmark datasets: Our optimizer outperforms traditional DBMS, using 30% less training time than SOTA methods. Meanwhile, our approach can enhance the efficiency of other learning-based optimizers.

An Attributed Dynamic Graph (ADG) contains multiple dynamic attributes associated with each edge in the graph, where people usually can specify multiple constraints in the attributes to illustrate their requirements, such as the total cost, the total travel time and the stopover interval of a flight between two cities. This inspires the Multi-Constrained Temporal Path (MCTP) discovery in ADGs, which is a challenging NP-Complete problem. The existing methods adopt Reinforcement Learning (RL) and Monte Carlo Tree Search (MCTS) in MCTP discovery. However, they require a certain degree of discovery experience to obtain better results, which can lead to the expensive cost of query time and storage space, and thus are not applicable in real-time applications. This motivates us to develop a new Adaptive Monte Carlo Tree Search algorithm (A-MCTS). A-MCTS dynamically adjusts the priority of historical records that are used in MCTS to improve the performance and reduce the size of required discovery experience. The experimental results on ten real-world dynamic graphs demonstrate that our proposed A-MCTS outperforms the state-of-the-art methods in terms of both efficiency and effectiveness.

Modeling heterogeneity by extraction and exploitation of high-order information from heterogeneous information networks (HINs) has been attracting immense research attention in recent times. Such heterogeneous network embedding (HNE) methods effectively harness the heterogeneity of small-scale HINs. However, in the real world, the size of HINs grow exponentially with the continuous introduction of new nodes and different types of links, making it a billion-scale network. Learning node embeddings on such HINs creates a performance bottleneck for existing HNE methods that are commonly centralized, i.e., complete data and the model are both on a single machine. To address large-scale HNE tasks with strong efficiency and effectiveness guarantee, we presentDecentralized Embedding Framework for Heterogeneous Information Network(DeHIN) in this paper. In DeHIN, we generate a distributed parallel pipeline that utilizes hypergraphs in order to infuse parallelization into the HNE task. DeHIN presents a context preserving partition mechanism that innovatively formulates a large HIN as a hypergraph, whose hyperedges connect semantically similar nodes. Our framework then adopts a decentralized strategy to efficiently partition HINs by adopting a tree-like pipeline. Then, each resulting subnetwork is assigned to a distributed worker, which employs the deep information maximization theorem to locally learn node embeddings from the partition it receives. We further devise a novel embedding alignment scheme to precisely project independently learned node embeddings from all subnetworks onto a common vector space, thus allowing for downstream tasks like link prediction and node classification. As shown from our experimental results, DeHIN significantly improves the efficiency and accuracy of existing HNE models as well as outperforms the large-scale graph embedding frameworks by efficiently scaling up to large-scale HINs.

Information network embedding is an important way to enable efficient graph analytics. However, it still faces with computational challenges in problems such as link prediction and node recommendation, particularly with the increasing scale of networks. Both hashing and quantization are promising approaches for accelerating these problems by orders of magnitude. In the preliminary work, we have proposed to learn binary codes for information networks, but graph analytics may suffer from large accuracy degradation. To reduce information loss while achieving memory and search efficiency, we further propose to learn quantized codes for information networks. In particular, each node is represented by compositing multiple latent vectors, each of which is optimally selected from a distinct set. Since (generalized) matrix factorization unifies several well-known embedding methods with high-order proximity preserved, we propose a \underline{N}etwork \underline{R}epresentation \underline{L}ightening framework based on \underline{M}atrix \underline{F}actorization (NRL-MF) to learn binary and quantized codes. We also propose an alternating optimization algorithm for efficient parameter learning, even for the generalized matrix factorization case. We finally evaluate NRL-MF on four real-world information network datasets with respect to the tasks of node classification and node recommendation. The results show that NRL-MF significantly outperforms competing baselines in both tasks, and that quantized representations indeed incur much smaller information loss than binarized codes.

Fastest route recommendation (FRR) is crucial for intelligent transportation systems. The existing methods treat it as a pathfinding problem on dynamic graphs, and extend A* algorithm with neuralized travel time estimators as cost functions. However, they fail to provide effective heuristic cost due to the neglect of its admissibility and the utilization of noise path information, resulting in sub-optimal results and inefficiency. Besides, path sequentiality is also ignored, affecting algorithm accuracy as well. In this paper, we propose a variational inference based fastest route recommendation method, which follows the framework of A* algorithm and provides effective costs for routing. Specifically, we first adopt a sequential estimator to accurately estimate the travel time of a specific path. More importantly, we design a variational inference based estimator, which models the distribution of travel time between two nodes and provides an effective heuristic cost with high probability of being admissible. We further take advantage of adversarial learning to enrich the fastest path information. To the best of our knowledge, we are the first to use variational estimator to consider the admissibility of heuristics in FRR. Extensive experiments are conducted on two real-world datasets. The results verify the performance advantage of our proposed method.

With the diffusion of online mobile devices with geo-location capabilities, the infrastructure necessary for real-world deployment of Spatial Crowdsourcing (SC), where so-called mobile workers are assigned location-sensitive tasks, is in place. Some SC tasks cannot be completed by a single worker due to their complexity, but rather must be assigned to and completed by a group of users. Achieving such group assignments that satisfy all group members evenly is an open challenge. To address this challenge, we propose a novel preference-aware group task assignment framework encompassing two components: Mutual Information-based Preference Modeling (MIPM) and Preference-aware Group Task Assignment (PGTA). The MIPM component learns the preferences of groups contrastively by maximizing the mutual information between workers and worker groups based on worker-task and group-task interaction data and by using an attention mechanism to weight group members adaptively. In addition, curriculum negative sampling is adopted to generate a small number of negative workers for each worker group, following the principles of curriculum learning. Next, the PGTA component offers an optimal task assignment algorithm that employs tree decomposition to assign tasks to appropriate worker groups, with the aim of maximizing the number of task assignments while prioritizing more interested groups when assigning tasks. The task assignment framework also features preference-constrained pruning of unpromising worker groups to speed up the assignment process. Finally, we report extensive experiments that offer evidence of the effectiveness and practicality of the paper's proposal.

The pervasiveness of GPS-enabled devices and wireless communication technologies flourish the market of Spatial Crowdsourcing (SC), which consists of location-based tasks and requires workers to be at specific locations physically to complete them. In this work, we study the problem of worker-churn-based task assignment in SC, where tasks are assigned by considering workers’ churn. In particular, we aim to maximize the total rewards of task assignments based on the worker churn prediction. To solve the problem, we propose a two-phase framework, which consists of a worker churn prediction and a task assignment phase. In the first phase, we use an LSTM-based model to extract latent feelings of workers based on historical data and then estimate idle time intervals of workers. In the assignment phase, we design an efficient greedy algorithm and a Kuhn-Munkras-based algorithm that can achieve the optimal task assignment. To improve the accuracy of the idle time interval estimation for workers, we adopt a context-dependent LSTM model, which involves interactions between inputs and their context. We further optimize the original task assignment framework by proposing a travel distance optimization strategy to reduce the overall travel distance. Extensive experiments offer insight into the effectiveness and efficiency of the proposed solutions.

In Spatial crowdsourcing, mobile users perform spatio-temporal tasks that involve travel to specified locations. Spatial crowdsourcing (SC) is enabled by SC platforms that support mobile worker recruitment and retention, as well as task assignment, which is essential to maximize profits that are accrued from serving task requests. Specifically, how to best achieve task assignment in a cost-effective manner while contending with spatio-temporal constraints is a key challenge in SC. To address this challenge, we formalize and study a novel Profit-driven Task Assignment problem. We first establish a task reward pricing model that takes into account the temporal constraints (i.e., expected completion time and deadline) of tasks. Then we adopt an optimal algorithm based on tree decomposition to achieve an optimal task assignment and propose greedy algorithms based on Random Tuning Optimization to improve the computational efficiency. To balance effectiveness and efficiency, we also provide a heuristic task assignment algorithm based on Ant Colony Optimization that assigns tasks by simulating behavior of ant colonies foraging for food. Finally, we conduct extensive experiments using real and synthetic data, offering detailed insight into effectiveness and efficiency of the proposed methods.

We consider a setting with an evolving set of requests for transportation from an origin to a destination before a deadline and a set of agents capable of servicing the requests. In this setting, an assignment authority is to assign agents to requests such that the average idle time of the agents is minimized. An example is the scheduling of taxis (agents) to meet incoming passenger requests for trips while ensuring that the taxis are empty as little as possible. In this paper, we study the problem of spatial-temporal demand forecasting and competitive supply (SOUP). We address the problem in two steps. First, we build a granular model that provides spatial-temporal predictions of requests. Specifically, we propose a Spatial-Temporal Graph Convolutional Sequential Learning (ST-GCSL) model that predicts the requests across locations and time slots. Second, we provide means of routing agents to request origins while avoiding competition among the agents. In particular, we develop a demand-aware route planning (DROP) algorithm that considers both the spatial-temporal predictions and the supply-demand state. We report on extensive experiments with real-world data that offer insight into the performance of the solution and show that it is capable of outperforming the state-of-the-art proposals.

Owing to its nature of scalability and privacy by design, federated learning (FL) has received increasing interest in decentralized deep learning. FL has also facilitated recent research on upscaling and privatizing personalized recommendation services, using on-device data to learn recommender models locally. These models are then aggregated globally to obtain a more performant model while maintaining data privacy. Typically, federated recommender systems (FRSs) do not take into account the lack of resources and data availability at the end-devices. In addition, they assume that the interaction data between users and items is i.i.d. and stationary across end-devices (i.e., users), and that all local recommender models can be directly averaged without considering the user’s behavioral diversity. However, in real scenarios, recommendations have to be made on end-devices with sparse interaction data and limited resources. Furthermore, users’ preferences are heterogeneous and they frequently visit new items. This makes their personal preferences highly skewed, and the straightforwardly aggregated model is thus ill-posed for such non-i.i.d. data. In this article, we propose Resource Efficient Federated Recommender System (ReFRS) to enable decentralized recommendation with dynamic and diversified user preferences. On the device side, ReFRS consists of a lightweight self-supervised local model built upon the variational autoencoder for learning a user’s temporal preference from a sequence of interacted items. On the server side, ReFRS utilizes a scalable semantic sampler to adaptively perform model aggregation within each identified cluster of similar users. The clustering module operates in an asynchronous and dynamic manner to support efficient global model update and cope with shifting user interests. As a result, ReFRS achieves superior performance in terms of both accuracy and scalability, as demonstrated by comparative experiments on real datasets.

Spatial crowdsourcing is one of the prime movers for the orchestration of location-based tasks, and task recommendation is a crucial means to help workers discover attractive tasks. While a number of existing studies have focused on modeling workers’ geographical preferences in task recommendation, they ignore the phenomenon of workers’ travel intention drifts across geographical areas, i.e., workers tend to have different intentions when they travel in different areas, which discounts the task recommendation quality of existing methods especially for workers that travel in unfamiliar out-of-town areas. To address this problem, we propose an Adaptive Task Recommendation ( AdaTaskRec ) framework. Specifically, we first give a novel two-module worker preference learning architecture that can calculate workers’ preferences for POIs (that tasks are associated with) in different areas adaptively based on workers’ current locations. If we detect that a worker is in the hometown area, then we apply the hometown preference learning module, which hybrids different strategies to aggregate workers’ travel intentions into their preferences while considering the transition and the sequence patterns among locations. Otherwise, we invoke the out-of-town preference learning module, which is to capture workers’ preferences by learning their travel intentions and transferring their hometown preferences into their out-of-town ones. Additionally, to improve task recommendation effectiveness, we propose a dynamic top- k recommendation method that sets different k values dynamically according to the numbers of neighboring workers and tasks. We also give an extra-reward-based and a fair top- k recommendation method, which introduce the extra rewards for tasks based on their recommendation rounds and consider exposure-based fairness of tasks, respectively. Extensive experiments offer insight into the effectiveness of the proposed framework.

Query cost estimation, which is to estimate the query plan cost and query execution cost, is of utmost importance to query optimizers. Query plan cost estimation heavily relies on accurate cardinality estimation, and query execution cost estimation gives good hints on query latency, both of which are challenging in database management systems. Despite decades of research, existing studies either over-simplify the models only using histograms and polynomial calculation that leads to inaccurate estimates, or over-complicate them by using cumbersome neural networks with the requirements for large amounts of training data hence poor computational efficiency. Besides, most of the studies ignore the diversity of query plan structures. In this work, we propose a plan-based query cost estimation framework, called Saturn, which can eStimate cardinality and latency accurately and efficiently, for any query plan structures. Saturn first encodes each query plan tree into a compressed vector by using a traversal-based query plan autoencoder to cope with diverse plan structures. The compressed vectors can be leveraged to distinguish different query types, which is highly useful for downstream tasks. Then a pseudo label generator is designed to acquire all cardinality and latency labels with the execution part of the query plans in the training workload, which can significantly reduce the overhead of collecting the real cardinality and latency labels. Finally, a chain-wise transfer learning module is proposed to estimate the cardinality and latency of the query plan in a pipeline paradigm, which further enhances the efficiency. An extensive empirical study on benchmark data offers evidence that Saturn outperforms the state-of-the-art proposals in terms of accuracy, efficiency, and generalizability for query cost estimation.

Trajectory prediction enables the fast and accurate response of autonomous driving navigation in complex and dense traffics. In this paper, we present a novel trajectory prediction network called Heterogeneous Graph Aggregation (HeGA) for high-density heterogeneous traffic, where the traffic agents of various categories interact densely with each other. To predict the trajectory of a target agent, HeGA first automatically selects neighbors that interact with it by our proposed adaptive neighbor selector, and then aggregates their interactions based on a novel two-phase aggregation transformer block. At last, the historical residual connection LSTM enhances the historical information awareness and decodes the spatial coordinates as the prediction results. Extensive experiments on real data demonstrate that the proposed network significantly outperforms the existing state-of-the-art competitors by over 27% on average displacement error (ADE) and over 31% on final displacement error (FDE). We also deploy HeGA in a state-of-the-art framework for autonomous driving, demonstrating its superior applicability based on three simulated environments with different densities and complexities.

The increasing proliferation of networked and geo-positioned mobile devices brings about increased opportunities for Spatial Crowdsourcing (SC), which aims to enable effective location-based task assignment. We propose and study a novel SC framework, namely Task Assignment with Task Publication Time Recommendation. The framework consists of two phases, task publication time recommendation and task assignment. More specifically, the task publication time recommendation phase hybrids different learning models to recommend the suitable publication time for each task to ensure the timely task assignment and completion while reducing the waiting time of the task requester at the SC platform. We use a cross-graph neural network to learn the representations of task requesters by integrating the obtained representations from two semantic spaces and utilize the self-attention mechanism to learn the representations of task-publishing sequences from multiple perspectives. Then a fully connected layer is used to predict suitable task publication time based on the obtained representations. In the task assignment phase, we propose a greedy and a minimum cost maximum flow algorithm to achieve the efficient and the optimal task assignment, respectively. An extensive empirical study demonstrates the effectiveness and efficiency of our framework.

The ubiquity of mobile devices and the accompanying deployment of sensing technologies have resulted in a massive amount of trajectory data. One important fundamental task is trajectory similarity computation, which is to determine how similar two trajectories are. To enable effective and efficient trajectory similarity computation, we propose a novel robust model, namely Contrastive Learning based Trajectory Similarity Computation (CL-TSim). Specifically, we employ a contrastive learning mechanism to learn the latent representations of trajectories and then calculate the dissimilarity between trajectories based on these representations. Compared with sequential auto-encoders that are the mainstream deep learning architectures for trajectory similarity computation, CL-TSim does not require a decoder and step-by-step reconstruction, thus improving the training efficiency significantly. Moreover, considering the non-uniform sampling rate and noisy points in trajectories, we adopt two type of augmentations, i.e., point dowm-sampling and point distorting, to enhance the robustness of the proposed model. Extensive experiments are conducted on two widely-used real-world datasets, i.e., Porto and ChengDu, which demonstrate the superior effectiveness and efficiency of the proposed model.

With the fast-paced development of mobile networks and the widespread usage of mobile devices, Spatial Crowdsourcing (SC) has drawn increasing attention in recent years. SC has the potential for collecting information for a broad range of applications such as on-demand local delivery and on-demand transportation. One of the critical issues in SC is task assignment that allocates location-based tasks (e.g., delivering food and packages) to appropriate moving workers (i.e., intelligent device carriers). In this paper, we study a loyalty-based task assignment problem, which aims to maximize the overall rewards of workers while considering worker loyalty. We propose a two-phase framework to solve the problem, including a worker loyalty prediction and a task assignment phase. In the first phase, we use a model based on an efficient time series prediction method called Prophet and an Entropy Weighting method to extract workers' short-term and long-term loyalty and then predict workers' current loyalty scores. In the task assignment phase, we design a Kuhn-Munkras-based algorithm that achieves the optimal task assignment and an efficient Degree-Reduction-based algorithm with minority first scheme. Extensive experiments offer insight into the effectiveness and efficiency of the proposed solutions.

Spatial Crowdsourcing (SC) is ubiquitous in the online world today. As we have transitioned from crowdsourcing applications (e.g., Wikipedia) to SC applications (e.g., Uber), there is a substantial precedent that SC systems have a responsibility not only to effective task assignment but also to privacy protection. To address these often-conflicting responsibilities, we propose a framework, Task Assignment with Federated Preference Learning, which performs task assignment based on worker preferences while keeping the data decentralized and private in each platform center (e.g., each delivery center of an SC company). The framework includes two phases, i.e., a federated preference learning and a task assignment phase. Specifically, in the first phase, we design a local preference model for each platform center based on historical data. Meanwhile, the horizontal federated learning with a client-server structure is introduced to collaboratively train these local preference models under the orchestration of a central server. The task assignment phase aims to achieve effective and efficient task assignment by considering workers' preferences. Extensive evaluations over real data show the effectiveness and efficiency of the paper's proposals.

Velocity control in autonomous driving is an emerging technology that has achieved rapid progress over the last decade. However, existing velocity control models are developed in single-lane scenarios and ignore the negative impacts caused by harsh velocity changes. In this work, we propose a velocity control framework based on reinforcement learning, called RISE (contRol velocIty for autonomouS vEhicle). In multi-lane circumstances, RISE improves velocity decisions regarding the autonomous vehicle itself, while minimizing impacts on rear vehicles. To achieve multiple objectives, we propose a hybrid reward function to rate each velocity decision from four aspects: safety, efficiency, comfort, and negative impact to guide the autonomous vehicle. Among these reward factors, the negative impact is used to penalize the harsh actions of the autonomous vehicle, thus prompting it to reduce the negative impacts on its rear vehicles. To detect the latent perturbations among surrounding vehicles in multiple lanes, we propose an attention-based encoder to learn the positions and interactions from an impact graph. Extensive experiments evidence that RISE enables safe driving, and outperforms state-of-the-art methods in efficiency, comfort, and alleviating negative impacts.

The proliferation of real-time monitoring applications such as Artificial Intelligence for IT Operations (AIOps) and the Internet of Things (IoT) has led to the generation of a vast amount of time-series data. To extract the underlying value of the data, both the industry and the academia are in dire need of efficient and effective methods for time-series analysis. To this end, in this paper, we propose a Multi-layer perceptron (MLP)-attention based multivariate time-series analysis model MARINA. MARINA is designed to simultaneously learn the temporal and spatial correlations among multivariate time-series. Also, the model is versatile in that it is suitable for major time-series analysis tasks such as forecasting and anomaly detection. Through extensive comparisons with the representative multivariate time-series forecasting and anomaly detection algorithms, MARINA is shown to achieve state-of-the-art (SOTA) performance in both forecasting and anomaly detection tasks.

With the widespread diffusion of smartphones, Spatial Crowdsourcing (SC), which aims to assign spatial tasks to mobile workers, has drawn increasing attention in both academia and industry. One of the major issues is how to best assign tasks to workers. Given a worker and a task, the worker will choose to accept the task based on her affinity towards the task, and the worker can propagate the information of the task to attract more workers to perform it. These factors can be measured as worker-task influence. Since workers' affinities towards tasks are different and task issuers may ask workers who performed tasks to propagate the information of tasks to attract more workers to perform them, it is important to analyze worker-task influence when making assignments. We propose and solve a novel influence-aware task assignment problem in SC, where tasks are assigned to workers in a manner that achieves high worker-task influence. In particular, we aim to maximize the number of assigned tasks and worker-task influence. To solve the problem, we first determine workers' affinities towards tasks by identifying workers' historical task-performing patterns. Next, a Historical Acceptance approach is developed to measure workers' willingness of performing a task, i.e., the probability of workers visiting the location of the task when they are informed. Next, we propose a Random reverse reachable-based Propagation Optimization algorithm that exploits reverse reachable sets to calculate the probability of workers being informed about tasks in a social network. Based on worker-task influence derived from the above three factors, we propose three influence-aware task assignment algorithms that aim to maximize the number of assigned tasks and worker-task influence. Extensive experiments on two real-world datasets offer detailed insight into the effectiveness of our solutions.

Time series data occurs widely, and outlier detection is a fundamental problem in data mining, which has numerous applications. Existing autoencoder-based approaches deliver state-of-the-art performance on challenging real-world data but are vulnerable to outliers and exhibit low explainability. To address these two limitations, we propose robust and explainable unsupervised auto encoder frameworks that decompose an input time series into a clean time series and an outlier time series using autoencoders. Improved explainability is achieved because clean time series are better explained with easy-to-understand patterns such as trends and periodicities. We provide insight into this by means of a post-hoc explainability analysis and empirical studies. In addition, since outliers are separated from clean time series iteratively, our approach offers improved robustness to outliers, which in turn improves accuracy. We evaluate our approach on five real-world datasets and report improvements over the state-of-the-art approaches in terms of robustness and explainability.

Hazardous chemicals transportation (HCT) brings significant financial, environmental, and health-related risks. It is imperative that a robust regulatory system is in place to reduce the risk of accidents occurring while such hazardous chemicals are being transported. Governments around the world use GPS sensors to monitor the raw trajectories of HCT trucks, but they have difficulty detecting the loaded trajectories, which is of utmost importance for the management of H CT processes. The loaded trajectory refers to the subtrajectory generated by tracking an HCT truck when it is loaded with hazardous chemical in an HCT process. The stay points in the raw trajectory provide some feasibility to detect the loaded trajectory as they reflect the potential loading and unloading actions of the HCT truck. However, directly using the stay points to detect the loaded trajectory usually leads to unsatisfactory results due to two chal-lenges: (1) complex staying scenarios, and (2) numerous loading and unloading locations. To tackle the challenges, we propose a LoadEd trAjectory Detectlon framework, called LEAD, to detect the loaded trajectory from the raw HCT trajectory accurately and efficiently. LEAD processes a raw trajectory into a set of candidate trajectories, encodes each candidate trajectory into a latent representation, and detects the loaded trajectory using the latent representations of candidate trajectories. Extensive experiments based on a real-world dataset from Nantong, China confirm the effectiveness of our framework. The results show that the detection accuracy of LEAD exceeds 83 % which outperforms competing baselines by over 42 %.

Join order selection plays an important role in DBMS query optimizers. The problem aims to find the optimal join order with the minimum cost, and usually becomes an NP-hard problem due to the exponentially increasing search space. Recent advanced studies attempt to use deep reinforcement learning (DRL) to generate better join plans than the ones provided by conventional query optimizers. However, DRL-based methods require time-consuming training, which is not suitable for online applications that need frequent periodic re-training. In this paper, we propose a novel framework, namely efficient Join Order selection learninG with Graph-basEd Representation (JOGGER). We firstly construct a schema graph based on the primary-foreign key relationships, from which table representations are well learned to capture the correlations between tables. The second component is the state representation, where a graph convolutional network is utilized to encode the query graph and a tailored-tree-based attention module is designed to encode the join plan. To speed up the convergence of DRL training process, we exploit the idea of curriculum learning, in which queries are incrementally added into the training set according to the level of difficulties. We conduct extensive experiments on JOB and TPC-H datasets, which demonstrate the effectiveness and efficiency of the proposed solutions.

Trajectory prediction is a fundamental problem for a wide spectrum of location-based applications. Existing methods can achieve inspiring results in predicting personal frequent routes conditioned on massive historical data. However, trajectory estimation may involve cold-start routes or users due to the data sparsity problem, which severely limits the performance of spatial trajectory prediction. Although meta-learning models can alleviate the cold-start problem, they simply utilize the same initialization for all tasks and thus cannot fit each user well due to users' varying travel preferences. To this end, we propose an adaptive meta-optimized model called MetaPTP for personalized spatial trajectory prediction. Specifically, it adopts a soft-clustering based method to guide the network initialization in a finer granularity, so that shared knowledge can be better transferred across users with similar travel preferences. Besides, towards model fine-tuning, an effective trajectory sampling method is introduced to generate meaningful support set, which simultaneously considers user preference and spatial trace similarities to provide task-related information for model adaptation. In addition, we design a weight generator to adaptively assign reasonable weights to trajectories in support set to avoid sub-optimal results which will occur when fine-tuning the initial network with the same weight for trajectories with different user preferences and spatial distributions. Finally, extensive experiments on two real-world datasets demonstrate the superiority of our model.

With the rapid development of mobile networks and the widespread usage of mobile devices, Location-Based Adver-tising (LBA), which allows an advertiser to promote products or services to targeted customers in a suitable location, has drawn increasing attention. Recommending an optimal location by delivering appealing advertisements to potential customers is crucial for the advertiser. Existing recommendation models (such as collaborative filtering) are insufficient for solving the data sparsity and cold-start issue (e.g., no historical advertisement records in new domains) in LBA problems. To tackle the defi-ciency mentioned above, we propose a novel location-based ad-vertising recommendation framework: CityCross. The CityCross framework consists of a data extraction module and a learning module. The data extraction module conducts commercial and POI feature extractions from the LBA platform, and Gaode Map, respectively. The learning module is dedicated to learning the relevant knowledge of advertisement in a new domain by utilizing the attention-based semantic information, cross-city knowledge association, and the local neighbors' knowledge. The top-k locations are identified by a modified linear regression model based on the learned knowledge. Finally, we conduct extensive experiments on two real datasets to verify the superiority of the proposed approach.

Crowdsourcing aims to enable the assignment of available resources to the completion of tasks at scale. The continued digitization of societal processes translates into increased opportunities for crowdsourcing. For example, crowdsourcing enables the assignment of computational resources of humans, called workers, to tasks that are notoriously hard for computers. In settings faced with malicious actors, detection of such actors holds the potential to increase the robustness of crowdsourcing platform. We propose a framework called Outlier Detection for Streaming Task Assignment that aims to improve robustness by detecting malicious actors. In particular, we model the arrival of workers and the submission of tasks as evolving time series and provide means of detecting malicious actors by means of outlier detection. We propose a novel socially aware Generative Adversarial Network (GAN) based architecture that is capable of contending with the complex distributions found in time series. The architecture includes two GANs that are designed to adversarially train an autoencoder to learn the patterns of distributions in worker and task time series, thus enabling outlier detection based on reconstruction errors. A GAN structure encompasses a game between a generator and a discriminator, where it is desirable that the two can learn to coordinate towards socially optimal outcomes, while avoiding being exploited by selfish opponents. To this end, we propose a novel training approach that incorporates social awareness into the loss functions of the two GANs. Additionally, to improve task assignment efficiency, we propose an efficient greedy algorithm based on degree reduction that transforms task assignment into a bipartite graph matching. Extensive experiments offer insight into the effectiveness and efficiency of the proposed framework.

Recommendation is prevalently studied for implicit feedback recently, but it seriously suffers from the lack of negative samples, which has a significant impact on the training of recommendation models. Existing negative sampling is based on the static or adaptive probability distributions. Sampling from the adaptive probability receives more attention, since it tends to generate more hard examples, to make recommender training faster to converge. However, item sampling becomes much more time-consuming particularly for complex recommendation models. In this paper, we propose an Adaptive Sampling method based on Importance Resampling (AdaSIR for short), which is not only almost equally efficient and accurate for any recommender models, but also can robustly accommodate arbitrary proposal distributions. More concretely, AdaSIR maintains a contextualized sample pool of fixed-size with importance resampling, from which items are only uniformly sampled. Such a simple sampling method can be proved to provide approximately accurate adaptive sampling under some conditions. The sample pool plays two extra important roles in (1) reusing historical hard samples with certain probabilities; (2) estimating the rank of positive samples for weighting, such that recommender training can concentrate more on difficult positive samples. Extensive empirical experiments demonstrate that AdaSIR outperforms state-of-the-art methods in terms of sampling efficiency and effectiveness.

Variational AutoEncoder (VAE) has been extended as a representative nonlinear method for collaborative filtering. However, the bottleneck of VAE lies in the softmax computation over all items, such that it takes linear costs in the number of items to compute the loss and gradient for optimization. This hinders the practical use due to millions of items in real-world scenarios. Importance sampling is an effective approximation method, based on which the sampled softmax has been derived. However, existing methods usually exploit the uniform or popularity sampler as proposal distributions, leading to a large bias of gradient estimation. To this end, we propose to decompose the inner-product-based softmax probability based on the inverted multi-index, leading to sublinear-time and highly accurate sampling. Based on the proposed proposals, we develop a fast Variational AutoEncoder (FastVAE) for collaborative filtering. FastVAE can outperform the state-of-the-art baselines in terms of both sampling quality and efficiency according to the experiments on three real-world datasets.

No abstract available.

No abstract available.

With the explosion of GPS-enabled smartphones and social media platforms, geo-social networks are increasing as tools for businesses to promote their products or services. Influence maximization, which aims to maximize the expected spread of influence in the networks, has drawn increasing attention. However, most recent work tries to study influence maximization by only considering geographic distance, while ignoring the influence of users’ spatio-temporal behavior on information propagation or location promotion, which can often lead to poor results. To relieve this problem, we propose a Similarity-aware Influence Maximization (SIM) model to efficiently maximize the influence spread by taking the effect of users’ spatio-temporal behavior into account, which is more reasonable to describe the real information propagation. We first calculate the similarity between users according to their historical check-ins, and then we propose a Propagation to Consumption (PTC) model to capture both online and offline behaviors of users. Finally, we propose two greedy algorithms to efficiently maximize the influence spread. The extensive experiments over real datasets demonstrate the efficiency and effectiveness of the proposed algorithms.

The widespread use of positioning devices has given rise to many trajectories, with each having three explicit attributes:user ID,location ID, andtime-stampand an implicit attribute:activity type(akin to “topic” in text mining). To model these trajectories, existing works learn different attribute representations by either introducing latent activity types based on topic models or transforming the location and time context into a low-dimensional space via embedding techniques. In this paper, we propose a holistic approach named Human Mobility Representation Model (HMRM) to simultaneously produce the vector representations of all four (explicit and implicit) attributes. The merits of HMRM lie in that: (1) it models the latent activity types and learns trajectory attribute embeddings in an integrated manner, and (2) it connects the activity-related distributions and these attributes embeddings by adding a newly designed collaborative learning component, and makes them mutually exchanged to take the best of both worlds. We apply HMRM to both unsupervised and supervised tasks including two activity evaluation tasks and two embedding evaluation tasks, on two real check-in datasets collected from Foursquare. Experimental results show that HMRM could not only improve the performance of capturing latent activity types, but also learn better trajectory embeddings.

The task of point of interest (POI) recommendation aims to recommend unvisited places to users based on their check-in history. A major challenge in POI recommendation is data sparsity, because a user typically visits only a very small number of POIs among all available POIs. In this paper, we propose AUC-MF to address the POI recommendation problem by maximizing Area Under the ROC curve (AUC). AUC has been widely used for measuring classification performance with imbalanced data distributions. To optimize AUC, we transform the recommendation task to a classification problem, where the visited locations are positive examples and the unvisited are negative ones. We define a new lambda for AUC to utilize the LambdaMF model, which combines the lambda-based method and matrix factorization model in collaborative filtering. Many studies have shown that geographic information plays an important role in POI recommendation. In this study, we focus on two levels geographic information: local similarity and global similarity. We further show that AUC-MF can be easily extended to incorporate geographical contextual information for POI recommendation. Specifically, we propose two novel methods to incorporate geographical information in AUC-MF. Different from most existing models where the contextual information are incorporated into the objective function, the incorporation of contextual information in AUC-MF is a refinement of the model and a sampling strategy. The sampling strategy could speedup convergence and the refining of recommendations is independent of training of the model. This mechanism also enables AUC-MF to be able produce recommendations refined towards different contextual information, with minimum computational cost. Experiments on two datasets show that the proposed AUC-MF outperforms state-of-the-art methods significantly in terms of recommendation accuracy.

One-class collaborative filtering (OCCF) problems are ubiquitous in real-world recommendation systems, such as news recommendation, but suffer from data sparsity and lack of negative items. To address the challenge, the state-of-the-art algorithm assigns uninteracted items with smaller weights of being negative and performs low-rank approximation over the user-item interaction matrix. However, the prior ratings are usually suggested to be zero but may not be well-defined. To avert the direct utilization of prior ratings for uninteracted items, we propose a novel ranking-based implicit regularizer by hypothesizing that users’ preference scores for uninteracted items should not deviate a lot from each other. The regularizer is then used in a ranking-based OCCF framework to penalize large differences of preference scores between uninteracted items. To efficiently optimize model parameters in this framework, we develop the scalable alternating least square algorithm and coordinate descent algorithm, whose time complexity is linearly proportional to the data size. Finally, we extensively evaluate the proposed algorithms on six public real-world datasets. The results show that the proposed regularizer significantly improves the recommendation quality of ranking-based OCCF algorithms, such as BPRMF and RankALS. Moreover, the ranking-based framework with the proposed regularizer outperforms the state-of-the-art recommendation algorithms for implicit feedback.

An effective recommender system can significantly help customers to find desired products and assist business owners to earn more income. Nevertheless, the decision-making process of users is highly complex, not only dependent on the personality and preference of a user, but also complicated by the characteristics of a specific product. For example, for products of different domains (e.g., clothing versus office products), the product aspects that affect a user’s decision are very different. As such, traditional collaborative filtering methods that model only user-item interaction data would deliver unsatisfactory recommendation results. In this work, we focus on fine-grained modeling of product characteristics to improve recommendation quality. Specifically, we first divide a product’s characteristics into visual and functional aspects—i.e., thevisual appearanceandfunctionalityof the product. One insight is that, the visual characteristic is very important for products of visually-aware domain (e.g., clothing), while the functional characteristic plays a more crucial role for visually non-aware domain (e.g., office products). We then contribute a novel probabilistic model, namedVisual and Functional Probabilistic Matrix Factorization(VFPMF), to unify the two factors to estimate user preferences on products. Nevertheless, such an expressive model poses efficiency challenge in parameter learning from implicit feedback. To address the technical challenge, we devise a computationally efficient learning algorithm based on alternating least squares. Furthermore, we provide an online updating procedure of the algorithm, shedding some light on how to adapt our method to real-world recommendation scenario where data continuously streams in. Extensive experiments on four real-word datasets demonstrate the effectiveness of our method with both offline and online protocols.

It has been an important task for recommender systems to suggest satisfying activities to a group of users in peoples daily social life. The major challenge in this task is how to aggregate personal preferences of group members to infer the decision of a group. In this paper, we propose a novel end-to-end group recommender system named CAGR (short for Centrality-Aware Group Recommender), which takes the Bipartite Graph Embedding Model (BGEM), the self-attention mechanism and Graph Convolutional Networks (GCNs) as basic building blocks to learn group and user representations in a unified way. Specifically, we first extend BGEM to model group-item interactions, and then in order to overcome the sparsity of the interaction data generated by occasional groups, we propose a self-attentive mechanism to represent groups based on the group members. To further alleviate the group data sparsity problem, we propose two model optimization approaches to exploit an and integrate the user-item interaction data. To overcome the sparsity issue of user-item interaction data, we extend GCNs to leverage the social network to enhance user representation learning. We create two large-scale benchmark datasets and conduct extensive experiments on them. The experimental results show the superiority of our proposed CAGR.

With the ubiquity of smart devices, Spatial Crowdsourcing (SC) has emerged as a new transformative platform that engages mobile users to perform spatio-temporal tasks by physically traveling to specified locations. Thus, various SC techniques have been studied for performance optimization, among which one of the major challenges is how to assign workers the tasks that they are really interested in and willing to perform. In this paper, we propose a novel preference-aware spatial task assignment system based on workers’ temporal preferences, which consists of two components:History-based Context-aware Tensor Decomposition (HCTD) for workers’ temporal preferences modelingandpreference-aware task assignment. We model workers’ preferences with a three-dimension tensor (worker-task-time). Supplementing the missing entries of the tensor through HCTD with the assistant of historical data and other two context matrices, we recover workers’ preferences for different categories of tasks in different time slots. Several preference-aware individual task assignment algorithms are then devised, aiming to maximize the total number of task assignments at every time instance, in which we give higher priorities to the workers who are more interested in the tasks. In order to make our proposed framework applicable to more scenarios, we further optimize the original framework by proposing strategies to allow each task to be assigned to a group of workers such that the task can be completed by these workers simultaneously, wherein workers’ tolerable waiting time, consensus, and tasks’ rewards are taken into consideration. We conduct extensive experiments using a real dataset, verifying the practicability of our proposed methods.

Accurately recommending the next point of interest (POI) has become a fundamental problem with the rapid growth of location-based social networks. However, sparse, imbalanced check-in data and diverse user check-in patterns pose severe challenges for POI recommendation tasks. Knowledge-aware models are known to be primary in leveraging these problems. However, as most knowledge graphs are constructed statically, sequential information is yet integrated. In this work, we propose a meta-learned sequential-knowledge-aware recommender (Meta-SKR), which utilizes sequential, spatio-temporal, and social knowledge to recommend the next POI for a location-based social network user. The framework mainly contains four modules. First, in the graph construction module, a novel type of knowledge graph—the sequential knowledge graph, which is sensitive to the check-in order of POIs—is built to model users’ check-in patterns. To deal with the problem of data sparsity, a meta-learning module based on latent embedding optimization is then introduced to generate user-conditioned parameters of the subsequent sequential-knowledge-aware embedding module, where representation vectors of entities (nodes) and relations (edges) are learned. In this embedding module, gated recurrent units are adapted to distill intra- and inter-sequential knowledge graph information. We also design a novel knowledge-aware attention mechanism to capture information surrounding a given node. Finally, POI recommendation is provided by inferring potential links of knowledge graphs in the prediction module. Evaluations on three real-world check-in datasets show that Meta-SKR can achieve high recommendation accuracy even with sparse data.

Group recommendation aims to recommend items to a group of users. In this work, we study group recommendation in a particular scenario, namely occasional group recommendation, where groups are formed ad hoc and users may just constitute a group for the first time—that is, the historical group-item interaction records are highly limited. Most state-of-the-art works have addressed the challenge by aggregating group members’ personal preferences to learn the group representation. However, the representation learning for a group is most complex beyond the aggregation or fusion of group member representation, as the personal preferences and group preferences may be in different spaces and even orthogonal. In addition, the learned user representation is not accurate due to the sparsity of users’ interaction data. Moreover, the group similarity in terms of common group members has been overlooked, which, however, has the great potential to improve the group representation learning. In this work, we focus on addressing the aforementioned challenges in the group representation learning task, and devise a hierarchical hyperedge embedding-based group recommender, namely HyperGroup. Specifically, we propose to leverage the user-user interactions to alleviate the sparsity issue of user-item interactions, and design a graph neural network-based representation learning network to enhance the learning of individuals’ preferences from their friends’ preferences, which provides a solid foundation for learning groups’ preferences. To exploit the group similarity (i.e., overlapping relationships among groups) to learn a more accurate group representation from highly limited group-item interactions, we connect all groups as a network of overlapping sets (a.k.a. hypergraph), and treat the task of group preference learning as embedding hyperedges (i.e., user sets/groups) in a hypergraph, where an inductive hyperedge embedding method is proposed. To further enhance the group-level preference modeling, we develop a joint training strategy to learn both user-item and group-item interactions in the same process. We conduct extensive experiments on two real-world datasets, and the experimental results demonstrate the superiority of our proposed HyperGroup in comparison to the state-of-the-art baselines.

Long sequence time-series forecasting (LSTF) has become increasingly popular for its wide range of applications. Though superior models have been proposed to enhance the prediction effectiveness and efficiency, it is reckless to neglect or underestimate one of the most natural and basic temporal properties of time series: history has inertia. In this paper, we introduce a new baseline for LSTF, named historical inertia (HI). In HI, the most recent historical data points in the input time series are adopted as the prediction results. We experimentally evaluate HI on 4 public real-world datasets and 2 LSTF tasks. The results demonstrate that up to 82% relative improvement over state-of-the-art works can be achieved. We further discuss why HI works and potential ways of benefiting from it.

The ongoing COVID-19 pandemic has dramatically changed people's daily lives. A robust forecasting model for COVID-19 infections is essential for governments and institutions to plan timely and perform accurate interventions. Mainstream solutions for COVID-19 prediction fit reported data only by considering observed cases. However, the neglected facts that positive samples are incomplete and many facts of the novel disease are unknown may be prone to cause severe error accumulation, especially in long-term predictions. To fully understand the spreading patterns of the virus, we propose an encoder-decoder framework: (i) in the encoder we embed historical case data into multiple expose-infection ranges and learn message passing between time slices and across ranges with coarse-grained human mobility data incorporated; (ii) in the decoder, we decode the embedded features based on reported cases as well as deaths to jointly consider the effect of both observed and hidden data. We model the spreading of disease in over 60 counties of California and New York, which are two of the most metropolitan areas in the US. The proposed framework significantly outperforms state-of-the-art baselines on JHU COVID-19 dataset on both weekly prediction and daily prediction tasks. We design detailed ablation studies to verify the effectiveness of each key module and find the model not only works with the assistance of mobility data but also with purely cases and deaths, which implies its broad application scenarios.

Human mobility recovery is of great importance for a wide range of location-based services. However, recovering human mobility is not trivial because of three challenges: 1) complex transition patterns among locations; 2) multi-level periodicity and shifting periodicity of human mobility; 3) sparsity of the collected trajectory data. In this paper, we propose PeriodicMove, a neural attention model based on graph neural network for human mobility recovery from lengthy and sparse trajectories. In PeriodicMove, we first construct a directed graph for each trajectory and capture complex location transition patterns using graph neural network. Then, we design two attention mechanisms which capture multi-level periodicity and shifting periodicity of human mobility respectively. Finally, a spatial-aware loss function is proposed to incorporate spatial proximity into the model optimization, which alleviates the data sparsity problem. We perform extensive experiments and the evaluation results demonstrate that PeriodicMove yields significant improvements over the competitors on two representative real-life mobility datasets. In addition, by providing high-quality mobility data, our model can benefit a variety of mobility-oriented downstream applications.

The pervasiveness of GPS-enabled devices and wireless communication technologies flourish the market of Spatial Crowdsourcing (SC), which consists of location-based tasks and requires workers to physically be at specific locations to complete them. In this work, we study the problem of Worker Churn based Task Assignment in SC, where tasks are to be assigned by considering workers' churn. In particular, we aim to achieve the highest total rewards of task assignments based on the worker churn prediction. To solve the problem, we propose a two-phase framework, which consists of a worker churn prediction phase and a task assignment phase. In the first phase, we use an LSTM-based model to extract the latent feelings of workers based on the historical data and then estimate the idle time intervals of workers. In the assignment phase, we design an efficient greedy algorithm and a Kuhn-Munkras (KM)-based algorithm that can achieve the optimal task assignment. Extensive experiments offer insight into the effectiveness and efficiency of the proposed solutions.

The largest portion of urban congestion is caused by 'phantom' traffic jams, causing significant delay travel time, fuel waste, and air pollution. It frequently occurs in high-density traffics without any obvious signs of accidents or roadworks. The root cause of 'phantom' traffic jams in one-lane traffics is the sudden change in velocity of some vehicles (i.e. harsh driving behavior (HDB)), which may generate a chain reaction with accumulated impact throughout the vehicles along the lane. This paper makes the first attempt to address this notorious problem in a one-lane traffic environment through velocity control of autonomous vehicles. Specifically, we propose a velocity control framework, called PATROL (sPAtial-temporal ReinfOrcement Learning). First, we design a spatial-temporal graph inside the reinforcement learning model to process and extract the information (e.g. velocity and distance difference) of multiple vehicles ahead across several historical time steps in the interactive environment. Then, we propose an attention mechanism to characterize the vehicle interactions and an LSTM structure to understand the vehicles' driving patterns through time. At last, we modify the reward function used in previous velocity control works to enable the autonomous driving agent to predict the HDB of preceding vehicles and smoothly adjust its velocity, which could alleviate the chain reaction caused by HDB. We conduct extensive experiments to demonstrate the effectiveness and superiority of PATROL in alleviating the 'phantom' traffic jam in simulation environments. Further, on the real-world velocity control dataset, our method significantly outperforms the existing methods in terms of driving safety, comfortability, and efficiency.

Recent years have witnessed a revolution in Spatial Crowdsourcing (SC), in which people with mobile connectivity can perform spatio-temporal tasks that involve travel to specified locations. In this paper, we identify and study in depth a new multi-center-based task allocation problem in the context of SC, where multiple allocation centers exist. In particular, we aim to maximize the total number of the allocated tasks while minimizing the average allocated task number difference. To solve the problem, we propose a two-phase framework, called Task Allocation with Geographic Partition, consisting of a geographic partition phase and a task allocation phase. The first phase is to divide the whole study area based on the allocation centers by using both a basic Voronoi diagram-based algorithm and an adaptive weighted Voronoi diagram-based algorithm. In the allocation phase, we utilize a Reinforcement Learning method to achieve the task allocation, where a graph neural network with the attention mechanism is used to learn the embeddings of allocation centers, delivery points and workers. Extensive experiments give insight into the effectiveness and efficiency of the proposed solutions.

In many complex systems, devices are typically monitored and generating massive multivariate time series. However, due to the complex patterns and little useful labeled data, it is a great challenge to detect anomalies from these time series data. Existing methods either rely on less regularizations, or require a large number of labeled data, leading to poor accuracy in anomaly detection. To overcome those limitations, in this paper, we propose an unsupervised anomaly detection framework, called DAEMON (Adversarial Autoencoder Anomaly Detection Interpretation), which performs robustly for various datasets. The key idea is to use two discriminators to adversarially train an autoencoder to learn the normal pattern of multivariate time series, and thereafter use the reconstruction error to detect anomalies. The robustness of DAEMON is guaranteed by the regularization of hidden variables and reconstructed data using the adversarial generation method. Moreover, in order to help operators better diagnose anomalies, DAEMON provides anomaly interpretation based on the reconstruction error of the constituent univariate time series. Experiment results on four real datasets show that DAEMON can achieve an overall F1-score of 0.94, outperforming state-of-the-art methods. In addition, the anomaly interpretation accuracy of DAEMON can achieve 97%.

Learning vector representations (i.e., embeddings) of nodes for graph-structured information network has attracted vast interest from both industry and academia. Most real-world networks exhibit a complex and heterogeneous format, enclosing high-order relationships and rich semantic information among nodes. However, existing heterogeneous network embedding (HNE) frameworks are commonly designed in a centralized fashion, i.e., all the data storage and learning process take place on a single machine. Hence, those HNE methods show severe performance bottlenecks when handling large-scale networks due to high consumption on memory, storage, and running time. In light of this, to cope with large-scale HNE tasks with strong efficiency and effectiveness guarantee, we propose Decentralized Deep Heterogeneous Hypergraph (DDHH) embedding framework in this paper. In DDHH, we innovatively formulate a large heterogeneous network as a hypergraph, where its hyperedges can connect a set of semantically similar nodes. Our framework then intelligently partitions the heterogeneous network using the identified hyperedges. Then, each resulted subnetwork is assigned to a distributed worker, which employs the deep information maximization theorem to locally learn node embeddings from the partition received. We further devise a novel embedding alignment scheme to precisely project independently learned node embeddings from all subnetworks onto a public vector space, thus allowing for downstream tasks. As shown from our experimental results, DDHH significantly improves the efficiency and accuracy of existing HNE models, and can easily scale up to large-scale heterogeneous networks.

With the fast-paced development of mobile networks and the widespread usage of mobile devices, Spatial Crowdsourcing (SC), which refers to assigning location-based tasks to moving workers, has drawn increasing attention in recent years. One of the critical issues in SC is task assignment that allocates tasks to appropriate workers. In this paper, we propose a novel SC problem, namely Coalition-based Task Assignment (CTA), where the spatial tasks (e.g., house removals, furniture installation) may require more than one workers (forming a coalition) to cooperate in order to maximize the overall rewards of workers. To tackle the CTA problem, we design both greedy method and equilibrium-based method. In particular, the greedy method aims to form a set of worker coalitions greedily to perform the tasks, in which we introduce an acceptance possibility to find the high-value task assignments. In the equilibrium-based algorithm, workers form coalitions in sequence and update their strategy (i.e., selecting a best-response task) at their turn, in order to maximize their own utility (i.e., reward of the coalition they stay in) until Nash equilibrium is reached. Since the equilibrium point obtained by the best-response approach is not unique and optimal in terms of total rewards, we further propose a simulated annealing scheme to find a better Nash equilibrium. The extensive experiments demonstrate the efficiency and effectiveness of the proposed methods on both real and synthetic datasets.

The widespread diffusion of smartphones offers a capable foundation for the deployment of Spatial Crowdsourcing (SC), where mobile users, called workers, perform location- dependent tasks assigned to them. A key issue in SC is how best to assign tasks, e.g., the delivery of food and packages, to appropriate workers. Specifically, we study the problem of Fairness-aware Task Assignment (FTA) in SC, where tasks are to be assigned in a manner that achieves some notion of fairness across workers. In particular, we aim to minimize the payoff difference among workers while maximizing the average worker payoff. To solve the problem, we first generate so-called Valid Delivery Point Sets (VDPSs) for each worker according to an approach that exploits dynamic programming and distance- constrained pruning. Next, we show that FTA is NP-hard and proceed to propose two heuristic algorithms, a Fairness-aware Game-Theoretic (FGT) algorithm and an Improved Evolutionary Game-Theoretic (IEGT) algorithm. More specifically, we formulate FTA as a multi-player game. In this setting, the FGT approach represents a best-response method with sequential and asynchronous updates of workers' strategies, given by the VDPSs, that achieves a satisfying task assignment when a pure Nash equilibrium is reached. Next, the IEGT approach considers a setting with a large population of workers that repeatedly engage in strategic interactions. The IEGT approach exploits replicator dynamics that cause the whole population to evolve and choose better resources, i.e., VDPSs. Using the property of evolutionary equilibrium, a satisfying task assignment is obtained that corresponds to a stable state with similar payoffs among workers and good average worker payoff. Extensive experiments offer insight into the effectiveness and efficiency of the proposed solutions.

With the popularity of GPS-enable smart devices and the development of wireless network, Spatial Crowdsourcing (SC), as a framework for assigning location-sensitive tasks to moving workers, has received wide attention in recent years. In real-world scenarios, some complex tasks exist that may not be completed by a single worker. In this case, the tasks are often assigned to multiple workers, which is called group task assignment. However, the assignment of tasks that satisfy all group members in an even way remains a challenge. To this end, we propose a novel preference-aware group task assignment framework that includes two components: Mutual Information-based Preference Modeling (MIPM) and Preference-aware Group Task Assignment (PGTA). Specifically, MIPM learns the preferences of worker groups by maximizing the mutual information among workers based on the worker-task interaction data and the group-task interaction data, where an attention mechanism is used. PGTA adopts an optimal task assignment algorithm based on tree decomposition to assign tasks to appropriate worker groups, which aims to maximize the overall number of assigned tasks while giving priority to the groups of workers that are more interested in the tasks. Finally, extensive experiments are conducted, verifying the effectiveness and practicality of the proposed solutions.

Automation in road vehicles is an emerging technology that has developed rapidly over the last decade. There have been many inter-disciplinary challenges posed on existing transportation infrastructure by autonomous vehicles (AV). In this paper, we conduct an algorithmic study on when and how an autonomous vehicle should change its lane, which is a fundamental problem in vehicle automation field and root cause of most 'phantom' traffic jams. We propose a prediction-and-search framework, called Cheetah (Change lane smart for autonomous vehicle), which aims to optimize the lane changing maneuvers of autonomous vehicle while minimizing its impact on surrounding vehicles. In the prediction phase, Cheetah learns the spatio-temporal dynamics from historical trajectories of surrounding vehicles with a deep model (GAS-LED) and predict their corresponding actions in the near future. A global attention mechanism and state sharing strategy are also incorporated to achieve higher accuracy and better convergence efficiency. Then in the search phase, Cheetah looks for optimal lane change maneuvers for the autonomous vehicle by taking into account a few factors such as speed, impact on other vehicles and safety issues. A tree-based adaptive beam search algorithm is designed to reduce the search space and improve accuracy. Extensive experiments on real and synthetic data evidence that the proposed framework excels state-of-the-art competitors with respect to both effectiveness and efficiency.

Conversational recommender systems (CRSs) have revolutionized the conventional recommendation paradigm by embracing dialogue agents to dynamically capture the fine-grained user preference. In a typical conversational recommendation scenario, a CRS firstly generates questions to let the user clarify her/his demands and then makes suitable recommendations. Hence, the ability to generate suitable clarifying questions is the key to timely tracing users' dynamic preferences and achieving successful recommendations. However, existing CRSs fall short in asking high-quality questions because: (1) system-generated responses heavily depends on the performance of the dialogue policy agent, which has to be trained with huge conversation corpus to cover all circumstances; and (2) current CRSs cannot fully utilize the learned latent user profiles for generating appropriate and personalized responses.

Advertising creatives are ubiquitous in E-commerce advertisements and aesthetic creatives may improve the click-through rate (CTR) of the products. Nowadays smart advertisement platforms provide the function of compositing creatives based on source materials provided by advertisers. Since a great number of creatives can be generated, it is difficult to accurately predict their CTR given a limited amount of feedback. Factorization machine (FM), which models inner product interaction between features, can be applied for the CTR prediction of creatives. However, interactions between creative elements may be more complex than the inner product, and the FM-estimated CTR may be of high variance due to limited feedback. To address these two issues, we propose an Automated Creative Optimization (AutoCO) framework to model complex interaction between creative elements and to balance between exploration and exploitation. Specifically, motivated by AutoML, we propose one-shot search algorithms for searching effective interaction functions between elements. We then develop stochastic variational inference to estimate the posterior distribution of parameters based on the reparameterization trick, and apply Thompson Sampling for efficiently exploring potentially better creatives. We evaluate the proposed method with both a synthetic dataset and two public datasets. The experimental results show our method can outperform competing baselines with respect to cumulative regret. The online A/B test shows our method leads to a 7% increase in CTR compared to the baseline.

With the sweeping digitalization of societal, medical, industrial, and scientific processes, sensing technologies are being deployed that produce increasing volumes of time series data, thus fueling a plethora of new or improved applications. In this setting, outlier detection is frequently important, and while solutions based on neural networks exist, they leave room for improvement in terms of both accuracy and efficiency. With the objective of achieving such improvements, we propose a diversity-driven, convolutional ensemble. To improve accuracy, the ensemble employs multiple basic outlier detection models built on convolutional sequence-to-sequence autoencoders that can capture temporal dependencies in time series. Further, a novel diversity-driven training method maintains diversity among the basic models, with the aim of improving the ensemble's accuracy. To improve efficiency, the approach enables a high degree of parallelism during training. In addition, it is able to transfer some model parameters from one basic model to another, which reduces training time. We report on extensive experiments using real-world multivariate time series that offer insight into the design choices underlying the new approach and offer evidence that it is capable of improved accuracy and efficiency.

Multivariate time series forecasting has been drawing increasing attention due to its prevalent applications. It has been commonly assumed that leveraging latent dependencies between pairs of variables can enhance prediction accuracy. However, most existing methods suffer from static variable relevance modeling and ignorance of correlation between temporal scales, thereby failing to fully retain the dynamic and periodic interdependencies among variables, which are vital for long- and short-term forecasting. In this paper, we propose METRO, a generic framework with multi-scale temporal graphs neural networks, which models the dynamic and cross-scale variable correlations simultaneously. By representing the multivariate time series as a series of temporal graphs, both intra- and inter-step correlations can be well preserved via message-passing and node embedding update. To enable information propagation across temporal scales, we design a novel sampling strategy to align specific steps between higher and lower scales and fuse the cross-scale information efficiently. Moreover, we provide a modular interpretation of existing GNN-based time series forecasting works as specific instances under our framework. Extensive experiments conducted on four benchmark datasets demonstrate the effectiveness and efficiency of our approach. METRO has been successfully deployed onto the time series analytics platform of Huawei Cloud, where a one-month online test demonstrated that up to 20% relative improvement over state-of-the-art models w.r.t. RSE can be achieved.

Mobility prediction plays an important role in a wide range of location-based applications and services. However, there are three problems in the existing literature: (1) explicit high-order interactions of spatio-temporal features are not systemically modeled; (2) most existing algorithms place attention mechanisms on top of recurrent network, so they can not allow for full parallelism and are inferior to self-attention for capturing long-range dependence; (3) most literature does not make good use of long-term historical information and do not effectively model the long-term periodicity of users. To this end, we propose MoveNet and RLMoveNet. MoveNet is a self-attention-based sequential model, predicting each user’s next destination based on her most recent visits and historical trajectory. MoveNet first introduces a cross-based learning framework for modeling feature interactions. With self-attention on both the most recent visits and historical trajectory, MoveNet can use an attention mechanism to capture the user’s long-term regularity in a more efficient way. Based on MoveNet, to model long-term periodicity more effectively, we add the reinforcement learning layer and named RLMoveNet. RLMoveNet regards the human mobility prediction as a reinforcement learning problem, using the reinforcement learning layer as the regularization part to drive the model to pay attention to the behavior with periodic actions, which can help us make the algorithm more effective. We evaluate both of them with three real-world mobility datasets. MoveNet outperforms the state-of-the-art mobility predictor by around 10% in terms of accuracy, and simultaneously achieves faster convergence and over 4x training speedup. Moreover, RLMoveNet achieves higher prediction accuracy than MoveNet, which proves that modeling periodicity explicitly from the perspective of reinforcement learning is more effective.

The join operations, including both equi and non-equi joins, are essential to the complex data analytics in the big data era. However, they are not inherently supported by existing DSPEs (Distributed Stream Processing Engines). The state-of-the-art join solutions on DSPEs rely on either complicated routing strategies or resource-inefficient processing structures, which are susceptible to dynamic workload, especially when the DSPEs face various join predicate operations and skewed data distribution. In this paper, we propose a new cost-effective stream join framework, named A-DSP (Adaptive Dimensional Space Processing), which enhances the adaptability of real-time join model and minimizes the resource used over the dynamic workloads. Our proposal includes: 1) a join model generation algorithm devised to adaptively switch between different join schemes so as to minimize the number of processing task required; 2) a load-balancing mechanism which maximizes the processing throughput; and 3) a lightweight algorithm designed for cutting down unnecessary migration cost. Extensive experiments are conducted to compare our proposal against state-of-the-art solutions on both benchmark and real-world workloads. The experimental results verify the effectiveness of our method, especially on reducing the operational cost under pay-as-you-go pricing scheme.

Recently accumulated massive amounts of geo-tagged photos provide an excellent opportunity to understand human behaviors and can be used for personalized tour recommendation. However, no existing work has considered the visual content information in these photos for tour recommendation. We believe the visual features of photos provide valuable information on measuring user / Point-of-Interest (POI) similarities, which is challenging due to data sparsity. To this end, in this paper, we propose a visual feature enhanced tour recommender system, named ‘Photo2Trip’, to utilize the visual contents and collaborative filtering models for recommendation. Specifically, we propose a Visual-enhanced Probabilistic Matrix Factorization model (VPMF), which integrates visual features into the collaborative filtering model, to learn user interests by leveraging the historical travel records. We then extend VPMF to End-to-End training framework to incorporate users (POIs) latent factors into the learning process of the visual content of photos, which generalizes the applicability of the proposed VPMF framework in tour recommendation. Extensive empirical studies verify that our proposed visual-enhanced personalized tour recommendation method outperforms other benchmark methods in terms of recommendation accuracy. The results also show that visual features are effective in alleviating the data sparsity and cold start problems on personalized tour recommendation.

Recommender systems have shown great potential to solve the information explosion problem and enhance user experience in various online applications. To tackle data sparsity and cold start problems in recommender systems, researchers propose knowledge graphs (KGs) based recommendations by leveraging valuable external knowledge as auxiliary information. However, most of these works ignore the variety of data types (e.g., texts and images) in multi-modal knowledge graphs (MMKGs). In this paper, we propose Multi-modal Knowledge Graph Attention Network (MKGAT) to better enhance recommender systems by leveraging multi-modal knowledge. Specifically, we propose a multi-modal graph attention technique to conduct information propagation over MMKGs, and then use the resulting aggregated embedding representation for recommendation. To the best of our knowledge, this is the first work that incorporates multi-modal knowledge graph into recommender systems. We conduct extensive experiments on two real datasets from different domains, results of which demonstrate that our model MKGAT can successfully employ MMKGs to improve the quality of recommendation system.

With the rapid development of mobile networks and the widespread usage of mobile devices, spatial crowdsourcing, which refers to assigning location-based tasks to moving workers, has drawn increasing attention. One of the major issues in spatial crowdsourcing is task assignment, which allocates tasks to appropriate workers. However, existing works generally assume the static offline scenarios, where the spatio-temporal information of all the workers and tasks is determined and known a priori. Ignorance of the dynamic spatio-temporal distributions of workers and tasks can often lead to poor assignment results. In this work we study a novel spatial crowdsourcing problem, namely Predictive Task Assignment (PTA), which aims to maximize the number of assigned tasks by taking into account both current and future workers/tasks that enter the system dynamically with location unknown in advance. We propose a two-phase data-driven framework. The prediction phase hybrids different learning models to predict the locations and routes of future workers and designs a graph embedding approach to estimate the distribution of future tasks. In the assignment component, we propose both greedy algorithm for large-scale applications and optimal algorithm with graph partition based decomposition. Extensive experiments on two real datasets demonstrate the effectiveness of our framework.

In Pickup-and-Delivery problems (PDP), mobile workers are employed to pick up and deliver items with the goal of reducing travel and fuel consumption. Unlike most existing efforts that focus on finding a schedule that enables the delivery of as many items as possible at the lowest cost, we consider trichromatic (worker-item-task) utility that encompasses worker reliability, item quality, and task profitability. Moreover, we allow customers to specify keywords for desired items when they submit tasks, which may result in multiple pickup options, thus further increasing the difficulty of the problem. Specifically, we formulate the problem of Online Trichromatic Pickup and Delivery Scheduling (OTPD) that aims to find optimal delivery schedules with highest overall utility. In order to quickly respond to submitted tasks, we propose a greedy solution that finds the schedule with the highest utility-cost ratio. Next, we introduce a skyline kinetic tree-based solution that materializes intermediate results to improve the result quality. Finally, we propose a density-based grouping solution that partitions streaming tasks and efficiently assigns them to the workers with high overall utility. Extensive experiments with real and synthetic data offer evidence that the proposed solutions excel over baselines with respect to both effectiveness and efficiency.

Abstract With the pervasiveness of GPS-enabled smart devices and increased wireless communication technologies, spatial crowdsourcing (SC) has drawn increasing attention in assigning location-sensitive tasks to moving workers. In real-world scenarios, for the complex tasks, SC is more likely to assign each task to more than one worker, called group task assignment (GTA), for the reason that an individual worker cannot complete the task well by herself. It is a challenging issue to assign worker groups the tasks that they are interested in and willing to perform. In this paper, we propose a novel framework for group task assignment based on worker groups’ preferences, which includes two components: social impact-based preference modeling (SIPM) and preference-aware group task assignment (PGTA). SIPM employs a bipartite graph embedding model and the attention mechanism to learn the social impact-based preferences of different worker groups on different task categories. PGTA utilizes an optimal task assignment algorithm based on the tree decomposition technique to maximize the overall task assignments, in which we give higher priorities to the worker groups showing more interests in the tasks. We further optimize the original framework by proposing strategies to improve the effectiveness of group task assignment, wherein a deep learning method and the group consensus are taken into consideration. Extensive empirical studies verify that the proposed techniques and optimization strategies can settle the problem nicely.

The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. In addition, by indexing the reference trajectories directly with an in-memory R-tree and building connections to the raw trajectories with inverted index, we develop an extremely efficient algorithm that can answer spatio-temporal range queries over trajectories in their compressed form. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.

In this paper, we study a new type of spatial crowdsourcing, namely competitive detour tasking, where workers can make detours from their original travel paths to perform multiple tasks, and each worker is allowed to compete for preferred tasks by strategically claiming his/her detour costs. The objective is to make suitable task assignment by maximizing the social welfare of crowdsourcing systems and protecting workers' private sensitive information. We first model the task assignment problem as a reverse auction process. We formalize the winning bid selection of reverse auction as an n-to-one weighted bipartite graph matching problem with multiple 0-1 knapsack constraints. Since this problem is NP-hard, we design an approximation algorithm to select winning bids and determine corresponding payments. Based on this, a Secure Reverse Auction (SRA) protocol is proposed for this novel spatial crowdsourcing. We analyze the approximation performance of the proposed protocol and prove that it has some desired properties, including truthfulness, individual rationality, computational efficiency, and security. To the best of our knowledge, this is the first theoretically provable secure auction protocol for spatial crowdsourcing systems. In addition, we also conduct extensive simulations on a real trace to verify the performance of the proposed protocol.

With the proliferation of GPS-enabled smart devices and increased availability of wireless network, spatial crowdsourcing (SC) has been recently proposed as a framework to automatically request workers (i.e., smart device carriers) to perform location-sensitive tasks (e.g., taking scenic photos, reporting events). In this paper, we study a destination-aware task assignment problem that concerns the optimal strategy of assigning each task to proper worker such that the total number of completed tasks can be maximized whilst all workers can reach their destinations before deadlines after performing assigned tasks. Finding the global optimal assignment turns out to be an intractable problem since it does not imply optimal assignment for individual worker. Observing that the task assignment dependency only exists amongst subsets of workers, we utilize tree-decomposition technique to separate workers into independent clusters and develop an efficient depth-first search algorithm with progressive bounds to prune non-promising assignments. In order to make our proposed framework applicable to more scenarios, we further optimize the original framework by proposing strategies to reduce the overall travel cost and allow each task to be assigned to multiple workers. Extensive empirical studies verify that the proposed technique and optimization strategies perform effectively and settle the problem nicely.

With the proliferation of geo-textual objects on the web, extensive efforts have been devoted to improving the efficiency of top-k spatial keyword queries in different settings. However, comparatively much less work has been reported on enhancing the quality and usability of such queries. In this context, we propose means of enhancing the usability of a top-k group spatial keyword query, where a group of users aim to find k objects that contain given query keywords and are nearest to the users. Specifically, when users receive the result of such a query, they may find that one or more objects that they expect to be in the result are in fact missing, and they may wonder why. To address this situation, we develop a so-called why-notquery that is able to minimally modifythe original query into a query that returns the expected, but missing, objects, in addition to other objects. Specifically, we formalize the why-not query in relation to the top-k group spatial keyword query, called the Why-not Group Spatial Keyword Query (WGSK) that is able to provide a group of users with a more satisfactory query result. We propose a three-phase framework for efficiently computing the WGSK. The first phase substantially reduces the search space for the subsequent phases by retrieving a set of objects that may affect the ranking of the user-expected objects. The second phase provides an incremental sampling algorithm that generates candidate weightings of more promising queries. The third phase determines the penalty of each refined query and returns the querywith minimal penalty, i.e., the minimally modified query. Extensive experiments with real and synthetic data offer evidence that the proposed solution excels over baselines with respect to both effectiveness and efficiency.

The turn-by-turn route descriptions provided in the existing navigation applications are exclusively derived from underlying road network topology information, i.e., the connectivity of edges to each other. Therefore, the turn-by-turn route descriptions are simplified as metric translation of physical world (e.g. distance/time to turn) to spoken language. Such translation that ignores human cognition of the geographic space, is frequently verbose and redundant for the drivers who have knowledge of the geographical areas. In this paper, we study a Personalized Route Description system dubbed PerRD-with which the goal is to generate more customized and intuitive route descriptions based on user generated content. PerRD utilizes a wealth of user generated historical trajectory data to extract frequently visited routes in the road network. The extracted information is used to make cognitive customized route description for each user. We formalize this task as a problem of finding the optimal partition for a given route that maximizes the familiarity while minimizing the number of partitions, and finding a proper sentence to describe each partition. For empirical study, our solution is applied to three trajectory datasets and users' real experiences to evaluate the performance and effectiveness of PerRD.

Geo-textual data that contain spatial, textual, and temporal information are being generated at a very high rate. These geo-textual data cover a wide range of topics. Users may be interested in receiving local popular topics from geo-textual messages. We study the cluster-based subscription matching (CSM) problem. Given a stream of geo-textual messages, we maintain up-to-date clustering results based on a threshold-based online clustering algorithm. Based on the clustering result, we feed subscribers with their preferred geo-textual message clusters according to their specified keywords and location. Moreover, we summarize each cluster by selecting a set of representative messages. The CSM problem considers spatial proximity, textual relevance, and message freshness during the clustering, cluster feeding, and summarization processes. To solve the CSM problem, we propose a novel solution to cluster, feed, and summarize a stream of geo-textual messages efficiently. We evaluate the efficiency of our solution on two real-world datasets and the experimental results demonstrate that our solution is capable of high efficiency compared with baselines.

The task of point of interest (POI) recommendation aims to recommend unvisited places to users based on their check-in history. A major challenge in POI recommendation is data sparsity, because a user typically visits only a very small number of POIs among all available POIs. In this paper, we propose AUC-MF to address the POI recommendation problem by maximizing Area Under the ROC curve (AUC). AUC has been widely used for measuring classification performance with imbalanced data distributions. To optimize AUC, we transform the recommendation task to a classification problem, where the visited locations are positive examples and the unvisited are negative ones. We define a new lambda for AUC to utilize the LambdaMF model, which combines the lambda-based method and matrix factorization model in collaborative filtering. Experiments on two datasets show that the proposed AUC-MF outperforms state-of-the-art methods significantly in terms of recommendation accuracy.

Nowadays, mobile devices are already seen everywhere in life, which makes the application of vehicle navigation more and more widely. The traditional turn-by-turn navigation does the path planning just based on the characteristics of the roads themselves, and then gives mechanized steering instructions at each corner. For those roads people are familiar with in this route, path descriptions which provide detailed route description information, will become redundant and verbose. In this paper, we study a Personalized Route Description system dubbed PerRD - with which the goal is to generate more customized and intuitive route descriptions based on user generated content. The goal is to optimize a given route description with paths which users know well, which makes the route more consistent with users' driving habits, and to create a concise and meaningful route descriptions with POIs and street names.

As social animals, attending group activities is an indispensable part in people's daily social life, and it is an important task for recommender systems to suggest satisfying activities to a group of users. The major challenge in this task is how to aggregate personal preferences of group members to infer the decision of a group. Conventional group recommendation methods applied a predefined strategy for preference aggregation. However, these static strategies are too simple to model the real and complex process of group decision-making, especially for occasional groups which are formed ad-hoc. Moreover, group members should have non-uniform influences or weights in a group, and the weight of a user can be varied in different groups. Therefore, an ideal group recommender system should be able to accurately learn not only users' personal preferences but also the preference aggregation strategy from data. In this paper, we propose a novel group recommender system, namely SIGR (short for "Social Influence-based Group Recommender"), which takes an attention mechanism and a bipartite graph embedding model BGEM as building blocks. Specifically, we adopt an attention mechanism to learn each user's social influence and adapt their social influences to different groups and develop a novel deep social influence learning framework to exploit and integrate users' global and local social network structure information to further improve the estimation of users' social influences. BGEM is extended to model group-item interactions. In order to overcome the limitation and sparsity of the interaction data generated by occasional groups, we propose two model optimization approaches to seamlessly integrate the user-item interaction data. We create two large-scale benchmark datasets and conduct extensive experiments on them. The experimental results show the superiority of our proposed SIGR by comparing with state-of-the-art group recommender models.

With the proliferation of geo-textual objects on the web, extensive efforts have been devoted to improving the efficiency of top-k spatial keyword queries in different settings. However, comparatively much less work has been reported on enhancing the quality and usability of such queries. In this context, we propose means of enhancing the usability of a top-k group spatial keyword query, where a group of users aim to find k objects that contain given query keywords and are nearest to the users. Specifically, when users receive the result of such a query, they may find that one or more objects that they expect to be in the result are in fact missing, and they may wonder why. To address this situation, we develop a so-called why-not query that is able to minimally modify the original query into a query that returns the expected, but missing, objects, in addition to other objects. Specifically, we formalize the why-not query in relation to the top-k group spatial keyword query, called the Why-not Group Spatial Keyword Query (WGSK) that is able to provide a group of users with a more satisfactory query result. We propose a three-phase framework for efficiently computing he WGSK. Extensive experiments with real and synthetic data offer evidence that the proposed solution excels over baselines with respect to both effectiveness and efficiency.

An Attributed Dynamic Graph (ADG) contains multiple dynamic attributes associated with each edge. In ADG based applications, people usually can specify multiple constrains in the attributes to illustrate their requirements, such as the total cost, the total travel time and the stopover interval of a flight between two cities. This inspires a type of Multi-Constrained Temporal Path (MCTP) discovery in ADGs, which is a challenging NP-Complete problem. In order to deliver an efficient and effective temporal path discovery method to be used in real-time environment, we propose a Reinforcement Learning (RL) based, Monte Carlo Tree Search algorithm (RLMCTS). RL-MCTS uses a newly designed memory structure to address the challenges of Monte Carlo Tree Search (MCTS) in MCTP discovery. To the best of our knowledge, RL-MCTS is the first RL algorithm that supports path discovery in ADGs. The experimental results on ten real dynamic graphs demonstrate that our algorithm outperforms the state-of-the-art methods in terms of both efficiency and effectiveness.

The time signals behind a user's historical behaviors are important for better inferring what she prefers to interact with at the next time. For the attention-based recommendation methods, relative position encoding and time intervals division are two common ways to model the time signal behind each behavior. They either only consider the relative position of each behavior in the behavior sequence, or process the continuous temporal features into discrete category features for subsequent tasks, which can hardly capture the dynamic preferences of a user. In addition, although the existing recommendation methods have considered both long-term preference and short-term preference, they ignore the fact that the long-term preference of a user may be multi-faceted, and it is difficult to learn a user's fine-grained short-term preference. In this paper, we propose a Dynamic Multi-faceted Fine-grained Preference model (DMFP), where the multi-hops attention mechanism and the feature-level attention mechanism together with a vertical convolution operation are adopted to capture users' multi-faceted long-term preference and fine-grained short-term preference, respectively. Therefore, DMFP can better support the next item recommendation. Extensive experiments on three real-world datasets illustrate that our model can improve the effectiveness of the recommendation compared with the state-of-the-art methods.

Exploring Hidden Points of Interest (H-POIs), which are rarely referred in online search and recommendation systems due to insufficient check-in records, benefits business and individuals. In this work, we investigate how to eliminate the hidden feature of H-POIs by enhancing conventional crowdsourced ranking aggregation framework with heterogeneous (i.e., H-POI and Popular Point of Interest (P-POI)) pairwise tasks. We propose a two-phase solution focusing on both effectiveness and efficiency. In offline phase, we substantially narrow down the search space by retrieving a set of geo-textual valid heterogeneous pairs as the initial candidates and develop two practical data-driven strategies to compute worker qualities. In the online phase, we minimize the cost of assessment by introducing an active learning algorithm to jointly select pairs and workers with worker quality, uncertainty of P-POI rankings and uncertainty of the model taken into account. In addition, a (Minimum Spanning) Tree-constrained Skip search strategy is proposed for the purpose of reducing search time cost. Empirical experiments based on real POI datasets verify that the ranking accuracy of H-POIs can be greatly improved with small number of query iterations.

Ride-hailing applications are becoming more and more popular for providing drivers and passengers with convenient ride services, especially in metropolises like Beijing or New York. To obtain the passengers' mobility patterns, the online platforms of ride services need to predict the number of passenger demands from one region to another in advance. We formulate this problem as an Origin-Destination Matrix Prediction (ODMP) problem. Though this problem is essential to large-scale providers of ride services for helping them make decisions and some providers have already put it forward in public, existing studies have not solved this problem well. One of the main reasons is that the ODMP problem is more challenging than the common demand prediction. Besides the number of demands in a region, it also requires the model to predict the destinations of them. In addition, data sparsity is a severe issue. To solve the problem effectively, we propose a unified model, Grid-Embedding based Multi-task Learning (GEML) which consists of two components focusing on spatial and temporal information respectively. The Grid-Embedding part is designed to model the spatial mobility patterns of passengers and neighboring relationships of different areas, the pre-weighted aggregator of which aims to sense the sparsity and range of data. The Multi-task Learning framework focuses on modeling temporal attributes and capturing several objectives of the ODMP problem. The evaluation of our model is conducted on real operational datasets from UCAR and Didi. The experimental results demonstrate the superiority of our GEML against the state-of-the-art approaches.

The matching between trajectories and locations, called Trajectory-to-Location join (TL-Join), is fundamental functionality in spatiotemporal data management. Given a set of trajectories, a set of locations, and a threshold 8, the TL-Join finds all (trajectory, location) pairs from the two sets with spatiotemporal correlation above 8. This join targets diverse applications, including location recommendation, event tracking, and trajectory activity analyses. We address three challenges in relation to the TL-Join: how to define the spatiotemporal correlation between trajectories and locations, how to prune the search space effectively when computing the join, and how to perform the computation in parallel. Specifically, we define new metrics to measure the spatiotemporal correlation between trajectories and locations. We develop a novel parallel collaborative (PCol) search method based on a divide-and-conquer strategy. For each location o, we retrieve the trajectories with high spatiotemporal correlation to o, and then we merge the results. An upper bound on the spatiotemporal correlation and a heuristic scheduling strategy are developed to prune the search space. The trajectory searches from different locations are independent and are performed in parallel, and the result merging cost is independent of the degree of parallelism. Studies of the performance of the developed algorithms using large spatiotemporal data sets are reported.

What-if analysis is a data-intensive exploration to inspect how changes in a set of input parameters of a model influence some outcomes. It is motivated by a user trying to understand the sensitivity of a model to a certain parameter in order to reach a set of goals that are defined over the outcomes. To avoid an exploration of all possible combinations of parameter values, efficient what-if analysis calls for a partitioning of parameter values into data ranges and a unified representation of the obtained outcomes per range. Traditional techniques to capture data ranges, such as histograms, are limited to one outcome dimension. Yet, in practice, what-if analysis often involves conflicting goals that are defined over different dimensions of the outcome. Working on each of those goals independently cannot capture the inherent trade-off between them. In this paper, we propose techniques to recommend data ranges for what-if analysis, which capture not only data regularities, but also the trade-off between conflicting goals. Specifically, we formulate a parametric data partitioning problem and propose a method to find an optimal solution for it. Targeting scalability to large datasets, we further provide a heuristic solution to this problem. By theoretical and empirical analyses, we establish performance guarantees in terms of runtime and result quality.

Discovering expert drivers is highly important for a broad range of location based services, but this issue is largely untouched in previous trajectory mining and search studies. In this paper, we study the problem of trajectory data driven expert driver discovery. It aims to find out top-k expert drivers about a region of interest, based on the understanding of their historical trajectories. To this end, we first investigate the construction of reference system, which collectively describes exemplar routes among important junctions, so that the driving behaviors embedded in each trajectory can be evaluated. To discover expert drivers accurately, a novel tf-idf concept based measure is proposed afterwards, such that the rationality of their trajectories are not only precisely evaluated by the match to reference system, but also properly aggregated for modelling expert drivers. Extensive experimental evaluation using real trajectory datasets demonstrates the effectiveness and efficiency of our proposed solutions.

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

Information network embedding is an effective way for efficient graph analytics. However, it still faces with computational challenges in problems such as link prediction and node recommendation, particularly with increasing scale of networks. Hashing is a promising approach for accelerating these problems by orders of magnitude. However, no prior studies have been focused on seeking binary codes for information networks to preserve high-order proximity. Since matrix factorization (MF) unifies and outperforms several well-known embedding methods with high-order proximity preserved, we propose a MF-based \underlineI nformation \underlineN etwork \underlineH ashing (INH-MF) algorithm, to learn binary codes which can preserve high-order proximity. We also suggest Hamming subspace learning, which only updates partial binary codes each time, to scale up INH-MF. We finally evaluate INH-MF on four real-world information network datasets with respect to the tasks of node classification and node recommendation. The results demonstrate that INH-MF can perform significantly better than competing learning to hash baselines in both tasks, and surprisingly outperforms network embedding methods, including DeepWalk, LINE and NetMF, in the task of node recommendation. The source code of INH-MF is available online\footnote\urlhttps://github.com/DefuLian/network .

The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.

Graph Pattern Matching (GPM) has been used in lots of areas, like biology, medical science, and physics. With the advent of Online Social Networks (OSNs), recently, GPM has been playing a significant role in social network analysis, which has been widely used in, for example, finding experts, social community mining, and social position detection. Given a query which contains a pattern graph GQand a data graph GD, a GPM algorithm finds those subgraphs, GM, that match GQin GD. However, the existing GPM methods do not consider the multiple end-to-end constraints of the social contexts, like social relationships, social trust, and social positions on edges in GQ, which are commonly found in various applications, such as crowdsourcing travel, social network based ecommerce, and study group selection, etc. In this paper, we first conceptually extend Bounded Simulation to Multi-Constrained Simulation (MCS), and propose a novel NP-Complete Multi-Constrained Graph Pattern Matching (MC-GPM) problem. Then, to address the efficiency issue in large-scale MC-GPM, we propose a new concept called Strong Social Component (SSC), consisting of participants with strong social connections. We also propose an approach to identifying SSCs, and propose a novel index method and a graph compression method for SSC. Moreover, we devise a multithreading heuristic algorithm, called M-HAMC, to bidirectionally search the MC-GPM results in parallel without decompressing graphs. An extensive empirical study over five real-world large-scale social graphs has demonstrated the effectiveness and efficiency of our approach.

Location recommendation is an important means to help people discover attractive locations. However, extreme sparsity of user-location matrices leads to a severe challenge, so it is necessary to take implicit feedback characteristics of user mobility data into account and leverage the location’s spatial information. To this end, based on previously developed GeoMF, we propose a scalable and flexible framework, dubbed GeoMF++, for joint geographical modeling and implicit feedback-based matrix factorization. We then develop an efficient optimization algorithm for parameter learning, which scales linearly with data size and the total number of neighbor grids of all locations. GeoMF++ can be well explained from two perspectives. First, it subsumes two-dimensional kernel density estimation so that it captures spatial clustering phenomenon in user mobility data; Second, it is strongly connected with widely used neighbor additive models, graph Laplacian regularized models, and collective matrix factorization. Finally, we extensively evaluate GeoMF++ on two large-scale LBSN datasets. The experimental results show that GeoMF++ consistently outperforms the state-of-the-art and other competing baselines on both datasets in terms of NDCG and Recall. Besides, the efficiency studies show that GeoMF++ is much more scalable with the increase of data size and the dimension of latent space.

Information Extraction by Text Segmentation (IETS) aims at segmenting text inputs to extract implicit data values contained in them.The state-of-art IETS approaches mainly rely on machine learning techniques, either supervised or unsupervised.However, while the supervised approaches require a large labelled training data, the performance of the unsupervised ones could be unstable on different data sets.To overcome their weaknesses, this paper introduces CNN-IETS, a novel unsupervised probabilistic approach that takes the advantages of pre-existing data and a Convolution Neural Network (CNN)-based probabilistic classification model. While using the CNN model can ease the burden of selecting high-quality features in associating text segments with attributes of a given domain, the pre-existing data as a domain knowledge base can provide training data with a comprehensive list of features for building the CNN model.Given an input text, we do initial segmentation (according to the occurrences of these words in the knowledge base) to generate text segments for CNN classification with probabilities. Then, based on the probabilistic CNN classification results, we work on finding the most probable labelling way to the whole input text.As a complementary, a bidirectional sequencing model learned on-demand from test data is finally deployed to do further adjustment to some problematic labelled segments.Our experimental study conducted on several real data collections shows that CNN-IETS improves the extraction quality of state-of-art approaches by more than 10%.

Conventional spatial keyword queries confront the difficulty of returning desired objects that are synonyms but morphologically different to query keywords. To overcome this flaw, this paper investigates the interactive spatial keyword querying with semantics. It aims to enhance the conventional queries by not only making sense of the query keywords, but also refining the understanding of query semantics through interactions. On top of the probabilistic topic model, a novel interactive strategy is proposed to precisely infer the latent query semantics by learning from user feedbacks. In each interaction, the returned objects are carefully selected to ensure effective inference of user intended query semantics. Query processing is carried out on a small candidate object set at each round of interaction, and the whole querying process terminates when the latent query semantics learned from user feedback becomes explicit enough. The experimental results on real check-in dataset demonstrates that the quality of results has been significantly improved through limited number of interactions.

With the proliferation of GPS-enabled smart devices and increased availability of wireless network, spatial crowdsourcing (SC) has been recently proposed as a framework to automatically request workers (i.e., smart device carriers) to perform location-sensitive tasks (e.g., taking scenic photos, reporting events). In this paper we study a destination-aware task assignment problem that concerns the optimal strategy of assigning each task to proper worker such that the total number of completed tasks can be maximized whilst all workers can reach their destinations before deadlines after performing assigned tasks. Finding the global optimal assignment turns out to be an intractable problem since it does not imply optimal assignment for individual worker. Observing that the task assignment dependency only exists amongst subsets of workers, we utilize tree-decomposition technique to separate workers into independent clusters and develop an efficient depth-first search algorithm with progressive bounds to prune non-promising assignments. Our empirical studies demonstrate that our proposed technique is quite effective and settle the problem nicely.

Schema Matching (SM) and Record Matching (RM) are two necessary steps in integrating multiple relational tables of different schemas, where SM unifies the schemas and RM detects records referring to the same real-world entity. The two processes have been thoroughly studied separately, but few attention has been paid to the interaction of SM and RM. In this work we find that, even alternating them in a simple manner, SM and RM can benefit from each other to reach a better integration performance (i.e., in terms of precision and recall). Therefore, combining SM and RM is a promising solution for improving data integration.

With the rapid development of location-based social networks, Point-of-Interest (POI) recommendation has played an important role in helping people discover attractive locations. However, existing POI recommendation methods assume a flat structure of POIs, which are better described in a hierarchical structure in reality. Furthermore, we discover that both users' content and spatial preferences exhibit hierarchical structures. To this end, in this paper, we propose a hierarchical geographical matrix factorization model (HGMF) to utilize the hierarchical structures of both users and POIs for POI recommendation. Specifically, we first describe the POI influence degrees over regions with two-dimensional normal distribution, and learn the influence areas of different layers of POIs as the input of HGMF. Then, we perform matrix factorization on user content preference matrix, user spatial preference matrix, and POIs characteristic matrix jointly with the modeling of implicit hierarchical structures. Moreover, a two-step optimization method is proposed to learn the implicit hierarchical structure and find the solution of HGMF efficiently. Finally, we evaluate HGMF on two large-scale real-world location-based social networks datasets. Our experimental results demonstrate that it outperforms the state-of-the-art methods in terms of precision and recall.

Precisely recommending relevant items from massive candidates to a large number of users is an indispensable yet computationally expensive task in many online platforms (e.g., Amazon.com and Netflix.com). A promising way is to project users and items into a Hamming space and then recommend items via Hamming distance. However, previous studies didn't address the cold-start challenges and couldn't make the best use of preference data like implicit feedback. To fill this gap, we propose a Discrete Content-aware Matrix Factorization (DCMF) model, 1) to derive compact yet informative binary codes at the presence of user/item content information; 2) to support the classification task based on a local upper bound of logit loss; 3) to introduce an interaction regularization for dealing with the sparsity issue. We further develop an efficient discrete optimization algorithm for parameter learning. Based on extensive experiments on three real-world datasets, we show that DCFM outperforms the state-of-the-arts on both regression and classification tasks.

Nowadays, users of social networks like tweets and weibo have generated massive geo-tagged records, and these records reveal their activities in the physical world together with spatio-temporal dynamics. Existing trajectory data management studies mainly focus on analyzing the spatio-temporal properties of trajectories, while leaving the understanding of their activities largely untouched. In this paper, we incorporate the semantic analysis of the activity information embedded in trajectories into query modelling and processing, with the aim of providing end users more accurate and meaningful trip recommendations. To this end, we propose a novel trajectory query that not only considers the spatio-temporal closeness but also, more importantly, leverages probabilistic topic modelling to capture the semantic relevance of the activities between data and query. To support efficient query processing, we design a novel hybrid index structure, namely ST-tree, to organize the trajectory points hierarchically, which enables us to prune the search space in spatial and topic dimensions simultaneously. The experimental results on real datasets demonstrate the efficiency and scalability of the proposed index structure and search algorithms.

Single-source and top- k SimRank queries are two important types of similarity search in graphs with numerous applications in web mining, social network analysis, spam detection, etc. A plethora of techniques have been proposed for these two types of queries, but very few can efficiently support similarity search over large dynamic graphs, due to either significant preprocessing time or large space overheads. This paper presents ProbeSim , an index-free algorithm for single-source and top- k SimRank queries that provides a non-trivial theoretical guarantee in the absolute error of query results. ProbeSim estimates SimRank similarities without precomputing any indexing structures, and thus can naturally support real-time SimRank queries on dynamic graphs. Besides the theoretical guarantee, ProbeSim also offers satisfying practical efficiency and effectiveness due to non-trivial optimizations. We conduct extensive experiments on a number of benchmark datasets, which demonstrate that our solutions outperform the existing methods in terms of efficiency and effectiveness. Notably, our experiments include the first empirical study that evaluates the effectiveness of SimRank algorithms on graphs with billion edges, using the idea of pooling.

The matching of similar pairs of objects, called similarity join, is fundamental functionality in data management. We consider the case of trajectory similarity join (TS-Join), where the objects are trajectories of vehicles moving in road networks. Thus, given two sets of trajectories and a threshold θ , the TS-Join returns all pairs of trajectories from the two sets with similarity above θ . This join targets applications such as trajectory near-duplicate detection, data cleaning, ridesharing recommendation, and traffic congestion prediction. With these applications in mind, we provide a purposeful definition of similarity. To enable efficient TS-Join processing on large sets of trajectories, we develop search space pruning techniques and take into account the parallel processing capabilities of modern processors. Specifically, we present a two-phase divide-and-conquer algorithm. For each trajectory, the algorithm first finds similar trajectories. Then it merges the results to achieve a final result. The algorithm exploits an upper bound on the spatiotemporal similarity and a heuristic scheduling strategy for search space pruning. The algorithm's per-trajectory searches are independent of each other and can be performed in parallel, and the merging has constant cost. An empirical study with real data offers insight in the performance of the algorithm and demonstrates that is capable of outperforming a well-designed baseline algorithm by an order of magnitude.

Schema Matching (SM) and Record Matching (RM) are two necessary steps in integrating multiple relational tables of different schemas, where SM unifies the schemas and RM detects records referring to the same real-world entity. The two processes have been thoroughly studied separately, but few attention has been paid to the interaction of SM and RM. In this work, we find that, even alternating them in a simple manner, SM and RM can benefit from each other to reach a better integration performance (i.e., in terms of precision and recall). Therefore, combining SM and RM is a promising solution for improving data integration. To this end, we define novel matching rules for SM and RM, respectively, that is, every SM decision is made based on intermediate RM results, and vice versa, such that SM and RM can be performed alternately. The quality of integration is guaranteed by a Matching Likelihood Estimation model and the control of semantic drift, which prevent the effect of mismatch magnification. To reduce the computational cost, we design an index structure based on q-grams and a greedy search algorithm that can reduce around 90 percent overhead of the interaction. Extensive experiments on three data collections show that the combination and interaction between SM and RM significantly outperforms previous works that conduct SM and RM separately.

Understanding short texts is crucial to many applications, but challenges abound. First, short texts do not always observe the syntax of a written language. As a result, traditional natural language processing tools, ranging from part-of-speech tagging to dependency parsing, cannot be easily applied. Second, short texts usually do not contain sufficient statistical signals to support many state-of-the-art approaches for text mining such as topic modeling. Third, short texts are more ambiguous and noisy, and are generated in an enormous volume, which further increases the difficulty to handle them. We argue that semantic knowledge is required in order to better understand short texts. In this work, we build a prototype system for short text understanding which exploits semantic knowledge provided by a well-known knowledgebase and automatically harvested from a web corpus. Our knowledge-intensive approaches disrupt traditional methods for tasks such as text segmentation, part-of-speech tagging, and concept labeling, in the sense that we focus on semantics in all these tasks. We conduct a comprehensive performance evaluation on real-life data. The results show that semantic knowledge is indispensable for short text understanding, and our knowledge-intensive approaches are both effective and efficient in discovering semantics of short texts.

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. For example, a personalized route query is issued by providing some clues that describe the spatial context between PoIs along the route, where the result can be far from the optimal one. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

Knowledge bases have shown their effectiveness in facilitating services like Web search and question-answering. Nevertheless, it remains challenging for ordinary users to fully understand the structure of a knowledge base and to issue structural queries. In many cases, users may have a natural language question and also know some popular (but not all) entities as sample answers. In this paper, we study the Reverse top-k Neighborhood Pattern Query problem, with the aim of discovering structural queries of the question based on: (i) the structure of the knowledge base, and (ii) the sample answers of the question. The proposed solution contains two phases: filter and refine. In the filter phase, a search space of candidate queries is systematically explored. The invalid queries whose result sets do not fully cover the sample answers are filtered out. In the refine phase, all surviving queries are verified to ensure that they are sufficiently relevant to the sample answers, with the assumption that the sample answers are more well-known or popular than other entities in the results of relevant queries. Several optimization techniques are proposed to accelerate the refine phrase. For evaluation, we conduct extensive experiments using the DBpedia knowledge base and a set of real-life questions. Empirical results show that our algorithm is able to provide a small set of possible queries, which contains the query matching the user question in natural language.

The prediction of periodical time-series remains challenging due to various types of scaling, misalignments and distortion effects. Here, we propose a novel model called Temporal embedding-enhanced convolutional neural Network (TeNet) to learn repeatedly-occurring-yet-hidden structural elements in periodical time-series, called abstract snippet detectors, to predict future changes. Our model effectively learns a new feature space for a time-series dataset. In the new feature space, distorted time-series that have implicit similarity but substantial differences in value and sequence to regular patterns are re-aligned to the regular patterns in the dataset, and subsequently contribute to a robust prediction mode. The model is robust to various types of distortions and misalignments and demonstrates strong prediction power for periodical time-series. We conduct extensive experiments and discover that the proposed model shows significant and consistent advantages over existing methods on a variety of data modalities ranging from human mobility to household power consumption records, when evaluated under four metrics. The model is also robust to various factors such as number of samples, variance of data, numerical ranges of data etc. The experiments verify that the intuition behind the model can be generalized to multiple data types and applications and promises significant improvement in prediction performance across the datasets studied.

Social community detection is a growing field of interest in the area of social network applications, and many approaches have been developed, including graph partitioning, latent space model, block model and spectral clustering. Most existing work purely focuses on network structure information which is, however, often sparse, noisy and lack of interpretability. To improve the accuracy and interpretability of community discovery, we propose to infer users' social communities by incorporating their spatiotemporal data and semantic information. Technically, we propose a unified probabilistic generative model, User-Community-Geo-Topic (UCGT), to simulate the generative process of communities as a result of network proximities, spatiotemporal co-occurrences and semantic similarity. With a well-designed multi-component model structure and a parallel inference implementation to leverage the power of multicores and clusters, our UCGT model is expressive while remaining efficient and scalable to growing large-scale geo-social networking data. We deploy UCGT to two application scenarios of user behavior predictions: check-in prediction and social interaction prediction. Extensive experiments on two large-scale geo-social networking datasets show that UCGT achieves better performance than existing state-of-the-art comparison methods.

It is nowadays quite common for road networks to have textual contents on the vertices, which describe auxiliary information (e.g., business, traffic, etc.) associated with the vertex. In such road networks, which are modelled as weighted undirected graphs, each vertex is associated with one or more keywords, and each edge is assigned with a weight, which can be its physical length or travelling time. In this paper, we study the problem of keyword-aware continuous k nearest neighbour (KCkNN) search on road networks, which computes the k nearest vertices that contain the query keywords issued by a moving object and maintains the results continuously as the object is moving on the road network. Reducing the query processing costs in terms of computation and communication has attracted considerable attention in the database community with interesting techniques proposed. This paper proposes a framework, called a Labelling AppRoach for Continuous kNN query (LARC), on road networks to cope with KCkNN query efficiently. First we build a pivot-based reverse label index and a keyword-based pivot tree index to improve the efficiency of keyword-aware k nearest neighbour (KkNN) search by avoiding massive network traversals and sequential probe of keywords. To reduce the frequency of unnecessary result updates, we develop the concepts of dominance interval and region on road network, which share the similar intuition with safe region for processing continuous queries in Euclidean space but are more complicated and thus require more dedicated design. For high frequency keywords, we resolve the dominance interval when the query results changed. In addition, a path-based dominance updating approach is proposed to compute the dominance region efficiently when the query keywords are of low frequency. We conduct extensive experiments by comparing our algorithms with the state-of-the-art methods on real data sets. The empirical observations have verified the superiority of our proposed solution in all aspects of index size, communication cost and computation time.

The wide adoption of location-based services provide the potential to understand people's mobility pattern at an unprecedented level, which can also enable food-service industry to accurately predict consumers' dining behavior. In this paper, based on users' dining implicit feedbacks (restaurant visit via check-ins), explicit feedbacks (restaurant reviews) as well as some meta data (e.g., location, user demographics, restaurant attributes), we aim at recommending each user a list of restaurants for his next dining. Implicit and Explicit feedbacks of dining behavior exhibit different characteristics of user preference. Therefore, in our work, user's dining preference mainly contains two parts: implicit preference coming from check-in data (implicit feedbacks) and explicit preference coming from rating and review data (explicit feedbacks). For implicit preference, we first apply a probabilistic tensor factorization model (PTF) to capture preference in a latent subspace. Then, in order to incorporate contextual signals from meta data, we extend PTF by proposing an Implicit Preference Model (IPM), which can simultaneously capture users'/restaurants'/time' preference in the collaborative filtering and dining preference in a specific context (e.g., spatial distance preference, environmental preference). For explicit preference, we propose Explicit Preference Model (EPM) by combining matrix factorization with topic modeling to discover the user preference embedded both in rating score and text content. Finally, we design a unified model termed as Collective Implicit Explicit Preference Model (CIEPM) to combine implicit and explicit preference together for restaurant recommendation. To evaluate the performance of our system, we conduct extensive experiments with large-scale datasets covering hundreds of thousands of users and restaurants. The results reveal that our system is effective for restaurant recommendation.

Route recommendation is one of the most widely used location-based services nowadays, as it is vital for nice-driving experience and smooth public traffic. Given a pair of user-specified origin and destination, a route recommendation service aims to provide users with the routes of the best travelling experience according to given criteria. However, even the routes recommended by the big-thumb service providers can deviate significantly from the ones travelled by experienced drivers, which motivates the previous research that leverages crowds’ knowledge to improve the recommendation quality. Since route recommendation is normally an online task, low-latency response to drivers’ queries is required in this kind of systems. Unfortunately, latency of crowdsourced systems is usually high, because they need to generate tasks and wait for workers’ feedbacks before answering queries. To address this issue, we extend our previous system—CrowdPlanner—by proposing some strategies to reuse existing answers (truths) to deal with newly coming queries more efficiently. A prototype system has been deployed to many voluntary mobile clients and extensive tests on real-scenario queries have shown the superiority of our system in comparison with the results given by map services and popular route-mining algorithms.

With the explosion of smartphones and social network services, location-based social networks (LBSNs) are increasingly seen as tools for businesses (e.g., restaurants and hotels) to promote their products and services. In this article, we investigate the key techniques that can help businesses promote their locations by advertising wisely through the underlying LBSNs. In order to maximize the benefit of location promotion, we formalize it as an influence maximization problem in an LBSN, i.e., given a target location and an LBSN, a set of k users (called seeds) should be advertised initially such that they can successfully propagate and attract many other users to visit the target location. Existing studies have proposed different ways to calculate the information propagation probability, that is, how likely it is that a user may influence another, in the setting of a static social network. However, it is more challenging to derive the propagation probability in an LBSN since it is heavily affected by the target location and the user mobility, both of which are dynamic and query dependent. This article proposes two user mobility models, namely the Gaussian-based and distance-based mobility models, to capture the check-in behavior of individual LBSN users, based on which location-aware propagation probabilities can be derived. Extensive experiments based on two real LBSN datasets have demonstrated the superior effectiveness of our proposals compared with existing static models of propagation probabilities to truly reflect the information propagation in LBSNs.

Point-of-Interest recommendation is an essential means to help people discover attractive locations, especially when people travel out of town or to unfamiliar regions. While a growing line of research has focused on modeling user geographical preferences for POI recommendation, they ignore the phenomenon of user interest drift across geographical regions, i.e., users tend to have different interests when they travel in different regions, which discounts the recommendation quality of existing methods, especially for out-of-town users. In this paper, we propose a latent class probabilistic generative model Spatial-Temporal LDA (ST-LDA) to learn region-dependent personal interests according to the contents of their checked-in POIs at each region. As the users' check-in records left in the out-of-town regions are extremely sparse, ST-LDA incorporates the crowd's preferences by considering the public's visiting behaviors at the target region. To further alleviate the issue of data sparsity, a social-spatial collective inference framework is built on ST-LDA to enhance the inference of region-dependent personal interests by effectively exploiting the social and spatial correlation information. Besides, based on ST-LDA, we design an effective attribute pruning (AP) algorithm to overcome the curse of dimensionality and support fast online recommendation for large-scale POI data. Extensive experiments have been conducted to evaluate the performance of our ST-LDA model on two real-world and large-scale datasets. The experimental results demonstrate the superiority of ST-LDA and AP, compared with the state-of-the-art competing methods, by making more effective and efficient mobile recommendations.

Spatial trajectory data is widely available today. Over a sustained period of time, trajectory data has been collected from numerous GPS devices, smartphones, sensors and social media applications. Daily increases of real-time trajectory data have also been phenomenal in recent years. More and more new applications have emerged to derive business values from both trajectory data warehouses and real-time trajectory data. Due to their very large volumes, their nature of streaming, their highly variable levels of data quality, as well as many possible links with other types of data, making sense of spatial trajectory data becomes one of the crucial areas for big data analytics. In this paper we will present a review of the extensive work in spatiotemporal data management and trajectory mining, and discuss new challenges and new opportunities in the context of new applications, focusing on recent advances in trajectory data management and trajectory mining from their foundations to high performance processing with modern computing infrastructure.

Understanding short texts is crucial to many applications, but challenges abound. First, short texts do not always observe the syntax of a written language. As a result, traditional natural language processing methods cannot be easily applied. Second, short texts usually do not contain sufficient statistical signals to support many state-of-the-art approaches for text processing such as topic modeling. Third, short texts are usually more ambiguous. We argue that knowledge is needed in order to better understand short texts. In this work, we use lexical-semantic knowledge provided by a well-known semantic network for short text understanding. Our knowledge-intensive approach disrupts traditional methods for tasks such as text segmentation, part-of-speech tagging, and concept labeling, in the sense that we focus on semantics in all these tasks. We conduct a comprehensive performance evaluation on real-life data. The results show that knowledge is indispensable for short text understanding, and our knowledge-intensive approaches are effective in harvesting semantics of short texts.

Outsourcing database to clouds is a scalable and cost-effective way for large scale data storage, management, and query processing. Trajectory data contain rich spatio-temporal relationships and reveal many forms of individual sensitive information (e.g., home address, health condition), which necessitate them to be encrypted before being outsourced for privacy concerns. However, efficient query processing over encrypted trajectory data is a very challenging task. Though some achievements have been reported very recently for simple queries (e.g., SQL queries, kNN queries) on encrypted data, there is rather limited progress on secure evaluation of trajectory queries because they are more complex and need special treatment. In this paper, we focus on secure trajectory similarity computation that is the cornerstone of secure trajectory query processing. More specifically, we propose an efficient solution to securely compute the similarity between two encrypted trajectories, which reveals nothing about the trajectories, but the final result. We theoretically prove that our solution is secure against the semi-honest adversaries model as all the intermediate information in our protocols can be simulated in polynomial time. Finally we empirically study the efficiency of the proposed method, which demonstrates the feasibility of our solution.

Graph Pattern Matching (GPM) plays a significant role in social network analysis, which has been widely used in, for example, experts finding, social community mining and social position detection. Given a pattern graph GQand a data graph GD, a GPM algorithm finds those subgraphs, GM, that match GQin GD. However, the existing GPM methods do not consider the multiple constraints on edges in GQ, which are commonly exist in various applications such as, crowdsourcing travel, social network based e-commerce and study group selection, etc. In this paper, we first conceptually extend Bounded Simulation to Multi-Constrained Simulation (MCS), and propose a novel NP-Complete Multi-Constrained Graph Pattern Matching (MC-GPM) problem. Then, to address the efficiency issue in large-scale MC-GPM, we propose a new concept called Strong Social Component (SSC), consisting of participants with strong social connections. We also propose an approach to identify SSCs, and propose a novel index method and a graph compression method for SSC. Moreover, we devise a heuristic algorithm to identify MC-GPM results effectively and efficiently without decompressing graphs. An extensive empirical study on five real-world large-scale social graphs has demonstrated the effectiveness, efficiency and scalability of our approach.

Due to the prevalence of GPS-enabled devices and wireless communication technology, spatial trajectories that describe the movement history of moving objects are being generated and accumulated at an unprecedented pace. However, a raw trajectory in the form of sequence of timestamped locations does not make much sense for humans without semantic representation. In this work we aim to facilitate human's understanding of a raw trajectory by automatically generating a short text to describe it. By formulating this task as the problem of adaptive trajectory segmentation and feature selection, we propose a partition-and-summarization framework. In the partition phase, we first define a set of features for each trajectory segment and then derive an optimal partition with the aim to make the segments within each partition as homogeneous as possible in terms of their features. In the summarization phase, for each partition we select the most interesting features by comparing against the common behaviours of historical trajectories on the same route and generate short text description for these features. For empirical study, we apply our solution to a real trajectory dataset and have found that the generated text can effectively reflect the important parts in a trajectory.

Conventional top-k spatial keyword queries require users to explicitly specify their preferences between spatial proximity and keyword relevance. In this work we investigate how to eliminate this requirement by enhancing the conventional queries with interaction, resulting in Interactive Top-k Spatial Keyword (ITkSK) query. Having confirmed the feasibility by theoretical analysis, we propose a three-phase solution focusing on both effectiveness and efficiency. The first phase substantially narrows down the search space for subsequent phases by efficiently retrieving a set of geo-textual k-skyband objects as the initial candidates. In the second phase three practical strategies for selecting a subset of candidates are developed with the aim of maximizing the expected benefit for learning user preferences at each round of interaction. Finally we discuss how to determine the termination condition automatically and estimate the preference based on the user's feedback. Empirical study based on real PoI datasets verifies our theoretical observation that the quality of top-k results in spatial keyword queries can be greatly improved through only a few rounds of interactions.

Driven by the advances in location positioning techniques and the popularity of location sharing services, semantic enriched trajectory data have become unprecedentedly available. While finding relevant Point-of-Interest (POIs) based on users' locations and query keywords has been extensively studied in the past years, it is largely untouched to explore the keyword queries in the context of semantic trajectory database. In this paper, we study the problem of approximate keyword search in massive semantic trajectories. Given a set of query keywords, an approximate keyword query of semantic trajectory (AKQST) returns k trajectories that contain the most relevant keywords to the query and yield the least travel effort in the meantime. The main difference between AKQST and conventional spatial keyword queries is that there is no query location in AKQST, which means the search area cannot be localized. To capture the travel effort in the context of query keywords, a novel utility function, called spatio-textual utility function, is first defined. Then we develop a hybrid index structure called GiKi to organize the trajectories hierarchically, which enables pruning the search space by spatial and textual similarity simultaneously. Finally an efficient search algorithm and fast evaluation of the minimum value of spatio-textual utility function are proposed. The results of our empirical studies based on real check-in datasets demonstrate that our proposed index and algorithms can achieve good scalability.

With the explosion of smartphones and social network services, location-based social networks (LBSNs) are increasingly seen as tools for businesses (e.g., restaurants, hotels) to promote their products and services. In this paper, we investigate the key techniques that can help businesses promote their locations by advertising wisely through the underlying LBSNs. In order to maximize the benefit of location promotion, we formalize it as an influence maximization problem in an LBSN, i.e., given a target location and an LBSN, which a set of k users (called seeds) should be advertised initially such that they can successfully propagate and attract most other users to visit the target location. Existing studies have proposed different ways to calculate the information propagation probability, that is how likely a user may influence another, in the settings of static social network. However, it is more challenging to derive the propagation probability in an LBSN since it is heavily affected by the target location and the user mobility, both of which are dynamic and query dependent. This paper proposes two user mobility models, namely Gaussian-based and distance-based mobility models, to capture the check-in behavior of individual LBSN user, based on which location-aware propagation probabilities can be derived respectively. Extensive experiments based on two real LBSN datasets have demonstrated the superior effectiveness of our proposals than existing static models of propagation probabilities to truly reflect the information propagation in LBSNs.

Nowadays microblogging sites, such as Twitter and Chinese Sina Weibo, have established themselves as an invaluable information source, which provides a huge collection of manually-generated tweets with broad range of topics from daily life to breaking news. Entity linking is indispensable for understanding and maintaining such information, which in turn facilitates many real-world applications such as tweet clustering and classification, personalized microblog search, and so forth. However, tweets are short, informal and error-prone, rendering traditional approaches for entity linking in documents largely inapplicable. Recent work addresses this problem by utilising information from other tweets and linking entities in a batch manner. Nevertheless, the high computational complexity makes this approach infeasible for real-time applications given the high arrival rate of tweets. In this paper, we propose an efficient solution to link entities in tweets by analyzing their social and temporal context. Our proposed framework takes into consideration three features, namely entity popularity, entity recency, and user interest information embedded in social interactions to assist the entity linking task. Effective indexing structures along with incremental algorithms have also been developed to reduce the computation and maintenance costs of our approach. Experimental results based on real tweet datasets verify the effectiveness and efficiency of our proposals.

An increasing amount of motion history data, which is called trajectory, is being collected from different sources such as GPS-enabled mobile devices, surveillance cameras and social networks. However it is hard to store and manage trajectory data in traditional database systems, since its variable lengths and asynchronous sampling rates do not fit disk-based and tuple-oriented structures, which are the fundamental structures of traditional database systems. We implement a novel trajectory storage system that is motivated by the success of column store and recent development of in-memory based databases. In this storage design, we try to explore the potential opportunities, which can boost the performance of query processing for trajectory data. To achieve this, we partition the trajectories into frames as column-oriented storage in order to store the sample points of a moving object, which are aligned by the time interval, within the main memory. Furthermore, the frames can be highly compressed and well structured to increase the memory utilization ratio and reduce the CPU-cache missing. It is also easier for parallelizing data processing on the multi-core server since the frames are mutually independent.

The rapid growth of location-based services provide the potential to understand people's mobility pattern at an unprecedented level, which can also enable food-service industry to accurately predict consumer's dining behavior. In this paper, by leveraging users' historical dining pattern, socio-demographic characteristics and restaurants' attributes, we aim at generating the top-K restaurants for a user's next dining. Compared to previous studies in location prediction which mainly focus on regular mobility patterns, we present a novelty-seeking based dining recommender system, termed NDRS, in consideration of both exploration and exploitation. First, we apply a Conditional Random Field (CRF) with additional constraints to infer users' novelty-seeking statuses by considering both spatial-temporal-historical features and users' socio-demographic characteristics. On the one hand, when a user is predicted to be novelty-seeking, by incorporating the influence of restaurants' contextual factors such as price and service quality, we propose a context-aware collaborative filtering method to recommend restaurants she has never visited before. On the other hand, when a user is predicted to be not novelty-seeking, we then present a Hidden Markov Model (HMM) considering the temporal regularity to recommend the previously visited restaurants. To evaluate the performance of each component as well as the whole system, we conduct extensive experiments, with a large dataset we have collected covering the concerned dining related check-ins, users' demographics, and restaurants' attributes. The results reveal that our system is effective for dining recommendation.

Numerous applications such as data integration, protein detection, and article copy detection share a similar core problem: given a string as the query, how to efficiently find all the similar answers from a large scale string collection. Many existing methods adopt a prefix-filter-based framework to solve this problem, and a number of recent works aim to use advanced filters to improve the overall search performance. In this paper, we propose a gram-based framework to achieve near maximum filter performance. The main idea is to judiciously choose the high-quality grams as the prefix of query according to their estimated ability to filter candidates. As this selection process is proved to be NP-hard problem, we give a cost model to measure the filter ability of grams and develop efficient heuristic algorithms to find high-quality grams. Extensive experiments on real datasets demonstrate the superiority of the proposed framework in comparison with the state-of-art approaches.

The discovery of regions of interest in large cities is an important challenge. We propose and investigate a novel query called the path nearby cluster (PNC) query that finds regions of potential interest (e.g., sightseeing places and commercial districts) with respect to a user-specified travel route. Given a set of spatial objects$O$(e.g., POIs, geo-tagged photos, or geo-tagged tweets) and a query route$q$, if a cluster$c$has high spatial-object density and is spatially close to$q$, it is returned by the query (a cluster is a circular region defined by a center and a radius). This query aims to bring important benefits to users in popular applications such as trip planning and location recommendation. Efficient computation of the PNC query faces two challenges: how to prune the search space during query processing, and how to identify clusters with high density effectively. To address these challenges, a novel collective search algorithm is developed. Conceptually, the search process is conducted in the spatial and density domains concurrently. In the spatial domain, network expansion is adopted, and a set of vertices are selected from the query route as expansion centers. In the density domain, clusters are sorted according to their density distributions and they are scanned from the maximum to the minimum. A pair of upper and lower bounds are defined to prune the search space in the two domains globally. The performance of the PNC query is studied in extensive experiments based on real and synthetic spatial data.

The step of urbanization and modern civilization fosters different functional zones in a city, such as residential areas, business districts, and educational areas. In a metropolis, people commute between these functional zones every day to engage in different socioeconomic activities, e.g., working, shopping, and entertaining. In this paper, we propose a data-driven framework to discover functional zones in a city. Specifically, we introduce the concept of latent activity trajectory (LAT), which captures socioeconomic activities conducted by citizens at different locations in a chronological order. Later, we segment an urban area into disjointed regions according to major roads, such as highways and urban expressways. We have developed a topic-modeling-based approach to cluster the segmented regions into functional zones leveraging mobility and location semantics mined from LAT. Furthermore, we identify the intensity of each functional zone using Kernel Density Estimation. Extensive experiments are conducted with several urban scale datasets to show that the proposed framework offers a powerful ability to capture city dynamics and provides valuable calibrations to urban planners in terms of functional zones.

The last decade has witnessed the prevalence of sensor and GPS technologies that produce a high volume of trajectory data representing the motion history of moving objects. However some characteristics of trajectories such as variable lengths and asynchronous sampling rates make it difficult to fit into traditional database systems that are disk-based and tuple-oriented. Motivated by the success of column store and recent development of in-memory databases, we try to explore the potential opportunities of boosting the performance of trajectory data processing by designing a novel trajectory storage within main memory. In contrast to most existing trajectory indexing methods that keep consecutive samples of the same trajectory in the same disk page, we partition the database into frames in which the positions of all moving objects at the same time instant are stored together and aligned in main memory. We found this column-wise storage to be surprisingly well suited for in-memory computing since most frames can be stored in highly compressed form, which is pivotal for increasing the memory throughput and reducing CPU-cache miss. The independence between frames also makes them natural working units when parallelizing data processing on a multi-core environment. Lastly we run a variety of common trajectory queries on both real and synthetic datasets in order to demonstrate advantages and study the limitations of our proposed storage.

As travel is taking more significant part in our life, route recommendation service becomes a big business and attracts many major players in IT industry. Given a pair of user-specified origin and destination, a route recommendation service aims to provide users with the routes of best travelling experience according to criteria, such as travelling distance, travelling time, traffic condition, etc. However, previous research shows that even the routes recommended by the big-thumb service providers can deviate significantly from the routes travelled by experienced drivers. It means travellers' preferences on route selection are influenced by many latent and dynamic factors that are hard to model exactly with pre-defined formulas. In this work we approach this challenging problem with a very different perspective- leveraging crowds' knowledge to improve the recommendation quality. In this light, CrowdPlanner - a novel crowd-based route recommendation system has been developed, which requests human workers to evaluate candidate routes recommended by different sources and methods, and determine the best route based on their feedbacks. In this paper, we particularly focus on two important issues that affect system performance significantly: (1) how to efficiently generate tasks which are simple to answer but possess sufficient information to derive user-preferred routes; and (2) how to quickly identify a set of appropriate domain experts to answer the questions timely and accurately. Specifically, the task generation component in our system generates a series of informative and concise questions with optimized ordering for a given candidate route set so that workers feel comfortable and easy to answer. In addition, the worker selection component utilizes a set of selection criteria and an efficient algorithm to find the most eligible workers to answer the questions with high accuracy. A prototype system has been deployed to many voluntary mobile clients and extensive tests on real-scenario queries have shown the superiority of CrowdPlanner in comparison with the results given by map services and popular route mining algorithms.

Route recommendation service has become a big business in industry since traveling is now an important part of our daily life. We can travel to unknown places by simply typing in our destination and then following recommendation service's guidance, that a pleasant trip desires them to provide a good route. However, previous research shows that even the routes recommended by the big-thumb service providers can deviate significantly from the routes travelled by experienced drivers since the many latent factors affect drivers' preferences and it is hard for a single route recommendation algorithm to model all of them. In this demo we will present the CrowPlanner system to leverage crowds' knowledge to improve the recommendation quality. It requests human workers to evaluate candidates routes recommended by different sources and methods, and determines the best route based on the feedbacks of these workers. In this demo, we first introduce the core component of our system for smart question generation, and then show several real route recommendation cases and the feedback of users.

The efficiency of spatial query processing is crucial for many applications such as location-based services. In spatial networks, queries like k-NN queries are all based on network distance evaluation. Classic solutions for these queries rely on network expansion and are not efficient enough for large networks. Some approaches have improved the query efficiency but brought considerable space cost for index. To address these problems, we propose a hierarchical graph partitioning based index named Partition Tree. It organizes the vertices of a spatial network into a hierarchy through a series of graph partitioning processes. Meanwhile precomputed distances are associated with this hierarchy to facilitate efficient query processing. Inspired by the observation that queries are usually invoked around objects of interest, we propose a query-oriented optimization on top of the Partition Tree. It uses a cost model to evaluate the influence of the object distribution and partitioning topology on the query efficiency. Then a cost-efficient graph partitioning method is developed based on this cost model. Experimental results on real datasets demonstrate that our proposed index and algorithms have superior performance over the state-of-the-art approaches and are scalable to large spatial networks.

Understanding the dynamics of human daily mobility patterns is essential for the management and planning of urban facilities and services. Travel smart cards, which record users' public transporting histories, capture rich information of users' mobility pattern. This provides the opportunity to discover valuable knowledge from these transaction records. In recent years, research on measuring user similarity for behavior analysis has attracted a lot of attention in applications such as recommendation systems, crowd behavior analysis applications, and numerous data mining tasks. In this paper, our goal is to estimate the similarity between users' travel patterns according to their travel smart card data. The core of our proposal is a novel user similarity measurement, namely, Travel Spatial-Temporal Similarity (TST), which measures the spatial range and temporal similarity between users. Moreover, we also propose a hybrid index structure, which integrates inverted files and cluster-based partitioning, to allow for efficient retrieval of the top-K most similar users. Through experimental evaluation, our proposed approach is shown to deliver scalable performance.

Widely adoption of GPS-enabled devices generates large amounts of trajectories every day. The raw trajectory data describes the movement history of moving objects by a sequence of < longitude, latitude, time-stamp > triples, which are nonintuitive for human to perceive the prominent features of the trajectory, such as where and how the moving object travels. In this demo, we present the STMaker system to help users make sense of individual trajectories. Given a trajectory, STMaker can automatically extract the significant semantic behavior of the trajectory, and summarize the behavior by a short human-readable text. In this paper, we first introduce the phrases of generating trajectory summarizations, and then show several real trajectory summarization cases.

The increasing pervasiveness of location-acquisition technologies has enabled collection of huge amount of trajectories for almost any kind of moving objects. Discovering useful patterns from their movement behaviors can convey valuable knowledge to a variety of critical applications. In this light, we propose a novel concept, called gathering, which is a trajectory pattern modeling various group incidents such as celebrations, parades, protests, traffic jams and so on. A key observation is that these incidents typically involve large congregations of individuals, which form durable and stable areas with high density. In this work, we first develop a set of novel techniques to tackle the challenge of efficient discovery of gathering patterns on archived trajectory dataset. Afterwards, since trajectory databases are inherently dynamic in many real-world scenarios such as traffic monitoring, fleet management and battlefield surveillance, we further propose an online discovery solution by applying a series of optimization schemes, which can keep track of gathering patterns while new trajectory data arrive. Finally, the effectiveness of the proposed concepts and the efficiency of the approaches are validated by extensive experiments based on a real taxicab trajectory dataset.

The advances in location positioning and wireless communication technologies have led to a myriad of spatial trajectories representing the mobility of a variety of moving objects. While processing trajectory data with the focus of spatio-temporal features has been widely studied in the last decade, recent proliferation in location-based web applications (e.g., Foursquare, Facebook) has given rise to large amounts of trajectories associated with activity information, called activity trajectory. In this paper, we study the problem of efficient similarity search on activity trajectory database. Given a sequence of query locations, each associated with a set of desired activities, an activity trajectory similarity query (ATSQ) returns k trajectories that cover the query activities and yield the shortest minimum match distance. An order-sensitive activity trajectory similarity query (OATSQ) is also proposed to take into account the order of the query locations. To process the queries efficiently, we firstly develop a novel hybrid grid index, GAT, to organize the trajectory segments and activities hierarchically, which enables us to prune the search space by location proximity and activity containment simultaneously. In addition, we propose algorithms for efficient computation of the minimum match distance and minimum order-sensitive match distance, respectively. The results of our extensive empirical studies based on real online check-in datasets demonstrate that our proposed index and methods are capable of achieving superior performance and good scalability.

The increasing pervasiveness of location-acquisition technologies has enabled collection of huge amount of trajectories for almost any kind of moving objects. Discovering useful patterns from their movement behaviours can convey valuable knowledge to a variety of critical applications. In this light, we propose a novel concept, called gathering, which is a trajectory pattern modelling various group incidents such as celebrations, parades, protests, traffic jams and so on. A key observation is that these incidents typically involve large congregations of individuals, which form durable and stable areas with high density. Since the process of discovering gathering patterns over large-scale trajectory databases can be quite lengthy, we further develop a set of well thought out techniques to improve the performance. These techniques, including effective indexing structures, fast pattern detection algorithms implemented with bit vectors, and incremental algorithms for handling new trajectory arrivals, collectively constitute an efficient solution for this challenging task. Finally, the effectiveness of the proposed concepts and the efficiency of the approaches are validated by extensive experiments based on a real taxicab trajectory dataset.

Due to the prevalence of GPS-enabled devices and wireless communications technologies, spatial trajectories that describe the movement history of moving objects are being generated and accumulated at an unprecedented pace. Trajectory data in a database are intrinsically heterogeneous, as they represent discrete approximations of original continuous paths derived using different sampling strategies and different sampling rates. Such heterogeneity can have a negative impact on the effectiveness of trajectory similarity measures, which are the basis of many crucial trajectory processing tasks. In this paper, we pioneer a systematic approach to trajectory calibration that is a process to transform a heterogeneous trajectory dataset to one with (almost) unified sampling strategies. Specifically, we propose an anchor-based calibration system that aligns trajectories to a set of anchor points, which are fixed locations independent of trajectory data. After examining four different types of anchor points for the purpose of building a stable reference system, we propose a geometry-based calibration approach that considers the spatial relationship between anchor points and trajectories. Then a more advanced model-based calibration method is presented, which exploits the power of machine learning techniques to train inference models from historical trajectory data to improve calibration effectiveness. Finally, we conduct extensive experiments using real trajectory datasets to demonstrate the effectiveness and efficiency of the proposed calibration system.

Trajectory sharing and searching have received significant attentions in recent years. In this paper, we propose and investigate a novel problem called User Oriented Trajectory Search (UOTS) for trip recommendation. In contrast to conventional trajectory search by locations (spatial domain only), we consider both spatial and textual domains in the new UOTS query. Given a trajectory data set, the query input contains a set of intended places given by the traveler and a set of textual attributes describing the traveler's preference. If a trajectory is connecting/close to the specified query locations, and the textual attributes of the trajectory are similar to the traveler'e preference, it will be recommended to the traveler for reference. This type of queries can bring significant benefits to travelers in many popular applications such as trip planning and recommendation.

The increasing availability of GPS-embedded mobile devices has given rise to a new spectrum of location-based services, which have accumulated a huge collection of location trajectories. In practice, a large portion of these trajectories are of low-sampling-rate. For instance, the time interval between consecutive GPS points of some trajectories can be several minutes or even hours. With such a low sampling rate, most details of their movement are lost, which makes them difficult to process effectively. In this work, we investigate how to reduce the uncertainty in such kind of trajectories. Specifically, given a low-sampling-rate trajectory, we aim to infer its possible routes. The methodology adopted in our work is to take full advantage of the rich information extracted from the historical trajectories. We propose a systematic solution, History based Route Inference System (HRIS), which covers a series of novel algorithms that can derive the travel pattern from historical data and incorporate it into the route inference process. To validate the effectiveness of the system, we apply our solution to the map-matching problem which is an important application scenario of this work, and conduct extensive experiments on a real taxi trajectory dataset. The experiment results demonstrate that HRIS can achieve higher accuracy than the existing map-matching algorithms for low-sampling-rate trajectories.

With the rapidly increasing availability of uncertain data in many important applications such as location-based services, sensor monitoring, and biological information management systems, uncertainty-aware query processing has received a significant amount of research effort from the database community in recent years. In this paper, we investigate a new type of query in the context of uncertain databases, namely uncertain top-k influential sites query (UTkIS query for short), which can be applied in a wide range of application areas such as marketing analysis and mobile services. Since it is not so straightforward to precisely define the semantics of top-k query with uncertain data, in this paper we introduce a novel and more intuitive formulation of the query on the basis of expected rank semantics. To address the efficiency issue caused by possible worlds exploration, we propose effective pruning rules and a divide-and-conquer paradigm such that the number of candidates as well as the number of possible worlds to be considered can be significantly reduced. Finally, we conduct extensive experiments on real data sets to verify the effectiveness and efficiency of the new methods proposed in this paper.

Shortest path query is one of the most fundamental queries in spatial network databases. There exist algorithms that can process shortest path queries in real time. However, many complex applications require more than just the calculation of a single shortest path. For example, one of the common ways to determine the importance (or price) of a vertex or an edge in spatial network is to use Vickrey pricing, which intuitively values the vertex v (or edge e ) based on how much harder for travelling from the sources to the destinations without using v (or e ). In such cases, the alternative shortest paths without using v (or e ) are required. In this article, we propose using a precomputation based approach for both single pair alternative shortest path and all pairs shortest paths processing. To compute the alternative shortest path between a source and a destination efficiently, a naïive way is to precompute and store all alternative shortest paths between every pair of vertices avoiding every possible vertex (or edge), which requires O ( n 4 ) space. Currently, the state of the art approach for reducing the storage cost is to choose a subset of the vertices as center points, and only store the single-source alternative shortest paths from those center points. Such approach has the space complexity of O ( n 2 log n ). We propose a storage scheme termed iSPQF , which utilizes shortest path quadtrees by observing the relationships between each avoiding vertex and its corresponding alternative shortest paths. We have reduced the space complexity from the naïive O ( n 4 ) (or the state of the art O ( n 4 log n )) to O (min( γ, L ) n 1.5 ) with comparable query performance of O ( K ), where K is the number of vertices in the returned paths, L is the diameter of the spatial network, and γ is a value that depends on the structure of the spatial network, which is empirically estimated to be 40 for real road networks. Experiments on real road networks have shown that the space cost of the proposed iSPQF is scalable, and both the algorithms based on iSPQF are efficient.

Trajectories representing the motion of moving objects are typically obtained via location sampling, e.g. using GPS or road-side sensors, at discrete time-instants. In-between consecutive samples, nothing is known about the whereabouts of a given moving object. Various models have been proposed (e.g., sheared cylinders; spacetime prisms) to represent the uncertainty of the moving objects both in unconstrained Euclidian space, as well as road networks. In this paper, we focus on representing the uncertainty of the objects moving along road networks as time-dependent probability distribution functions, assuming availability of a maximal speed on each road segment. For these settings, we introduce a novel indexing mechanism -- UTH (Uncertain Trajectories Hierarchy), based upon which efficient algorithms for processing spatio-temporal range queries are proposed. We also present experimental results that demonstrate the benefits of our proposed methodologies.

The K-Nearest Neighbor search (kNN) problem has been investigated extensively in the past due to its broad range of applications. In this paper we study this problem in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS. Existing research on fuzzy objects mainly focuses on modelling basic fuzzy object types and operations, leaving the processing of more advanced queries such as kNN query untouched. In this paper, we propose two new kinds of kNN queries for fuzzy objects, Ad-hoc kNN query (AKNN) and Range kNN query (RKNN), to find the k nearest objects qualifying at a probability threshold or within a probability range. For efficient AKNN query processing, we optimize the basic best-first search algorithm by deriving more accurate approximations for the distance function between fuzzy objects and the query object. To improve the performance of RKNN search, effective pruning rules are developed to significantly reduce the search space and further speed up the candidate refinement process. The efficiency of our proposed algorithms as well as the optimization techniques are verified with an extensive set of experiments using both synthetic and real datasets.