An official website of the United States government
Abstract Identifying the underlying trajectory pattern in the spatial‐temporal data analysis is a fundamental but challenging task. In this paper, we study the problem of simultaneously identifying temporal trends and spatial clusters of spatial‐temporal trajectories. To achieve this goal, we propose a novel method named spatial clustered and sparse nonparametric regression (). Our method leverages the B‐spline model to fit the temporal data and penalty terms on spline coefficients to reveal the underlying spatial‐temporal patterns. In particular, our method estimates the model by solving a doubly‐penalized least square problem, in which we use a group sparse penalty for trend detection and a spanning tree‐based fusion penalty for spatial cluster recovery. We also develop an algorithm based on the alternating direction method of multipliers (ADMM) algorithm to efficiently minimize the penalized least square loss. The statistical consistency properties of estimator are established in our work. In the end, we conduct thorough numerical experiments to verify our theoretical findings and validate that our method outperforms the existing competitive approaches.
more »
« less
Only Attending What Matter within Trajectories – Memory-Efficient Trajectory Attention
Human-generated Spatial-Temporal Data (HSTD), represented as trajectory sequences, has undergone a data revolution, thanks to advances in mobile sensing, data mining, and AI. Previous studies have revealed the effectiveness of employing attention mechanisms to analyze massive HSTD. However, traditional attention models face challenges when managing lengthy and noisy trajectories as their computation comes with large memory overheads. Furthermore, attention scores within HSTD trajectories are sparse (i.e., most of the scores are zeros), and clustered with varying lengths (i.e., consecutive tokens clustered with similar scores). To address these challenges, we introduce an innovative strategy named Memory-efficient Trajectory Attention (MeTA). We leverage complicated spatial-temporal features (e.g., traffic speed, proximity to PoIs) and design an innovative feature-based trajectory partition technique to shrink trajectory length. Additionally, we present a learnable dynamic sorting mechanism, with which attention is only computed between sub-trajectories that have prominent correlations. Empirical validations using real-world HSTD demonstrate that our approach not only yields competitive results but also significantly lowers memory usage compared with state-of-the-art methods. Our approach presents innovative solutions for memory-efficient trajectory attention, offering valuable insights for handling HSTD efficiently.
more »
« less
- Award ID(s):
- 2021871
- PAR ID:
- 10523398
- Publisher / Repository:
- The 2024 SIAM International Conference on Data Mining (SDM)
- Date Published:
- ISBN:
- 978-1-61197-803-2
- Page Range / eLocation ID:
- 481-489
- Format(s):
- Medium: X
- Location:
- Houston, Texas
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We introduce a novel approach to endowing neural networks with emergent, long-term, large-scale memory. Distinct from strategies that connect neural networks to external memory banks via intricately crafted controllers and hand-designed attentional mechanisms, our memory is internal, distributed, co-located alongside computation, and implicitly addressed, while being drastically simpler than prior efforts. Architecting networks with multigrid structure and connectivity, while distributing memory cells alongside computation throughout this topology, we observe the emergence of coherent memory subsystems. Our hierarchical spatial organization, parameterized convolutionally, permits efficient instantiation of large-capacity memories, while multigrid topology provides short internal routing pathways, allowing convolutional networks to efficiently approximate the behavior of fully connected networks. Such networks have an implicit capacity for internal attention; augmented with memory, they learn to read and write specific memory locations in a dynamic data-dependent manner. We demonstrate these capabilities on exploration and mapping tasks, where our network is able to self-organize and retain long-term memory for trajectories of thousands of time steps. On tasks decoupled from any notion of spatial geometry: sorting, associative recall, and question answering, our design functions as a truly generic memory and yields excellent results.more » « less
-
Ruis, Andrew R.; Lee, Seung B. (Ed.)While quantitative ethnographers have used epistemic network analysis (ENA) to model trajectories that show change in network structure over time, visualizing trajectory models in a way that facilitates accurate interpretation has been a significant challenge. As a result, ENA has predominantly been used to construct aggregate models, which can obscure key differences in how network structures change over time. This study reports on the development and testing of a new approach to visualizing ENA trajectories. It documents the challenges associated with visualizing ENA trajectory models, the features constructed to address those challenges, and the design decisions that aid in the interpretation of trajectory models. To test this approach, we compare ENA trajectory models with aggregate models using a dataset with previously published results and known temporal features. This comparison focuses on interpretability and consistency with prior qualitative analysis, and we show that ENA trajectories are able to represent information unavailable in aggregate models and facilitate interpretations consistent with qualitative findings. This suggests that this approach to ENA trajectories is an effective tool for representing change in network structure over time.more » « less
-
Predicting the future trajectories of multiple interacting pedestrians within a scene has increasingly gained importance in various fields, e.g., autonomous driving, human–robot interaction, and so on. The complexity of this problem is heightened due to the social dynamics among different pedestrians and their heterogeneous implicit preferences. In this paper, we present Information Maximizing Spatial-Temporal Graph Convolutional Attention Network (InfoSTGCAN), which takes into account both pedestrian interactions and heterogeneous behavior choice modeling. To effectively capture the complex interactions among pedestrians, we integrate spatial-temporal graph convolution and spatial-temporal graph attention. For grasping the heterogeneity in pedestrians’ behavior choices, our model goes a step further by learning to predict an individual-level latent code for each pedestrian. Each latent code represents a distinct pattern of movement choice. Finally, based on the observed historical trajectory and the learned latent code, the proposed method is trained to cover the ground-truth future trajectory of this pedestrian with a bi-variate Gaussian distribution. We evaluate the proposed method through a comprehensive list of experiments and demonstrate that our method outperforms all baseline methods on the commonly used metrics, Average Displacement Error and Final Displacement Error. Notably, visualizations of the generated trajectories reveal our method’s capacity to handle different scenarios.more » « less
-
Learning explicit and implicit patterns in human trajectories plays an important role in many Location-Based Social Networks (LBSNs) applications, such as trajectory classification (e.g., walking, driving, etc.), trajectory-user linking, friend recommendation, etc. A particular problem that has attracted much attention recently – and is the focus of our work – is the Trajectory-based Social Circle Inference (TSCI), aiming at inferring user social circles (mainly social friendship) based on motion trajectories and without any explicit social networked information. Existing approaches addressing TSCI lack satisfactory results due to the challenges related to data sparsity, accessibility and model efficiency. Motivated by the recent success of machine learning in trajectory mining, in this paper we formulate TSCI as a novel multi-label classification problem and develop a Recurrent Neural Network (RNN)-based framework called DeepTSCI to use human mobility patterns for inferring corresponding social circles. We propose three methods to learn the latent representations of trajectories, based on: (1) bidirectional Long Short-Term Memory (LSTM); (2) Autoencoder; and (3) Variational autoencoder. Experiments conducted on real-world datasets demonstrate that our proposed methods perform well and achieve significant improvement in terms of macro-R, macro-F1 and accuracy when compared to baselines.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Proceeding:
- The DOI is not currently available.
