Recent learning-based methods have reduced the computational complexity of traditional trajectory similarity computation, but state-of-the-art (SOTA) methods still fail to leverage the comprehensive spectrum of trajectory information for similarity modeling. To tackle this problem, we propose RePo, a novel method that jointly encodes Region-wise and Point-wise features to capture both spatial context and fine-grained moving patterns. For region-wise representation, the GPS trajectories are first mapped to grid sequences, and spatial context are captured by structural features and semantic context enriched by visual features. For point-wise representation, three lightweight expert networks extract local, correlation, and continuous movement patterns from dense GPS sequences. Then, a router network adaptively fuses the learned point-wise features, which are subsequently combined with region-wise features using cross-attention to produce the final trajectory embedding. To train RePo, we adopt a contrastive loss with hard negative samples to provide similarity ranking supervision. Experiment results show that RePo achieves an average accuracy improvement of 22.2% over SOTA baselines across all evaluation metrics.

Next point-of-interest (POI) recommendation improves personalized location-based services by predicting users' next destinations based on their historical check-ins. However, most existing methods rely on static datasets and fixed models, limiting their ability to adapt to changes in user behavior over time. To address this limitation, we explore a novel task termed continual next POI recommendation, where models dynamically adapt to evolving user interests through continual updates. This task is particularly challenging, as it requires capturing shifting user behaviors while retaining previously learned knowledge. Moreover, it is essential to ensure efficiency in update time and memory usage for real-world deployment. To this end, we propose GIRAM (Generative Key-based Interest Retrieval and Adaptive Modeling), an efficient, model-agnostic framework that integrates context-aware sustained interests with recent interests. GIRAM comprises four components: (1) an interest memory to preserve historical preferences; (2) a context-aware key encoding module for unified interest key representation; (3) a generative key-based retrieval module to identify diverse and relevant sustained interests; and (4) an adaptive interest update and fusion module to update the interest memory and balance sustained and recent interests. In particular, GIRAM can be seamlessly integrated with existing next POI recommendation models. Experiments on three real-world datasets demonstrate that GIRAM consistently outperforms state-of-the-art methods while maintaining high efficiency in both update time and memory consumption.

Large Language Models (LLMs) have demonstrated remarkable capabilities across various tasks, yet they often exhibit a specific cultural bias, neglecting the values and linguistic diversity of low-resource regions. This cultural bias not only undermines universal equality but also risks reinforcing stereotypes and perpetuating discrimination. To address this, we propose CulFiT, a novel culturally-aware training paradigm that leverages multilingual data and fine-grained reward modeling to enhance cultural sensitivity and inclusivity. Our approach synthesizes diverse cultural-related questions, constructs critique data in multiple culturally relevant languages, and employs fine-grained rewards to decompose cultural texts into verifiable knowledge units for interpretable evaluation. We also introduce GlobalOpinionQA, a multilingual open-ended question-answering dataset designed to evaluate culturally-aware responses in a global context. Extensive experiments on three existing benchmarks and our GlobalOpinionQA demonstrate that CulFiT achieves state-of-the-art open-source model performance in cultural alignment and general reasoning.

With the continued proliferation of Large Language Model (LLM) based chatbots, there is a growing demand for generating responses that are not only linguistically fluent but also consistently aligned with persona-specific traits in conversations.However, existing role-play and persona-based chat approaches rely heavily on static role descriptions, coarse-grained signal space, and low-quality synthetic data, which fail to capture dynamic fine-grained details in human-like chat.Human-like chat requires modeling subtle latent traits, such as emotional tone, situational awareness, and evolving personality, which are difficult to predefine and cannot be easily learned from synthetic or distillation-based data.To address these limitations, we propose a Verbal Variational Auto-Encoding (V-VAE) framework, containing a variational auto-encoding module and fine-grained control space which dynamically adapts dialogue behaviour based on fine-grained, interpretable latent variables across talking style, interaction patterns, and personal attributes.We also construct a highquality dataset, HumanChatData, and benchmark HumanChatBench to address the scarcity of high-quality data in the human-like domain.Experiments show that LLMs based on V-VAE consistently outperform standard baselines on HumanChatBench and DialogBench, which further demonstrates the effectiveness of V-VAE and HumanChatData.

Human mobility prediction is a fundamental problem in spatio-temporal data mining with broad applications in urban computing and transportation systems. While large language models (LLMs) have demonstrated strong sequence modeling capabilities, directly adapting them to structured mobility data remains challenging due to long input sequences and efficiency limitations. In this study, we propose ELP-Mob, an efficient framework that reformulates mobility prediction as a language modeling problem. ELP-Mob employs an instruction-style prompt design that incorporates user mobility profiles, historical trajectories, and target future time slots, enabling LLMs to understand mobility patterns and make predictions. To further enhance efficiency, ELP-Mob includes a data selection strategy that reduces redundancy by sampling informative subsets of training users, and a dynamic splitting strategy with token-length control, which scales to long histories while reducing computational overhead. In the GISCUP 2025, ELP-Mob achieved 6th place on the official leaderboard. The source code is publicly available at https://github.com/chwang0721/ELP-Mob.

Single-Source Personalized PageRank (SSPPR) is a fundamental problem in social network analytics, yet maintaining accurate SSPPR query results in evolving social networks poses significant challenges, especially for real-time applications. Existing approaches often overlook the role of subgraphs and struggle with frequent graph updates, resulting in inefficiency regarding dynamic scenarios. In this study, we define a novel personalized PageRank query, n-steps SSPPR, designed to address the challenges of dynamic environments. To support this query, we propose a baseline solution, Pn-FORA, as a foundational approach. While effective, Pn-FORA is inefficient due to its computationally expensive information update scheme. To overcome these limitations, we propose a multithreaded framework for processing massive-scale n-steps SSPPR queries in real-time over evolving graphs. Central to our framework is the Global Walk Synchronization (GWS) method, ensuring the accuracy of SSPPR scores by synchronizing walk information across nodes as the graph evolves. To further enhance GWS, we introduce an influence-aware graph representation to optimize update propagation. Furthermore, we develop a dynamic workload balancing strategy and precision-aware concurrency controls, which achieve an effective balance between efficiency and accuracy. Extensive experiments on real-world datasets demonstrate that our approach significantly outperforms existing methods, offering superior scalability and efficiency for real-time n-steps SSPPR query processing over large-scale social networks. The source code of our implementation is publicly available at https://github.com/SujunShuai/Work2023.

Next POInt-of-Interest (POI) recommendation predicts a user's next move and facilitates location-based services such as navigation and travel planning. SOTA methods fuse each POI and its contexts (e.g., time, category, and region) into a single representation to model sequential user movement. This hinders the effective utilization of context information, and diverse user preferences are also neglected. To tackle these limitations, we propose Disentangled and Personalized Representation Learning (DPRL) as a novel method for next POI recommendation. DPRL decouples POIs and contexts during representation learning, capturing their sequential regularities independently using separate recurrent neural networks (RNNs). To model the preference of each user, DPRL adopts an aggregation mechanism that integrates dynamic user preferences and spatial-temporal factors into the learned representations. We compare DPRL with 16 state-of-the-art baselines. The results show that DPRL outperforms all baselines and achieves an average accuracy improvement of 10.53% over the best-performing baseline.

Traffic accidents represent a significant concern due to their devastating consequences. The ability to predict future traffic accident risks is of key importance to accident prevention activities in transportation systems. Although existing studies have made substantial efforts to model spatio-temporal correlations, they fall short when it comes to addressing the zero-inflated data issue and capturing spatio-temporal heterogeneity, which reduces their predictive abilities. In addition, improving efficiency is an urgent requirement for traffic accident forecasting. To overcome these limitations, we propose an efficient Spatio-Temporal learning framework for Traffic Accident Risk forecasting (ST-TAR). Taking long-term and short-term data as separate inputs, the ST-TAR model integrates hierarchical multi-view GCN and long short-term cross-attention mechanism to encode spatial dependencies and temporal patterns. We leverage long-term periodicity and short-term proximity for spatio-temporal contrastive learning to capture spatio-temporal heterogeneity. A tailored adaptive risk-level weighted loss function based on efficient locality-sensitive hashing is introduced to alleviate the zero-inflated issue. Extensive experiments on two real-world datasets offer evidence that ST-TAR is capable of advancing state-of-the-art forecasting accuracy with improved efficiency. This makes ST-TAR suitable for applications that require accurate real-time forecasting.

Multi-temporal Point-of-Interest (POI) relationship inference aims to identify evolving relationships among locations over time, providing critical insights for location-based services. While existing studies have made substantial efforts to model relationships with custom-designed graph neural networks, they face the challenge of leveraging POI contextual information characterized by spatial dependencies and temporal dynamics, as well as capturing the heterogeneity of multi-type relationships. To address these challenges, we propose a Triad-Enhanced Spatio-Temporal Network (TESTN), which conceptualizes triads as interactions between relationships for capturing potential interplay. Specifically, TESTN incorporates the spatial 2-hop aggregation layer to capture geographical and semantic information beyond first-order neighbors and the temporal context extractor to integrate relational dynamics within adjacent time segments. Furthermore, we introduce a self-supervised pairwise neighboring relation consistency detection scheme to preserve the heterogeneity of multi-type relationships. Extensive experiments on three real-world datasets demonstrate the superior performance of our TESTN framework.

With the proliferation of GPS-enabled devices such as smartphones, the querying of moving objects has attracted substantial attention, with studies covering joins, range and kNN queries, similarity queries, etc. Challenges arise due to variable sampling frequencies, potential inaccuracies in location samples, and the unavailability of locations between samples. Existing similarity joins often rely on discrete location samples, which fail to capture movement uncertainty and may miss meaningful interactions. To address this limitation, we propose Intersection Similarity Join (IS-Join), a novel approach that identifies object pairs based on the overlap of their motion ranges rather than location-based proximity. We define motion ranges as the spatial regions an object may traverse within a given time period, and introduce an intersection similarity measure that quantifies their overlap. To efficiently process IS-Join queries, we develop a Hybrid Ball-tree indexing structure with a repartitioning strategy, enabling scalable candidate filtering. Additionally, we introduce pre-checking and pruning techniques to further reduce computational overhead. Extensive experiments on two real-world trajectory datasets demonstrate that IS-Join significantly outperforms well-designed baselines, achieving up to a 3x reduction in runtime. Our work opens new opportunities for applications such as urban mobility analysis, traffic monitoring, wildlife tracking, and contact tracing.

Trajectory representation learning (TRL) maps trajectories to vector embeddings and facilitates tasks such as trajectory classification and similarity search. State-of-the-art (SOTA) TRL methods transform raw GPS trajectories to grid or road trajectories to capture high-level travel semantics, i.e., regions and roads. However, they lose fine-grained spatial-temporal details as multiple GPS points are grouped into a single grid cell or road segment. To tackle this problem, we propose the BLU rred Encoding method, dubbed BLUE, which gradually reduces the precision of GPS coordinates to create hierarchical patches with multiple levels. The low-level patches are small and preserve fine-grained spatial-temporal details, while the high-level patches are large and capture overall travel patterns. To complement different patch levels with each other, our BLUE is an encoder-decoder model with a pyramid structure. At each patch level, a Transformer is used to learn the trajectory embedding at the current level, while pooling prepares inputs for the higher level in the encoder, and up-resolution provides guidance for the lower level in the decoder. BLUE is trained using the trajectory reconstruction task with the MSE loss. We compare BLUE with 8 SOTA TRL methods for 3 downstream tasks, the results show that BLUE consistently achieves higher accuracy than all baselines, outperforming the best-performing baselines by an average of 30.90%. Our code is available at https://github.com/slzhou-xy/BLUE.

Trajectory representation learning (TRL) maps trajectories to vectors that can be used for many downstream tasks. Existing TRL methods use either grid trajectories, capturing movement in free space, or road trajectories, capturing movement in a road network, as input. We observe that the two types of trajectories are complementary, providing either region and location information or providing road structure and movement regularity. Therefore, we propose a novel multimodal TRL method, dubbed GREEN, to jointly utilize Grid and Road trajectory Expressions for Effective representatioN learning. In particular, we transform raw GPS trajectories into both grid and road trajectories and tailor two encoders to capture their respective information. To align the two encoders such that they complement each other, we adopt a contrastive loss to encourage them to produce similar embeddings for the same raw trajectory and design a mask language model (MLM) loss to use grid trajectories to help reconstruct masked road trajectories. To learn the final trajectory representation, a dual-modal interactor is used to fuse the outputs of the two encoders via cross-attention. We compare GREEN with 7 state-of-the-art TRL methods for 3 downstream tasks, finding that GREEN consistently outperforms all baselines and improves the accuracy of the best-performing baseline by an average of 15.99%. Code and data are available at https://github.com/slzhou-xy/GREEN.

Trajectory Similarity Join (TS-Join), as a fundamental operation in trajectory data analytics, has been extensively investigated by existing studies in data science. However, existing solutions are almost designed for offline static trajectories, which cannot ensure real-time feedback. In addition, the join results retrieved from existing solutions generally contain a large proportion of outdated similar pairs, making them inapplicable to evolving trajectories. In this light, we study a novel problem of online time-aware trajectory similarity join: Given a stream of evolving trajectories, we aim to dynamically discover trajectory pairs whose spatio-temporal similarity is no less than a specified threshold in a real-time manner. We innovatively introduce a time-aware exponential-decaying similarity function to eliminate outdated results. To support real-time querying over large populations of trajectories, we develop a Parallel Online Trajectory Similarity Join (POTSJ) framework with workload balancing techniques. We further enhance join efficiency through pruning strategies and tailored approximation techniques. The POTSJ framework we propose, which incorporates these elements, is capable of processing online TS-Join while simultaneously satisfying three key objectives: real-time result updates, comprehensive trajectory evaluation, and scalability. Extensive experiments on real-world datasets validate the efficiency and scalability of our POTSJ framework in processing online TS-Join.

Road trajectory generation creates synthetic yet realistic trajectories to tackle data collection costs and privacy concerns. Existing methods generate a trajectory either segment-by-segment using sequence models or holistically in one step using diffusion models. Sequence-based models have good regularity and consistency (i.e., resemble the input trajectories) but lack diversity, while diffusion-based models enhance diversity but sacrifice regularity and consistency. To combine the merits of existing methods, we propose Seed, by bridging sequence and diffusion models for trajectory generation. In particular, Seed adopts a conditional diffusion structure, where a Transformer models the movement of each trajectory along the road segments, and conditioned on the Transformer's output, a diffusion model recovers the next road segment from random noise. The rationale is that the Transformer captures sequential patterns for regularity and consistency, while the diffusion model introduces diversity by recovering from noise. We use a trajectory reconstruction task to train Seed, and design a curriculum learning strategy to accelerate convergence. We compare Seed with 8 state-of-the-art trajectory generation methods on 3 datasets, and the results show that Seed improves the best-performing baseline by over 50%.

Abstract Trajectory similarity computation is a fundamental function in many applications of urban data analysis, such as trajectory clustering, trajectory compression, and route planning. In this paper, we study trajectory similarity computation on the road network. However, existing methods have been designed primarily for road network trajectories with spatial information, while ignoring the important temporal information in the real world. To solve this problem, we propose a Feature Enhanced Spatial–Temporal trajectory similarity computation framework FEST, which is a graph neural network (GNN) and sequence model pipeline. We first use the GNN model to capture global information on the road network. In particular, we enhance the process with multi-graph to learn multiple signals from the road network on different aspects. In addition to the original road network topology signal, we also take into account the content signal to learn spatial–temporal features from trajectory traffic, as well as the adaptive similarity signal of the road network to learn hidden features. From these three signals, we construct a multi-graph and use GCN to learn road intersection embedding jointly. Next, we propose a feature-enhanced Transformer with spatial–temporal information to learn correlation within the trajectory, and we further use mean-pooling to get the final trajectory embedding. We compare FEST with six trajectory similarity computation methods on two real-world datasets. The results show that FEST consistently outperforms all baselines and can improve the accuracy of the best-performing baseline.

Abstract Synthetic trajectory generation is essential for addressing privacy concerns and data scarcity in mobility-related applications. Although existing solutions effectively capture general spatio-temporal features, they often overlook co-movement patterns among moving objects, which are crucial for applications such as traffic simulation, ride-sharing, and crowd modeling. Moreover, most approaches rely on road network representations, limiting generalization and failing to preserve fine-grained mobility trends. To tackle these challenges, we propose CA-Gen, a Co-movement Aware trajectory generation framework based on Generative Adversarial Networks (GANs). Instead of employing road vertex mapping, we introduce a hot grid-cell based trajectory representation to enhance robustness and generalization. To better simulate real-world co-movement patterns, we design a way-point guided search algorithm based on frequent subsequence mining. Extensive experiments on real-world datasets show that CA-Gen significantly outperforms existing SOTA methods, generating realistic trajectories that retain both individual mobility characteristics and co-movement trends, providing a privacy-preserving and high-fidelity solution for mobility analysis.

Matching similar pairs of trajectories, called trajectory similarity join, is a fundamental functionality for the Internet of Everything (IoE). We obverse that keyword-augmented trajectories are becoming increasingly popular. In this light, we investigate semantic trajectory similarity (STS) join that consists of two subproblems, threshold-based STS Join and top-k STS (k-STS) Join. Each semantic trajectory is a sequence of geo-textual objects with both location and text information. Specifically, given two sets of semantic trajectories and a threshold$\theta $or result number k, the STS Join returns all pairs of semantic trajectories from the two sets with spatio-textual similarity no less than$\theta $, and the k-STS Join returns k most similar pairs of semantic trajectories from the two sets. To enable efficient STS and k-STS Joins processing on large sets of semantic trajectories, we present a two-phase parallel search algorithm. We first group semantic trajectories based on their text information. The algorithm’s per-group searches are independent of each other and thus can be performed in parallel. We generate spatial and textual summaries for each trajectory batch and develop batch filtering techniques to prune unqualified trajectory pairs in a batch mode. Next, we propose a divide-and-conquer algorithm to derive bounds of spatial similarity and textual similarity between two semantic trajectories, which enable us filter out dissimilar trajectory pairs efficiently. Further, hierarchical batch filtering join algorithm is developed to process k-STS Join. Experimental study with large semantic trajectory data confirms that our algorithm of processing semantic trajectory join is capable of substantially outperforming well-designed baselines.

With the increasing availability of time-dependent objects on Social internet of Things (SIoT), taking advantage of this data for SIoT-based route planning and recommendation is becoming increasingly imperative. To facilitate IoT-based route planning and recommendation, Trajectory Search by Locations (TSL) has been serving as a fundamental operation for data cleaning based on personalized requirements. However, existing TSL methods regard each trajectory as an indivisible object of time series. Because that the lengths and spatial distributions of trajectories may vary, traditional TRL methods often fail to return high-quality results, especially when the trajectory data is spare. Such limitation is considered to be a major bottleneck for improving the effectiveness of SIoT-based route planning and recommendation. To address the limitation, we propose a parallel mechanism for handling the problem of Trajectory Search by Locations through Parallel split-and-combine (TSL-Psc). The TSL-Psc problem is described as follows. Given a set of trajectories, a query sequence Q consisting of a sequence of timestamped locations, and a spatio-temporal similarity threshold θ, we retrieve a combined trajectory composed of sub-trajectories that (i) has similarity to Q no less than θ and (ii) contains the minimum number of sub-trajectory combinations. The resulting functionality of TSL-Psc targets a broad range of time-sensitive applications regarding SIoT, including traffic analysis, real-time group route planning, and ridesharing. To enable efficient TSL-Psc computation of trajectory data, we develop a three-phase Joint-Split Parallel Search (JSPS) algorithm on the basis of FSPS and GSPS. JSPS consists of pre-checking, split, and combine phases. We develop a spatial-first expansion algorithm and a temporal-first expansion algorithm that are capable of pruning search space in both spatial and temporal domains. Comprehensive experiments conducted on real-world datasets provide valuable insights into the algorithm’s performance, demonstrating that the proposed TSL-Psc problem formulation produces high-quality outcomes while the search algorithms deliver high-standard efficiency and scalability.

The rapid advancement of location and information technologies has generated a significant volume of human mobility data, which has been extensively utilized in spatiotemporal recommendation systems, including personalized point-of-interest recommendation, route recommendation, and location-aware event recommendation. Achieving high-quality recommendation results necessitates excellent quality of input trajectory data. However, trajectories obtained from GPS-enabled devices often contain missing and erroneous data that is unevenly distributed over time and highly sparse, which significantly hampers the effectiveness spatiotemporal data analytics. Therefore, trajectory recovery plays an important role in spatiotemporal recommendation systems. The objective of trajectory recovery is to utilize historical trajectories to restore missing locations, providing high-quality data for spatiotemporal recommendation systems. The development of an effective trajectory recovery mechanism faces three major challenges: 1) Complex and multi-granularity transition patterns among different locations; 2) Difficulty in discovering spatio-temporal dependencies; and 3) Data sparsity and noise. To address these challenges, we propose an attentional model with spatio-temporal recurrent neural networks, ARMove, to recover human mobility from long and sparse trajectories. In ARMove, we first design a spatio-temporal weighted recurrent neural network to capture users' long-term preferences. Next, we introduce a multi-granularity trajectory encoder to model complex transition patterns and multi-level periodicity of human mobility. An attention-based history aggregation module is proposed to leverage historical mobility information. Extensive evaluation results reveal that our model outperforms the state-of-the-art models, demonstrating its ability to reconstruct high-quality and fine-grained human mobility trajectories.

Next point-of-interest (POI) recommendationpredicts user’s next movement and facilitates location-based applications such as destination suggestion and travel planning. State-of-the-art (SOTA) methods learn an adaptive graph from user trajectories and compute POI representations using graph neural networks (GNNs). However, a single graph cannot capture thediverse dependenciesamong the POIs (e.g., geographical proximity and transition frequency). To tackle this limitation, we propose theAdaptiveGraphContrastiveLearning(AGCL) framework. AGCL constructs multiple adaptive graphs, each modeling a kind of POI dependency and producing one POI representation; and the POI representations from different graphs are merged into amulti-facet representationthat encodes comprehensive information. To train the POI representations, we tailor agraph-based contrastive learning, which encourages the representations of similar POIs to align and dissimilar POIs to differentiate. Moreover, to learn the sequential regularities of user trajectories, we design an attention mechanism to integrate spatial-temporal information into the POI representations. An explicitspatial-temporal biasis also employed to adjust the predictions for enhanced accuracy. We compare AGCL with 10 state-of-the-art baselines on 3 datasets. The results show that AGCL outperforms all baselines and achieves an improvement of 10.14% over the best performing baseline in average accuracy.

Trajectory similarity computation serves as a fundamental functionality of various spatial information applications. Although existing deep learning similarity computation methods offer better efficiency and accuracy than non-learning solutions, they are still immature in trajectory embedding and suffer from poor generality and heavy preprocessing for training. Targeting these limitations, we propose a novel framework named KGTS based on knowledge graph grid embedding, prompt trajectory embedding, and unsupervised contrastive learning for improved trajectory similarity computation. Specifically, we first embed map grids with a GRot embedding method to vigorously grasp the neighbouring relations of grids. Then, a prompt trajectory embedding network incorporates the resulting grid embedding and extracts trajectory structure and point order information. It is trained by unsupervised contrastive learning, which not only alleviates the heavy preprocessing burden but also provides exceptional generality with creatively designed strategies for positive sample generation. The prompt trajectory embedding adopts a customized prompt paradigm to mitigate the gap between the grid embedding and the trajectory embedding. Extensive experiments on two real-world trajectory datasets demonstrate the superior performance of KGTS over state-of-the-art methods.

The next Point-of-interest recommendation has attracted extensive research interest recently, which predicts users' subsequent movements. The main challenge is how to effectively capture users' personalized sequential transitions in check-in trajectory, and various methods have been developed. However, most existing studies ignore the temporal information when conducting the next POI recommendation. To fill this gap, we investigate a time-specific next POI recommendation task, which additionally incorporates the target time information. We propose a brand new Time2Rotation technique to capture the temporal information. Different from conventional methods, we represent timeslots as rotation vectors and then perform the rotation operations. Based on the Time2Rotation technique, we propose a novel rotation-based temporal attention network, namely ROTAN, for the time-specific next POI recommendation task. The ROTAN begins by building a collaborative POI transition graph, capturing the asymmetric temporal influence in sequential transitions. After that, it incorporates temporal information into the modeling of individual check-in trajectories, extracting separate representations for user preference and POI influence to reflect their distinct temporal patterns. Lastly, the target time is integrated to generate recommendations. Extensive experiments are conducted on three real-world datasets, which demonstrates the advantages of the proposed Time2Rotation technique and ROTAN recommendation model.

A trajectory is a sequence of timestamped point locations that captures the movement of an object such as a vehicle. Such trajectories encode complex spatial and temporal patterns and provide rich information about object mobility and the underlying infrastructures, typically road networks, within which the movements occur. A trajectory dataset is evolving when new trajectories are included continuously. The ability to detect anomalous trajectories in online fashion in this setting is fundamental and challenging functionality that has many applications, e.g., location-based services. State-of-the-art solutions determine anomalies based on the shapes or routes of trajectories, ignoring potential anomalies caused by different sampling rates or time offsets. We propose a multi-scale model, termed MST-OATD, for anomalous streaming trajectory detection that considers both the spatial and temporal aspects of trajectories. The model's multi-scale capabilities aim to enable extraction of trajectory features at multiple scales. In addition, to improve model evolvability and to contend with changes in trajectory patterns, the model is equipped with a learned ranking model that updates the training set as new trajectories are included. Experiments on real datasets offer evidence that the model can outperform state-of-the-art solutions and is capable of real-time anomaly detection. Further, the learned ranking model achieves promising results when updating the training set with newly arrived trajectories.

Trajectory representation learning (TRL) maps trajectories to vectors that can then be used for various downstream tasks, including trajectory similarity computation, trajectory classification, and travel-time estimation. However, existing TRL methods often produce vectors that, when used in downstream tasks, yield insufficiently accurate results. A key reason is that they fail to utilize the comprehensive information encompassed by trajectories. We propose a self-supervised TRL framework, called RED, which effectively exploits multiple types of trajectory information. Overall, RED adopts the Transformer as the backbone model and masks the constituting paths in trajectories to train a masked autoencoder (MAE). In particular, RED considers the moving patterns of trajectories by employing a R oad-aware masking strategy that retains key paths of trajectories during masking, thereby preserving crucial information of the trajectories. RED also adopts a spatial-temporal-user joint E mbedding scheme to encode comprehensive information when preparing the trajectories as model inputs. To conduct training, RED adopts D ual-objective task learning : the Transformer encoder predicts the next segment in a trajectory, and the Transformer decoder reconstructs the entire trajectory. RED also considers the spatial-temporal correlations of trajectories by modifying the attention mechanism of the Transformer. We compare RED with 9 state-of-the-art TRL methods for 4 downstream tasks on 3 real-world datasets, finding that RED can usually improve the accuracy of the best-performing baseline by over 5%.

Next Point-Of-Interest (POI) recommendation plays an important role in various location-based services. Its main objective is to predict the user's next interested POI based on her previous check-in information. Most existing methods directly use users' historical check-in trajectories to construct various graphs to assist sequential models to complete this task. However, as users' check-in data is extremely sparse, it is difficult to capture the potential relations between POIs by directly using these check-in data. To this end, we propose the Sequence-based Neighbour search and Prediction Model (SNPM) for next POI recommendation. In SNPM, the RotatE knowledge graph embedding and Eigenmap methods are used to extract POI relationships implied in check-in data, and build the POI similarity graph. Then, we enhance the model's generalized representations of POIs' general features by aggregating similar POIs. As the context is typically rich and valuable when making Next POI predictions, the sequence model selects which POIs to aggregate not only depends on the current state, but also needs to consider the previous POI sequence. Therefore, we construct a Sequence-based, Dynamic Neighbor Graph (SDNG) to find the similarity neighbourhood and develop a Multi-Step Dependency Prediction model (MSDP) inspired by RotatE, which explicitly leverage information from previous states. We evaluate the proposed model on two real-world datasets, and the experimental results show that the proposed method significantly outperforms existing state-of-the-art POI recommendation methods.

The prevalence of region-based urban data has opened new possibilities for exploring correlations among regions to improve urban planning and smart-city solutions. Region embedding, which plays a critical role in this endeavor, faces significant challenges related to the varying nature of city data and the effectiveness of downstream applications. In this paper, we propose a novel framework, HREP (Heterogeneous Region Embedding with Prompt learning), which addresses both intra-region and inter-region correlations through two key modules: Heterogeneous Region Embedding (HRE) and prompt learning for different downstream tasks. The HRE module constructs a heterogeneous region graph based on three categories of data, capturing inter-region contexts such as human mobility and geographic neighbors, and intraregion contexts such as POI (Point-of-Interest) information. We use relation-aware graph embedding to learn region and relation embeddings of edge types, and introduce selfattention to capture global correlations among regions. Additionally, we develop an attention-based fusion module to integrate shared information among different types of correlations. To enhance the effectiveness of region embedding in downstream tasks, we incorporate prompt learning, specifically prefix-tuning, which guides the learning of downstream tasks and results in better prediction performance. Our experiment results on real-world datasets demonstrate that our proposed model outperforms state-of-the-art methods.

Empathy is one of the fundamental abilities of dialog systems. In order to build more intelligent dialogue systems, it’s important to learn how to demonstrate empathy toward others. Existing studies focus on identifying and leveraging the user’s coarse emotion to generate empathetic responses. However, human emotion and dialog act (e.g., intent) evolve as the talk goes along in an empathetic dialogue. This leads to the generated responses with very different intents from the human responses. As a result, empathy failure is ultimately caused. Therefore, using fine-grained emotion and intent sequential data on conversational emotions and dialog act is crucial for empathetic response generation. On the other hand, existing empathy models overvalue the empathy of responses while ignoring contextual relevance, which results in repetitive model-generated responses. To address these issues, we propose a Multi-Factor sequence Fusion framework (EmpMFF) based on conditional variational autoencoder. To generate empathetic responses, the proposed EmpMFF encodes a combination of contextual, emotion, and intent information into a continuous latent variable, which is then fed into the decoder. Experiments on the EmpatheticDialogues benchmark dataset demonstrate that EmpMFF exhibits exceptional performance in both automatic and human evaluations.

Abstract Re-ranking is to refine the candidate ranking list of recommended items, such that the re-ranked list attracts users to purchase or click more items than the candidate one without re-ranking. Items in the candidate list are often ranked by their relevance to users’ interests. It is thus important to exploit the mutual influence between items in the re-ranking process. Existing re-ranking models focus on only the pairwise influence between two items, and have limited capability to exploit the local mutual influence in a group of items. Users often show successive interests on a group of relevant items, e.g., mobile phone, phone covers, wireless headset, namely scene. We propose a novel re-ranking model that jointly exploits the local mutual influence in scenes and the global mutual influence between different scenes. Scene representations are learned by GNN and multi-head attention, where GNN aims to learn local mutual influence while multi-head attention is to learn global mutual influence. To study the interaction between users and scenes, matrix factorization on users is utilized to obtain the user preference, which can be further applied to scenes to compute the scene scores. The final re-ranking list is generated by sorting the predicted scores of all scenes. To further mine user history information and item related user information, we also develop the extension pretraining module which relies on mask mechanism to support users and items high-quality embedding generation. We conduct a comprehensive evaluation on several real-world datasets. The experimental results demonstrate that our model substantially outperforms existing approaches.

Graph embedding, which aims to learn low-dimensional node representations to preserve original graph structures, has attracted extensive research interests. However, most existing graph embedding models represent nodes in Euclidean spaces, which cannot effectively preserve complex patterns, e.g., hierarchical structures. Very recently, several hyperbolic embedding models have been proposed to preserve the hierarchical information in negative curvature spaces. Nevertheless, existing hyperbolic models fail to model the asymmetric proximity between nodes. To address this, we investigate a new asymmetric hyperbolic network representation problem, which targets at jointly preserving the hierarchical structures and asymmetric proximity for general directed graphs. We solve this problem by proposing a novelRotatedLorentzianEmbedding (ROLE) model, which yields two main benefits. First, our model can effectively capture both implicit and explicit hierarchical structures that come from the network topology and category information of nodes, respectively. Second, it can model the asymmetric proximity using rotation transformations. Specifically, we represent each node with a Lorentzian embedding vector, and learn two rotation matrices to reflect the direction of edges. We conduct extensive experiments on four real-world directed graph datasets. Empirical results demonstrate that the proposed approach consistently outperforms various state-of-the-art embedding models. In particular, ROLE achieves HR@1 scores up to 19.8% higher and NDCG@5 scores up to 11.3% higher than the best baselines on the task of node recommendation.

Recent neural architectures in sequence labeling have yielded state-of-the-art performance on single domain data such as newswires. However, they still suffer from (i) requiring massive amounts of training data to avoid overfitting; (ii) huge performance degradation when there is a domain shift in the data distribution between training and testing. In this paper, we investigate the problem of domain adaptation for sequence labeling under homogeneous and heterogeneous settings. We propose MetaSeq, a novel meta-learning approach for domain adaptation in sequence labeling. Specifically, MetaSeq incorporates meta-learning and adversarial training strategies to encourage robust, general and transferable representations for sequence labeling. The key advantage of MetaSeq is that it is capable of adapting to new unseen domains with a small amount of annotated data from those domains. We extensively evaluate MetaSeq on named entity recognition, part-of-speech tagging and slot filling tasks under homogeneous and heterogeneous settings. The experimental results show that MetaSeq achieves state-of-the-art performance against eight baselines. Impressively, MetaSeq surpasses the in-domain performance using only 16.17% and 7% of target domain data on average for homogeneous settings, and 34.76%, 24%, 22.5% of target domain data on average for heterogeneous settings.

The set similarity join finds all pairs of similar sets from two collections of sets. It has many real world applications, such as personalized recommendation and community mining. In this paper, we study the problem of computing the similarity join in a dynamic context, where the sets are updated dynamically. This, however, is inefficient with the state-of-the-art join methods, because they usually assume that data collections are static and have to compute the join result from scratch whenever a set is updated. To address this issue, we propose${{\sf ALJoin}}$, an adaptive filtering approach that computes the join result incrementally based on the update logs. We first investigate the effect of set updates on the similarity values, and on this basis we propose to build a neighborhood index for each set. The neighborhood index of a specific set consists of any other sets that can be transformed into its similar sets within a threshold number of update operations.${{\sf ALJoin}}$then uses this index to effectively identify both similar and dissimilar set pairs based on their update logs. To efficiently build the neighborhood index, we devise several filtering techniques and propose a “lazy-forward” method to reduce the computational cost. In addition, to improve the efficiency on varying workloads, we propose an analytical cost model, and design an online algorithm with performance guarantees to dynamically consolidate the update logs and adapt the neighborhood indexes. We evaluated our method using four real-world datasets. Experimental results show that our approach outperforms existing methods by up to$3.7\times$.

Infectious diseases have been recognized as major public health concerns for decades. Close contact discovery is playing an indispensable role in preventing epidemic transmission. In this light, we study the continuous exposure search problem: Given a collection of moving objects and a collection of moving queries, we continuously discover all objects that have been directly and indirectly exposed to at least one query over a period of time. Our problem targets a variety of applications, including but not limited to disease control, epidemic pre-warning, information spreading, and co-movement mining. To answer this problem, we develop an exact group processing algorithm with optimization strategies. Further, we propose an approximate algorithm that substantially improves the efficiency without false dismissal. Extensive experiments offer insight into effectiveness and efficiency of our proposed algorithms.

Next Point-of Interest (POI) recommendation plays an important role in location-based applications, which aims to recommend the next POIs to users that they are most likely to visit based on their historical trajectories. Existing methods usually use rich side information, or customized POI graphs to capture the sequential patterns among POIs. However, the graphs only focus on connectivity between POIs. Few studies propose to explicitly learn a weighted POI graph, which could reflect the transition patterns among POIs and show the importance of its different neighbors for each POI. In addition, these approaches simply utilize the user characteristics for personalized POI recommendation without sufficient consideration. To this end, we construct a novel User-POI Knowledge Graph with strong representation ability, called Spatial-Temporal Knowledge Graph (STKG). STKG is used to learn the representations of each node (i.e., user, POI) and each edge. Then, we design a similarity function to construct our POI transition graph based on the learned representations. To incorporate the learned graph into sequential model, we propose a novel network Graph-Flashback for recommendation. Graph-Flashback applies a simplified Graph Convolution Network (GCN) on the POI transition graph to enrich the representation of each POI. Further, we define a similarity function to consider both spatiotemporal information and user preference in modelling sequential regularity. Experimental results on two real-world datasets show that our proposed method achieves the state-of-the-art performance and significantly outperforms all existing solutions.

Recommendation systems have been extensively investigated by existing studies. However, previous work only targets a single type of user behavior (e.g., purchase) while ignoring the fact that users usually have multiple behaviors when browsing products (e.g., view, click, add-to-cart). These different behaviors can generate a large number of attributes about users. Meanwhile, in typical collaborative filtering (CF) systems, users and items are generally handled separately. Therefore, the associativity between users and items is not taken into account. To solve the above problems, we propose a novel framework named as Multiple Behaviors recommendation with Graph Learning (MBGL). To capture multiple characteristics of users and items, we construct a knowledge graph with multiple entity relations between users and items from a variety of data, such as purchase, view, and add-to-cart. We apply the knowledge graph embedding (KGE) method to learn the pre-training embedding of entity and relation. To better learn high-hop embedding from multi-behavior data, we construct a heterogeneous user-item graph and further design relation-aware GAT to learn graph embedding with relation type. To support high-order dependency in the graph, we introduce the residual network to solve feature smoothing and vanishing gradient problems. Moreover, to obtain the high-quality user and item embedding, we design an attention fusion layer to learn the fusion embedding and adopt the multi-task learning to predict users' preferences under different behaviors. Experiment results on real-world dataset show that our model outperforms other recommendation methods.

With the prevalence of location based services, activity trajectories are being generated at a rapid pace. The activity trajectory data enriches traditional trajectory data with semantic activities of users, which not only shows where the users have been, but also the preference of users. However, the large volume of data is expensive for people to explore. To address this issue, we study the problem of Diversity-aware Activity Trajectory Selection (DaATS). Given a region of interest for a user, it finds a small number of representative activity trajectories that can provide the user with a broad coverage of different aspects of the region. The problem is challenging in both the efficiency of trajectory similarity computation and subset selection. To tackle the two challenges, we propose a novel solution by: (1) exploiting a deep metric learning method to speedup the similarity computation; and (2) proving that DaATS is an NP-hard problem, and developing an efficient approximation algorithm with performance guarantees. Experiments on two real-world datasets show that our proposal significantly outperforms state-of-the-art baselines.

Recently, network embedding has attracted extensive research interest. Most existing network embedding models are based on Euclidean spaces. However, Euclidean embedding models cannot effectively capture complex patterns, especially latent hierarchical structures underlying in real-world graphs. Consequently, hyperbolic representation models have been developed to preserve the hierarchical information. Nevertheless, existing hyperbolic models only capture the first-order proximity between nodes. To this end, we propose a new embedding model, named Node2LV, that learns the hyperbolic representations of nodes using squared Lorentzian distances. This yields three advantages. First, our model can effectively capture hierarchical structures that come from the network topology. Second, compared with the conventional hyperbolic embedding methods that use computationally expensive Riemannian gradients, it can be optimized in a more efficient way. Lastly, different from existing hyperbolic embedding models, Node2LV captures higher-order proximities. Specifically, we represent each node with two hyperbolic embeddings, and make the embeddings of related nodes close to each other. To preserve higher-order node proximity, we use a random walk strategy to generate local neighborhood context. We conduct extensive experiments on four different types of real-world networks. Empirical results demonstrate that Node2LV significantly outperforms various graph embedding baselines.

We study the problem of subtrajectory alignment over massive-scale trajectory data. Given a collection of trajectories, a subtrajectory alignment query returns new targeted trajectories by splitting and aligning existing trajectories. The resulting functionality targets a range of applications, including trajectory data analysis, route planning and recommendation, ridesharing, and general location-based services. To enable efficient and effective subtrajectory alignment computation, we propose a novel search algorithm and filtering techniques that enable the use of the parallel processing capabilities of modern processors. Experiments with large trajectory datasets are conducted for evaluating the performance of our proposal. The results show that our solution to the subtrajectory alignment problem can generate high-quality results and are capable of achieving high efficiency and scalability.

Route planning and recommendation have attracted much attention for decades. In this paper, we study a continuous optimal route combination problem: Given a dynamic road network and a stream of trip queries, we continuously find an optimal route combination for each new query batch over the query stream such that the total travel time for all routes is minimized. Each route corresponds to a planning result for a particular trip query in the current query batch. Our problem targets a variety of applications, including traffic-flow management, real-time route planning and continuous congestion prevention. The exact algorithm bears exponential time complexity and is computationally prohibitive for application scenarios in dynamic traffic networks. To address this problem, a self-aware batch processing algorithm is developed in this paper. Extensive experiments offer insight into the accuracy and efficiency of our proposed algorithms.

Named entity recognition (NER) aims to recognize mentions of rigid designators from text belonging to predefined semantic types, such as person, location, and organization. In this article, we focus on a fundamental subtask of NER, named entity boundary detection, which aims at detecting the start and end boundaries of an entity mention in the text, without predicting its semantic type. The entity boundary detection is essentially a sequence labeling problem. Existing sequence labeling methods either suffer from sparse boundary tags (i.e., entities are rare and nonentities are common) or they cannot well handle the issue of variable size output vocabulary (i.e., need to retrain models with respect to different vocabularies). To address these two issues, we propose a novel entity boundary labeling model that leverages pointer networks to effectively infer boundaries depending on the input sequence. On the other hand, training models on source domains that generalize to new target domains at the test time are a challenging problem because of the performance degradation. To alleviate this issue, we propose Metabdry, a novel domain generalization approach for entity boundary detection without requiring any access to target domain information. Especially, adversarial learning is adopted to encourage domain-invariant representations. Meanwhile, metalearning is used to explicitly simulate a domain shift during training so that metaknowledge from multiple resource domains can be effectively aggregated. As such, Metabdry explicitly optimizes the capability of "learning to generalize," resulting in a more general and robust model to reduce the domain discrepancy. We first conduct experiments to demonstrate the effectiveness of our novel boundary labeling model. We then extensively evaluate Metabdry on eight data sets under domain generalization settings. The experimental results show that Metabdry achieves state-of-the-art results against the recent seven baselines.

With the proliferation of GPS-based data (e.g., routes and trajectories), it is of great importance to enable the functionality of real-time route search and recommendations. We define and study a novel Continuous Route-Search-by-Location (C-RSL) problem to enable real-time route search by locations for a large number of users over route data streams. Given a set of C-RSL queries where each query q contains a set of places q.O to visit and a threshold q.θ, we continuously feed each query q with routes that has similarity to q.O no less than q.θ. We also extend our proposal to support top-k C-RSL problem where each query continuously maintains k most similar routes. The C-RSL problem targets a variety of applications, including real-time route planning, ridesharing, and other location-based services that have real-time demand. To enable efficient route matching on a large number of C-RSL queries, we develop novel parallel route matching algorithms with good time complexity. Extensive experiments with real data offer insight into the performance of our algorithms, indicating that our proposal is capable of achieving high efficiency and scalability.

Pricing is essential in optimizing transportation resource allocation. Congestion pricing is widely used to reduce urban traffic congestion. We propose and investigate a novel Dynamic Pricing Strategy (DPS) to price travelers' trips in intelligent transportation platforms (e.g., DiDi, Lyft, Uber). The trips are charged according to their “congestion contributions” to global urban traffic systems. The dynamic pricing strategy retrieves a matching between n travelers' trips and the potential travel routes (each trip has k potential routes) to minimize the global traffic congestion. We believe that DPS holds the potential to benefit society and the environment, such as reducing traffic congestion and enabling smarter and greener transportation. The DPS problem is challenging due to its high computation complexity (there exist kn matching possibilities). We develop an efficient and effective approximate matching algorithm based on local search, as well as pruning techniques to further enhance the matching efficiency. The accuracy and efficiency of the dynamic pricing strategy are verified by extensive experiments on real datasets.

Matching similar pairs of trajectories, called trajectory similarity join, is a fundamental functionality in spatial data management. We consider the problem of semantic trajectory similarity join (STS-Join). Each semantic trajectory is a sequence of Points-of-interest (POIs) with both location and text information. Thus, given two sets of semantic trajectories and a threshold θ, the STS-Join returns all pairs of semantic trajectories from the two sets with spatio-textual similarity no less than θ. This join targets applications such as term-based trajectory near-duplicate detection, geo-text data cleaning, personalized ridesharing recommendation, keyword-aware route planning, and travel itinerary recommendation.With these applications in mind, we provide a purposeful definition of spatio-textual similarity. To enable efficient STS-Join processing on large sets of semantic trajectories, we develop trajectory pair filtering techniques and consider the parallel processing capabilities of modern processors. Specifically, we present a two-phase parallel search algorithm. We first group semantic trajectories based on their text information. The algorithm's per-group searches are independent of each other and thus can be performed in parallel. For each group, the trajectories are further partitioned based on the spatial domain. We generate spatial and textual summaries for each trajectory batch, based on which we develop batch filtering and trajectory-batch filtering techniques to prune unqualified trajectory pairs in a batch mode. Additionally, we propose an efficient divide-and-conquer algorithm to derive bounds of spatial similarity and textual similarity between two semantic trajectories, which enable us prune dissimilar trajectory pairs without the need of computing the exact value of spatio-textual similarity. Experimental study with large semantic trajectory data confirms that our algorithm of processing semantic trajectory join is capable of outperforming our well-designed baseline by a factor of 8-12.

We investigate the problem of optimal route planning for massive-scale trips: Given a traffic-aware road network and a set of trip queries Q, we aim to find a route for each trip such that the global travel time cost for all queries in Q is minimized. Our problem is designed for a range of applications such as traffic-flow management, route planning and congestion prevention in rush hours. The exact algorithm bears exponential time complexity and is computationally prohibitive for application scenarios in dynamic traffic networks. To address the challenge, we propose a greedy algorithm and an epsilon-refining algorithm. Extensive experiments offer insight into the accuracy and efficiency of our proposed algorithms.

With the increasing popularity of location-aware social media services, next-Point-of-Interest (POI) recommendation has gained significant research interest. The key challenge of next-POI recommendation is to precisely learn users' sequential movements from sparse check-in data. To this end, various embedding methods have been proposed to learn the representations of check-in data in the Euclidean space. However, their ability to learn complex patterns, especially hierarchical structures, is limited by the dimensionality of the Euclidean space. To this end, we propose a new research direction that aims to learn the representations of check-in activities in a hyperbolic space, which yields two advantages. First, it can effectively capture the underlying hierarchical structures, which are implied by the power-law distributions of user movements. Second, it provides high representative strength and enables the check-in data to be effectively represented in a low-dimensional space. Specifically, to solve the next-POI recommendation task, we propose a novel hyperbolic metric embedding (HME) model, which projects the check-in data into a hyperbolic space. The HME jointly captures sequential transition, user preference, category and region information in a unified approach by learning embeddings in a shared hyperbolic space. To the best of our knowledge, this is the first study to explore a non-Euclidean embedding model for next-POI recommendation. We conduct extensive experiments on three check-in datasets to demonstrate the superiority of our hyperbolic embedding approach over the state-of-the-art next-POI recommendation algorithms. Moreover, we conduct experiments on another four online transaction datasets for next-item recommendation to further demonstrate the generality of our proposed model.

Massive amount of spatio-temporal data that contain location and text content are being generated by location-based social media. These spatio-temporal messages cover a wide range of topics. It is of great significance to discover local trending topics based on users’ location-based and topicbased requirements. We develop a region-based message exploration mechanism that retrieve spatio-temporal message clusters from a stream of spatio-temporal messages based on users’ preferences on message topic and message spatial distribution. Additionally, we propose a region summarization algorithm that finds a subset of representative messages in a cluster to summarize the topics and the spatial attributes of messages in the cluster. We evaluate the efficacy and efficiency of our proposal on two real-world datasets and the results demonstrate that our solution is capable of high efficiency and effectiveness compared with baselines.

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.

With the popularization of portable devices, numerous applications continuously produce huge streams of geo-tagged textual data, thus posing challenges to index geo-textual streaming data efficiently, which is an important task in both data management and AI applications, e.g., real-time data streams mining and targeted advertising. This, however, is not possible with the state-of-the-art indexing methods as they focus on search optimizations of static datasets, and have high index maintenance cost. In this paper, we present NQ-tree, which combines new structure designs and self-tuning methods to navigate between update and search efficiency. Our contributions include: (1) the design of multiple stores each with a different emphasis on write-friendness and read-friendness; (2) utilizing data compression techniques to reduce the I/O cost; (3) exploiting both spatial and keyword information to improve the pruning efficiency; (4) proposing an analytical cost model, and using an online self-tuning method to achieve efficient accesses to different workloads. Experiments on two real-world datasets show that NQ-tree outperforms two well designed baselines by up to 10×.

With the increasing availability of moving-object tracking data, use of this data for route search and recommendation is increasingly important. To this end, we propose a novel parallel split-and-combine approach to enable route search by locations (RSL-Psc). Given a set of routes, a set of places to visit O, and a threshold θ, we retrieve the route composed of sub-routes that (i) has similarity to O no less than θ and (ii) contains the minimum number of sub-route combinations. The resulting functionality targets a broad range of applications, including route planning and recommendation, ridesharing, and location-based services in general. To enable efficient and effective RSL-Psc computation on massive route data, we develop novel search space pruning techniques and enable use of the parallel processing capabilities of modern processors. Specifically, we develop two parallel algorithms, Fully-Split Parallel Search (FSPS) and Group-Split Parallel Search (GSPS). We divide the route split-and-combine task into ∑k=0 M S(|O|,k+1) sub-tasks, where M is the maximum number of combinations and S(⋅) is the Stirling number of the second kind. In each sub-task, we use network expansion and exploit spatial similarity bounds for pruning. The algorithms split candidate routes into sub-routes and combine them to construct new routes. The sub-tasks are independent and are performed in parallel. Extensive experiments with real data offer insight into the performance of the algorithms, indicating that our RSL-Psc problem can generate high-quality results and that the two algorithms are capable of achieving high efficiency and scalability.

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.

Massive amount of data that contain spatial, textual, and temporal information are being generated at a high scale. These spatio-temporal documents cover a wide range of topics in local area. Users are interested in receiving local popular terms from spatio-temporal documents published with a specified region. We consider the Top-k Spatial-Temporal Term (ST2) Subscription. Given an ST2 subscription, we continuously maintain up-to-date top-k most popular terms over a stream of spatio-temporal documents. The ST2 subscription takes into account both frequency and recency of a term generated from spatio-temporal document streams in evaluating its popularity. We propose an efficient solution to process a large number of ST2 subscriptions over a stream of spatio-temporal documents. The performance of processing ST2 subscriptions is studied in extensive experiments based on two real spatio-temporal datasets.

We propose and investigate a novel query type named trajectory search by regions of interest (TSR query). Given an argument set of trajectories, a TSR query takes a set of regions of interest as a parameter and returns the trajectory in the argument set with the highest spatial-density correlation to the query regions. This type of query is useful in applications such as trip planning and recommendation. To process the TSR query, a set of new metrics are defined to model spatial-density correlations. An efficient trajectory search algorithm is developed that exploits upper and lower bounds to prune the search space and that adopts a query-source selection strategy, as well as integrates a heuristic search strategy based on priority ranking to schedule multiple query sources. The performance of TSR query processing is studied in extensive experiments based on real and synthetic spatial data.

Huge amount of data with both space and text information, e.g., geo-tagged tweets, is flooding on the Internet. Such spatio-textual data stream contains valuable information for millions of users with various interests on different keywords and locations. Publish/subscribe systems enable efficient and effective information distribution by allowing users to register continuous queries with both spatial and textual constraints. However, the explosive growth of data scale and user base has posed challenges to the existing centralized publish/subscribe systems for spatiotextual data streams. In this paper, we propose our distributed publish/subscribe system, called PS2Stream, which digests a massive spatio-textual data stream and directs the stream to target users with registered interests. Compared with existing systems, PS2Stream achieves a better workload distribution in terms of both minimizing the total amount of workload and balancing the load of workers. To achieve this, we propose a new workload distribution algorithm considering both space and text properties of the data. Additionally, PS2Stream supports dynamic load adjustments to adapt to the change of the workload, which makes PS2Stream adaptive. Extensive empirical evaluation, on commercial cloud computing platform with real data, validates the superiority of our system design and advantages of our techniques on system performance improvement.

We propose and investigate a novel query, the Collective Travel Planning (CTP) query, that finds the lowest-cost route connecting multiple query sources and a destination via at most k meeting points. This type of query is useful in organizing large events, and it can bring significant benefits to society and the environment: it can help optimize the allocation of transportation resources, reduce resource consumption, and enable smarter and greener transportation; and it can help reduce greenhouse-gas emissions and traffic congestion.

Air quality is one of the most important environmental concerns in the world, and it has deteriorated substantially over the past years in many countries. For example, Chinese Academy of Social Sciences reports that the problem of haze and fog in China is hitting a record level, and China is currently suffering from the worst air pollution. Among the various causal factors of air quality, particulate matter with a diameter of 2.5 micrometers or less (i.e., PM2.5) is a very important factor; governments and people are increasingly concerned with the concentration of PM2.5. In many cities, stations for monitoring PM2.5 concentration have been built by governments or companies to monitor urban air quality. Apart from monitoring, there is a rising demand for finding pollution sources of PM2.5 and discovering the transmission of PM2.5 based on the data from PM$_{2.5}$ monitoring stations.

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.

With the increasing availability of moving-object tracking data, trajectory search is increasingly important. We propose and investigate a novel query type named trajectory search by regions of interest (TSR query). Given an argument set of trajectories, a TSR query takes a set of regions of interest as a parameter and returns the trajectory in the argument set with the highest spatial-density correlation to the query regions. This type of query is useful in many popular applications such as trip planning and recommendation, and location based services in general. TSR query processing faces three challenges: how to model the spatial-density correlation between query regions and data trajectories, how to effectively prune the search space, and how to effectively schedule multiple so-called query sources. To tackle these challenges, a series of new metrics are defined to model spatial-density correlations. An efficient trajectory search algorithm is developed that exploits upper and lower bounds to prune the search space and that adopts a query-source selection strategy, as well as integrates a heuristic search strategy based on priority ranking to schedule multiple query sources. The performance of TSR query processing is studied in extensive experiments based on real and synthetic spatial data.

With the proliferation of geo-positioning techniques that enable users to acquire their geographical positions, there has been increasing popularity of online location-based services. This development has generated a large volume of points of interest labeled with category features (e.g., hotel, resort, stores, stations, and tourist attractions). It gives prominence to various types of spatial-keyword queries, which are employed to provide fundamental querying functionality for location-based services.

Huge amounts of data with both spatial and temporal information (e.g., geo-tagged tweets) are being generated, and are often used to share and spread personal updates, spontaneous ideas, and breaking news. We refer to such data as spatio-temporal documents. It is of great interest to explore topics in a collection of spatio-temporal documents.

Rich geo-textual data is available online and the data keeps increasing at a high speed. We propose two user behavior models to learn several types of user preferences from geo-textual data, and a prototype system on top of the user pre ference models for min ing and s e a r ch geo-textual data (called PreMiner) to support personalized maps. Different from existing recommender systems and data analysis systems, PreMiner highly personalizes user experience on maps and supports several applications, including user mobility & interests mining, opinion mining in regions, user recommendation, point-of-interest recommendation, and querying and subscribing on geo-textual data.

Travel planning and recommendation are important aspects of transportation. We propose and investigate a novel Collective Travel Planning (CTP) query that finds the lowest-cost route connecting multiple sources and a destination, via at most$k$meeting points. When multiple travelers target the same destination (e.g., a stadium or a theater), they may want to assemble at meeting points and then go together to the destination by public transport to reduce their global travel cost (e.g., energy, money, or greenhouse-gas emissions). This type of functionality holds the potential to bring significant benefits to society and the environment, such as reducing energy consumption and greenhouse-gas emissions, enabling smarter and greener transportation, and reducing traffic congestions. The CTP query is Max SNP-hard. To compute the query efficiently, we develop two algorithms, including an exact algorithm and an approximation algorithm. The exact algorithm is capable finding the optimal result for small values of$k$(e.g.,$k = 2$) in interactive time, while the approximation algorithm, which has a$5$-approximation ratio, is suitable for other situations. The performance of the CTP query is studied experimentally with real and synthetic spatial data.

Massive amount of data that are geo-tagged and associated with text information are being generated at an unprecedented scale. These geo-textual data cover a wide range of topics. Users are interested in receiving up-to-date tweets such that their locations are close to a user specified location and their texts are interesting to users. For example, a user may want to be updated with tweets near her home on the topic “food poisoning vomiting.” We consider the Temporal Spatial-Keyword Top-k Subscription (TaSK) query. Given a TaSK query, we continuously maintain up-to-date top-k most relevant results over a stream of geo-textual objects (e.g., geo-tagged Tweets) for the query. The TaSK query takes into account text relevance, spatial proximity, and recency of geo-textual objects in evaluating its relevance with a geo-textual object. We propose a novel solution to efficiently process a large number of TaSK queries over a stream of geotextual objects. We evaluate the efficiency of our approach on two real-world datasets and the experimental results show that our solution is able to achieve a reduction of the processing time by 70-80% compared with two baselines.

Massive amount of text data are being generated by a huge number of web users at an unprecedented scale. These data cover a wide range of topics. Users are interested in receiving a few up-to-date representative documents (e.g., tweets) that can provide them with a wide coverage of different aspects of their query topics. To address the problem, we consider the Diversity-Aware Top-k Subscription (DAS) query. Given a DAS query, we continuously maintain an up-to-date result set that contains k most recently returned documents over a text stream for the query. The DAS query takes into account text relevance, document recency, and result diversity. We propose a novel solution to efficiently processing a large number of DAS queries over a stream of documents. We demonstrate the efficiency of our approach on real-world dataset and the experimental results show that our solution is able to achieve a reduction of the processing time by 60--75% compared with two baselines. We also study the effectiveness of the DAS query.

Massive amount of data that are geo-tagged and associated with text information are being generated at an unprecedented scale. These geo-textual data cover a wide range of topics. Users are interested in receiving up-to-date geo-textual objects (e.g., geo-tagged Tweets) such that their locations meet users' need and their texts are interesting to users. For example, a user may want to be updated with tweets near her home on the topic "dengue fever headache". AB@In this demonstration, we present SOPS, the Spatial-Keyword Publish/Subscribe System, that is capable of efficiently processing spatial keyword continuous queries. SOPS supports two types of queries: (1) Boolean Range Continuous (BRC) query that can be used to subscribe the geo-textual objects satisfying a boolean keyword expression and falling in a specified spatial region; (2) Temporal Spatial-Keyword Top- k Continuous (TaSK) query that continuously maintains up-to-date top- k most relevant results over a stream of geo-textual objects. SOPS enables users to formulate their queries and view the real-time results over a stream of geo-textual objects by browser-based user interfaces. On the server side, we propose solutions to efficiently processing a large number of BRC queries (tens of millions) and TaSK queries over a stream of geo-textual objects.

We present the Keyword-aware Optimal Route Search System (KORS), which efficiently answers the KOR queries. A KOR query is to find a route such that it covers a set of user-specified keywords, a specified budget constraint is satisfied, and an objective score of the route is optimized. Consider a tourist who wants to spend a day exploring a city. The user may issue the following KOR query: “find the most popular route such that it passes by shopping mall, restaurant, and pub, and the travel time to and from her hotel is within 4 hours.” KORS provides browser-based interfaces for desktop and laptop computers and provides a client application for mobile devices as well. The interfaces and the client enable users to formulate queries and view the query results on a map. Queries are then sent to the server for processing by the HTTP post operation. Since answering a KOR query is NP-hard, we devise two approximation algorithms with provable performance bounds and one greedy algorithm to process the KOR queries in our KORS prototype. We use two real-world datasets to demonstrate the functionality and performance of this system.

Massive amount of data that are geo-tagged and associated with text information are being generated at an unprecedented scale. Users may want to be notified of interesting geo-textual objects during a period of time. For example, a user may want to be informed when tweets containing term "garage sale" are posted within 5 km of the user's home in the next 72 hours.

Geo-textual indices play an important role in spatial keyword querying. The existing geo-textual indices have not been compared systematically under the same experimental framework. This makes it difficult to determine which indexing technique best supports specific functionality. We provide an all-around survey of 12 state-of-the-art geo-textual indices. We propose a benchmark that enables the comparison of the spatial keyword query performance. We also report on the findings obtained when applying the benchmark to the indices, thus uncovering new insights that may guide index selection as well as further research.

Identifying a preferable route is an important problem that finds applications in map services. When a user plans a trip within a city, the user may want to find "a most popular route such that it passes by shopping mall, restaurant , and pub , and the travel time to and from his hotel is within 4 hours." However, none of the algorithms in the existing work on route planning can be used to answer such queries. Motivated by this, we define the problem of keyword-aware optimal route query, denoted by KOR, which is to find an optimal route such that it covers a set of user-specified keywords, a specified budget constraint is satisfied, and an objective score of the route is optimal. The problem of answering KOR queries is NP-hard. We devise an approximation algorithm OSScaling with provable approximation bounds. Based on this algorithm, another more efficient approximation algorithm BucketBound is proposed. We also design a greedy approximation algorithm. Results of empirical studies show that all the proposed algorithms are capable of answering KOR queries efficiently, while the BucketBound and Greedy algorithms run faster. The empirical studies also offer insight into the accuracy of the proposed algorithms.