Trajectory prediction estimates an entity's future path from its historical movements, enabling applications in autonomous navigation, robotics, and mobility analytics. This highlight paper presents TrajLearn, a deep generative framework that models higher-order mobility flows using a hexagonal spatial representation. TrajLearn combines a Transformer-based architecture with a constrained beam search to explore multiple plausible paths while preserving spatial continuity. Experiments on real-world datasets show up to 40% accuracy improvement over state-of-the-art models. We also propose a hierarchical mixed-resolution mapping algorithm that adaptively applies finer granularity to high-activity regions while using coarser resolution elsewhere, optimizing storage and computation. TrajLearn provides a scalable and reproducible foundation for accurate trajectory prediction in dynamic spatial environments.

Current AI models for mobility analytics, built on static datasets and generative architectures, are reaching their limits. They often fail to account for physical constraints, lack long-term memory, and struggle with reasoning and planning in dynamic environments. We introduce a vision for Structured Experiential Mobility Intelligence. At its core are World Foundation Models (WFMs), which capture the spatial, temporal, and causal structure of urban environments. WFMs enable mobility agents, through stream-based reinforcement learning, to reason about causality, plan within constraints, and adapt in real time by continuously learning from realistic, physically grounded interactions. We also present a research roadmap to advance this vision, highlighting key research questions and the methodologies needed to address them. Our vision aligns with Kantian epistemology, where knowledge emerges through the synthesis of a priori structures and experiential learning.

Sophisticated location and tracking technologies have led to the generation of vast amounts of trajectory data. Of interest is constructing a small set of basic building blocks that can represent a wide range of trajectories, known as a trajectory pathlet dictionary. This dictionary can be useful in various tasks and applications, such as trajectory compression, travel time estimation, route planning, and navigation services. Existing methods for constructing a pathlet dictionary use a top-down approach, which generates a large set of candidate pathlets and selects the most popular ones to form the dictionary. However, this approach is memory-intensive and leads to redundant storage due to the assumption that pathlets can overlap. To address these limitations, we propose a bottom-up approach for constructing a pathlet dictionary that significantly reduces memory storage needs of baseline methods by multiple orders of magnitude (by up to ~24K× better). The key idea is to initialize unit-length pathlets and iteratively merge them, while maximizing utility. The utility is defined using newly introduced metrics of trajectory loss and representability. A deep reinforcement learning method is proposed, PathletRL, that uses Deep Q Networks (Dqn) to approximate the utility function. Experiments show that our method outperforms the current state-of-the-art, both on synthetic and real-world data. Our method can reduce the size of the constructed dictionary by up to 65.8% compared to other methods. It is also shown that only half of the pathlets in the dictionary is needed to reconstruct 85% of the original trajectory data.

Research on trajectory data mining relies on appropriate datasets, including Gps-based geolocations, check-in data to points of interest (Pois), and synthetic datasets. Even though some data are accessible, the majority of mobility datasets are typically discovered through ad-hoc searches and lack comprehensive documentation of their generation process or source to reproduce curated or customized versions of them. At the same time, there has been a growing interest in a new type of mobility data, describing trajectories as sequences of higher-order geometric elements like hexagons that offer several benefits: (i) reduced sparsity and analysis at different granularity levels, (ii) compatibility with popular machine learning architectures, (iii) improved generalization and reduced overfitting, and (iv) efficient visualization. To this end, we present Point2Hex, a method and tool for generating higher-order mobility flow datasets from raw trajectory data. We used Point2Hex to create higherorder versions of seven popular mobility datasets typically employed in trajectory-related technical problems and downstream tasks, such as trajectory prediction, classification, clustering, imputation, and anomaly detection, to name a few. To promote reuse and encourage reproducibility, we provide the source code and documentation of Point2Hex, as well as the generated higher-order mobility flow datasets in publicly accessible repositories.

Trajectory user linking (TUL) is a problem in trajectory classification that links anonymous trajectories to the users who generated them. TUL has various uses such as identity verification, personalized recommendation, epidemiological monitoring, and threat assessments. A major challenge in TUL modeling is sparse data. Previous TUL research heavily relies on sequence-to-sequence models such as RNNs and LSTMs, with trajectory segmentation to combat sparsity, but segmentation does not sufficiently address the issue and existing models often ignore data skewness, resulting in poor precision and performance. To address these problems, we present TULHOR, a TUL model inspired by BERT, a popular language representation model. One of TULHOR’s innovations is the use of higher-order mobility flow data representations enabled by geographic area tessellation. This allows the model to alleviate the sparsity problem and also to generalize better. TULHOR consists of a spatial embedding layer, a spatial-temporal embedding layer and an encoder layer, which encodes properties and learns a rich trajectory representation. It is trained in two steps, first using a masked language modeling task to learn general embeddings, then fine-tuned using a balanced cross-entropy loss to make predictions while handling imbalanced data. Experiments on real-life mobility data show TULHOR’s effectiveness as compared to current state-of-the-art models.

Traffic congestion is characterized by longer trip times, and increased air pollution. In a static road network, the travel time to a destination is constant and can be computed using the shortest path first algorithm (SPF). However, road network conditions are dynamic, rendering the SPF to perform sub-optimally at times. In addition, in a realistic multiple-vehicle scenario, the SPF routing algorithm can cause congestion by routing all vehicles through the same shortest path. In this paper, we propose a network-aware multi-agent reinforcement learning model for addressing this problem. Our key idea is to assign an RL agent to intersections. Each RL agent operates as a router agent and is responsible for providing routing instructions to approaching vehicles. When a vehicle reaches an intersection, it submits a routing query to the RL agent consisting of its final destination. The RL agent generates a routing response based on (i) the destination, (ii) the current state of the road network, and (iii) routing policies learned by cooperating with other neighboring RL agents. Our experimental evaluation shows that the proposed MARL model outperforms the SPF algorithm by (up to) 20.2% in average travel time.

Road intersections represent one of the most complex configurations encountered when traversing road networks. It is therefore of vital importance to improve their operational performance, as that can significantly contribute towards the efficiency of the whole transport network. Traditional approaches to improve the efficiency of intersections are based on analysis of static data or expert opinions. However, due to the advancements on Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communication technologies, it is possible to enhance safety and improve road intersection efficiency by continuously monitoring traffic conditions and enabling situational awareness of vehicle drivers. Towards this end, we design, develop and evaluate a system for evaluating and forecasting the operational performance of road intersections by mining streams of V2I data. Our system makes use of graph mining and trajectory data mining methods to continuously evaluate a set of well-defined measures of effectiveness (MOEs) for traffic operations at different levels of road network abstraction. In addition, the system enables interactive analysis and exploration of the various MOEs. The system architecture and methods are general and can be used in various settings requiring continuous monitoring and/or forecasting of the road network state.

The relationship between human mobility and the spread of an infectious disease has been well documented. At the same time, availability of mobility data is growing due to advancements in digital contact tracing mobile applications and GPS-enabled devices. Motivated by these observations, we have designed and developed STRIPE (Safe Trips during Epidemics), a mobility-based recommendation system that can provide safer trip recommendations to individuals. The recommendation model considers the risk of infection of alternative trips between an origin and destination. It also considers the risk of infection of specific points of interests (POIs) that occur at the microscale. In this paper, we present a high-level architecture of the system, its main features and system use cases. The broader impact of our research is that by helping individuals making informed decisions, we promote more responsible behaviors in the community as a whole that could effectively alleviate the impact of the epidemic.

The bulk synchronous parallel (BSP) is a celebrated synchronization model for distributed training of deep learning models. A shortcoming of the BSP is that it requires workers to wait for the straggler at every iteration. Therefore, employing BSP increases the waiting time of the faster workers of a cluster and results in an overall prolonged training time. To ameliorate this shortcoming of BSP, we proposed ElasticBSP [1], a model that aims to relax its strict synchronization requirement with an elastic synchronization by allowing delayed synchronization to minimize the waiting time. ELASTICBSP is realized by the algorithm named ZipLine. In this work, we show the theoretical proof of ZipLine and further propose algorithmic and implementation optimizations of ZipLine, namely ZipLineOpt and Ziplineoptbs, which reduce the time complexity of ZipLine to linearithmic time. The experiments show that ZipLineOpt and ZipLineOptBs enable the scalability of ElasticBSP. Further experimental evaluation on large deep neural networks on large ImageNet dataset demonstrate that our proposed Elas-ticbspmodel, materialized by the proposed optimized ZipLine variants, converges faster and to a higher accuracy than the predominant BSP.

Several data mining and machine learning problems can be reduced to the computational geometry problem of finding intersections of a set of geometric objects, such as intersections of line segments or rectangles/boxes. Currently, the state-of-the-art approach for addressing such intersection problems in Euclidean space is collectively known as the sweep-line or plane sweep algorithm, and has been utilized in a variety of application domains, including databases, gaming and transportation, to name a few. The idea behind sweep line is to employ a conceptual line that is swept or moved across the plane, stopping at intersection points. However, to report all K intersections among any N objects, the standard sweep line algorithm (based on the Bentley-Ottmann algorithm) has a time complexity of O((N + K)logN), therefore cannot scale to very large number of objects and cases where there are many intersections. In this paper, we propose MRSWEEP and MRSWEEP-D, two sophisticated and highly scalable algorithms for the parallelization of sweep-line and its variants. We provide algorithmic details of fully distributed in-memory versions of the proposed algorithms using the MapReduce programming paradigm in the Apache Spark cluster environment. A theoretical analysis of the proposed algorithms is presented, as well as a thorough experimental evaluation that provides evidence of the algorithms' scalability in varying levels of problem complexity. We make source code and datasets available to support the reproducibility of the results.

Mining trajectory data to find interesting patterns is of increasing research interest due to a broad range of useful applications, including analysis of transportation systems, location-based social networks, and crowd behavior. The primary focus of this research is to leverage the abundance of trajectory data to automatically and accurately learn latent semantic relationships between different geographical areas (e.g., semantically correlated neighborhoods of a city) as revealed by patterns of moving objects over time. While previous studies have utilized trajectories for this type of analysis at the level of a single geographical area, the results cannot be easily generalized to inform comparative analysis of different geographical areas. In this paper, we study this problem systematically. First, we present a method that utilizes trajectories to learn low-dimensional representations of geographical areas in an embedded space. Then, we develop a statistical method that allows to quantify the degree to which real trajectories deviate from a theoretical null model. The method allows to (a) distinguish geographical proximity to semantic proximity, and (b) inform a comparative analysis of two (or more) models obtained by trajectories defined on different geographical areas. This deep analysis can improve our understanding of how space is perceived by individuals and inform better decisions of urban planning. Our experimental evaluation aims to demonstrate the effectiveness and usefulness of the proposed statistical method in two large-scale real-world data sets coming from the New York City and the city of Porto, Portugal, respectively. The methods we present are generic and can be utilized to inform a number of useful applications, ranging from location-based services, such as point-of-interest recommendations, to finding semantic relationships between different cities.

One popular thread of research in computational sarcasm detection involves modeling sarcasm as a contrast between positive and negative sentiment polarities or exploring more fine-grained categories of emotions such as happiness, sadness, surprise, and so on. Most current models, however, treat these affective features independently, without regard for the sequential information encoded among the affective states. In order to explore the role of transitions in affective states, we formulate the task of sarcasm detection as a sequence classification problem by leveraging the natural shifts in various emotions over the course of a piece of text. Experiments conducted on datasets from two different genres suggest that our proposed approach particularly benefits datasets with limited labeled data and longer instances of text.

Identifying and quantifying the size of multiple intersections among a large number of axis-aligned geometric objects is an essential computational geometry problem. The ability to solve this problem can effectively inform a number of spatial data mining methods and can provide support in decision making for a variety of applications. Currently, the state-of-the-art approach for addressing such intersection problems resorts to an algorithmic paradigm, collectively known as the sweep-line algorithm. However, its application on specific instances of the problem inherits a number of limitations. With that mind, we design and implement a novel, exact, fast and scalable yet versatile, sweep-line based algorithm, named SLIG. Our algorithm can be employed in a number of problems and applications involving the efficient computation of numerous axis-aligned object intersection problems in multiple dimensions. The key idea of our algorithm lies in constructing an auxiliary data structure when the sweep line algorithm is applied, an intersection graph. This graph can effectively be used to provide connectivity properties among overlapping objects, as well as to inform the much harder problem of finding the location and size of the common area defined by multiple overlapping objects. A thorough experimental evaluation on synthetic data of various characteristics and sizes, demonstrates that SLIG performs significantly faster than classic sweep-line based algorithms. SLIG is not only faster and more versatile, but also provides a suite of powerful querying capabilities. To support the reproducibility of our methods, we make source code and datasets available.

The bulk synchronous parallel (BSP) is a celebrated synchronization model for general-purpose parallel computing that has successfully been employed for distributed training of machine learning models. A prevalent shortcoming of the BSP is that it requires workers to wait for the straggler at every iteration. To ameliorate this shortcoming of classic BSP, we propose ELASTICBSP a model that aims to relax its strict synchronization requirement. The proposed model offers more flexibility and adaptability during the training phase, without sacrificing on the accuracy of the trained model. We also propose an efficient method that materializes the model, named ZIPLINE. The algorithm is tunable and can effectively balance the trade-off between quality of convergence and iteration throughput, in order to accommodate different environments or applications. A thorough experimental evaluation demonstrates that our proposed ELASTICBSP model converges faster and to a higher accuracy than the classic BSP. It also achieves comparable (if not higher) accuracy than the other sensible synchronization models.

Mining large-scale trajectory data streams (of moving objects) has attracted significant attention due to an abundance of modern tracking devices and a number of real-world applications. In this paper, we are interested in evaluating the relative importance of such objects through monitoring their interactions with other objects, over time. Which object has encountered more other objects? When did these encounters happen and how long did they last? To address this type of questions, we consider a trajectory network that is defined based on the proximity of moving objects over time. Given this network, we are able to evaluate the importance of an object (node) by monitoring its complex network connections to other nodes over time. Traditional approaches to address the problem rely on either evaluating network metrics over a number of static network snapshots or expensive trajectory similarity and clustering methods that require further post-processing. Streaming algorithms also exist, but they focus on simple network metrics. In contrast to these approaches, we devise a method that is able to simultaneously evaluate node importance metrics for all moving objects in the trajectory network. Our proposed method is based on, first, efficiently computing and representing the interactions of moving objects as time intervals. Then, a fast and accurate one-pass sweep-line algorithm over the trajectories (SLOT) is devised that can effectively compute the metrics of interest, all at once. Through experiments on various types of data, we demonstrate that our algorithm is a multitude of times faster than sensible baselines, for a varying range of conditions.

Mining large-scale trajectory data streams (of moving objects) has been of ever increasing research interest due to an abundance of modern tracking devices and its large number of critical applications. In this paper, we are interested in mining group patterns of moving objects. Group pattern mining describes a special type of trajectory mining task that requires to efficiently discover trajectories of objects that are found in close proximity to each other for a period of time. In particular, we focus on trajectories of pedestrians coming from motion video analysis and we are interested in interactive analysis and exploration of group dynamics, including various definitions of group gathering and dispersion. Towards this end, we present a suite of (three) tensor-based methods for efficient discovery of evolving groups of pedestrians. Traditional approaches to solve the problem heavily rely on well-defined clustering algorithms to discover groups of pedestrians at each time point, and then post-process these groups to discover groups that satisfy specific group pattern semantics, including time constraints. In contrast, our proposed methods are based on efficiently discovering pairs of pedestrians that move together over time, under varying conditions. Pairs of pedestrians are subsequently used as a building block for effectively discovering groups of pedestrians. The suite of proposed methods provides the ability to adapt to many different scenarios and application requirements. Furthermore, a query-based search method is provided that allows for interactive exploration and analysis of group dynamics over time and space. Through experiments on real data, we demonstrate the effectiveness of our methods on discovering group patterns of pedestrian trajectories against sensible baselines, for a varying range of conditions. In addition, a visual testing is performed on real motion video to assert the group dynamics discovered by each method.

Mining large-scale trajectory data streams (of moving objects) has been of ever increasing research interest due to an abundance of modern tracking devices and its large number of critical applications. A challenging task in this domain is that of mining group patterns of moving objects. Group pattern mining describes a special type of trajectory mining that requires to efficiently discover trajectories of objects that are found in close proximity to each other for a period of time. To this end, we introduce Trajectolizer, an online system for interactive analysis and exploration of trajectory group dynamics over time and space. We describe the system and demonstrate its effectiveness on discovering group patterns on trajectories of pedestrians. The system architecture and methods are general and can be used to perform group analysis of any domain-specific trajectories.

Small changes on the structure of a graph can have a dramatic effect on its connectivity. While in the traditional graph theory, the focus is on well-defined properties of graph connectivity, such as biconnectivity, in the context of a social graph , connectivity is typically manifested by its ability to carry on social processes . In this paper, we consider the problem of adding a small set of nonexisting edges ( shortcuts ) in a social graph with the main objective of minimizing its characteristic path length . This property determines the average distance between pairs of vertices and essentially controls how broadly information can propagate through a network. We formally define the problem of interest, characterize its hardness and propose a novel method, path screening , which quickly identifies important shortcuts to guide the augmentation of the graph. We devise a sampling-based variant of our method that can scale up the computation in larger graphs. The claims of our methods are formally validated. Through experiments on real and synthetic data, we demonstrate that our methods are a multitude of times faster than standard approaches, their accuracy outperforms sensible baselines and they can ease the spread of information in a network, for a varying range of conditions.

As online social networking emerges, there has been increased interest to utilize the underlying network structure as well as the available information on social peers to improve the information needs of a user. In this paper, we focus on improving the performance of information collection from the neighborhood of a user in a dynamic social network. We introduce sampling-based algorithms to efficiently explore a user's social network respecting its structure and to quickly approximate quantities of interest. We introduce and analyze variants of the basic sampling scheme exploring correlations across our samples. Models of centralized and distributed social networks are considered. We show that our algorithms can be utilized to rank items in the neighborhood of a user, assuming that information for each user in the network is available. Using real and synthetic data sets, we validate the results of our analysis and demonstrate the efficiency of our algorithms in approximating quantities of interest. The methods we describe are general and can probably be easily adopted in a variety of strategies aiming to efficiently collect information from a social graph.

Small changes in the network topology can have dramatic effects on its capacity to disseminate information. In this paper, we consider the problem of adding a small number of ghost edges in the network in order to minimize the average shortest-path distance between nodes, towards a smaller-world network. We formalize the problem of suggesting ghost edges and we propose a novel method for quickly evaluating the importance of ghost edges in sparse graphs. Through experiments on real and synthetic data sets, we demonstrate that our approach performs very well, for a varying range of conditions, and it outperforms sensible baselines.

For a place that gathers millions of people the Web seems pretty lonely at times. This is mainly due to the current predominant browsing scenario; that of an individual participating in an autonomous surfing session. We believe that people should be seen as an integral part of the browsing and searching activity towards a concept known as social navigation. In this work, we extend the typical Web browserpsilas functionality so as to raise awareness of other people having similar Web surfing goals at the current moment. We further present features and algorithms that facilitate online communication and collaboration towards common searching targets. The utility of our system is established by experimental studies. The extentions we present can be easily adopted in a typical Web browser.

Information in digital libraries and information systems frequently refers to locations or objects in geographic space. Digital gazetteers are commonly employed to match the referred placenames with actual locations in information integration and data cleaning procedures. This process may fail due to missing information in the gazetteer, multiple matches, or false positive matches. We have analyzed the cases of success and reasons for failure of the mapping process to a gazetteer. Based on these, we present a statistical model that permits estimating 1) the completeness of a gazetteer with respect to the specific target area and application, 2) the expected precision and recall of one-to-one mappings of source placenames to the gazetteer, 3) the semantic inconsistency that remains in one-to-one mappings, and 4) the degree to which the precision and recall are improved under knowledge of the identity of higher levels in a hierarchy of places. The presented model is based on statistical analysis of the mapping process of a large set of placenames itself and does not require any other background data. The statistical model assumes that a gazetteer is populated by a stochastic process. The paper discusses how future work could take deviations from this assumption into account. The method has been applied to a real case.